|
%I M0230 #91 Jan 29 2024 01:52:58
%S 1,1,1,2,2,2,3,4,4,4,4,5,6,6,7,8,8,8,8,8,9,10,10,11,12,12,12,13,14,14,
%T 15,16,16,16,16,16,16,17,18,18,19,20,20,20,21,22,22,23,24,24,24,24,25,
%U 26,26,27,28,28,28,29,30,30,31,32,32,32,32,32,32,32,33,34,34,35,36,36
%N A well-behaved cousin of the Hofstadter sequence: a(n) = a(n - 1 - a(n-1)) + a(n - 2 - a(n-2)) for n > 2 with a(0) = a(1) = a(2) = 1.
%C Number of different partial sums of 1+[1,2]+[1,4]+[1,8]+[1,16]+... E.g., a(6)=3 because we have 6 = 1+1+1+1+1+1 = 1+1+4 = 1+2+1+1+1. - _Jon Perry_, Jan 01 2004
%C Ignoring first term, this is the Meta-Fibonacci sequence for s=1. - _Frank Ruskey_ and Chris Deugau (deugaucj(AT)uvic.ca)
%C Comment from _N. J. A. Sloane_, Jul 03 2014: (Start)
%C The recurrence a(n) = a(n-1-a(n-1)) + a(n-2-a(n-2)) for n>2 with a(0)=X, a(1)=Y, a(2)=Z gives rise to the following sequences (cf. Higham-Tanny 1993):
%C X Y Z
%C 3 1 0 A244483
%C 2 1 0 A240808
%C 2 1 1 A240807
%C 2 0 2 A244478
%C 1 0 2 A240808 again
%C 1 1 1 A006949 (this sequence).
%C Most other initial values do not produce a nontrivial sequence. (End)
%C Higham and Tanny (1993) define a family {t_k(n)} (k=0,12,...) of sequences by t_k(n) = floor(n/2) for 0 <= n < k; thereafter t_k(n) = t_k(n-1-t_k(n-1)) + t_k(n-2-t_k(n-2)). The sequence t_4(n) begins 0, 0, 1, 1, 1, 2, 2, 2, 3, 4, 4, 4, 4, 5, 6, 6, 7, 8, 8, 8, 8, 8, 9, ..., which is essentially this sequence. - _N. J. A. Sloane_, Jul 03 2014
%C The values X=0 Y=1 Z=1 and X=1 Y=1 Z=2 (see above comments) also produce a sequence which is essentially this sequence. - _Pablo Hueso Merino_, Dec 31 2020
%D Jeff Higham and Stephen Tanny, More well-behaved meta-Fibonacci sequences. Proceedings of the Twenty-fourth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1993). Congr. Numer. 98(1993), 3-17.
%D Jeff Higham and Stephen Tanny, A tamely chaotic meta-Fibonacci sequence. Twenty-third Manitoba Conference on Numerical Mathematics and Computing (Winnipeg, MB, 1993). Congr. Numer. 99 (1994), 67-94.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H N. J. A. Sloane, <a href="/A006949/b006949.txt">Table of n, a(n) for n = 0..20000</a>
%H Altug Alkan, <a href="https://doi.org//10.1155/2018/8517125">On a Generalization of Hofstadter's Q-Sequence: A Family of Chaotic Generational Structures</a>, Complexity (2018) Article ID 8517125.
%H Joseph Callaghan, John J. Chew III, and Stephen M. Tanny, <a href="http://dx.doi.org/10.1137/S0895480103421397">On the behavior of a family of meta-Fibonacci sequences</a>, SIAM Journal on Discrete Mathematics 18.4 (2005): 794-824. See Eq. (1.4). - _N. J. A. Sloane_, Apr 16 2014
%H A. Das, <a href="https://doi.org/10.46298/dmtcs.547">A combinatorial approach to the Tanny sequence</a>, Discr. Math. Theor. Comp. Sci. 13 (2) (2011) 97-108.
%H Jonathan H. B. Deane and Guido Gentile, <a href="https://arxiv.org/abs/2311.13854">A diluted version of the problem of the existence of the Hofstadter sequence</a>, arXiv:2311.13854 [math.NT], 2023.
%H C. Deugau and F. Ruskey, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL12/Ruskey/ruskey6.pdf">Complete k-ary Trees and Generalized Meta-Fibonacci Sequences</a>, J. Integer Seq., Vol. 12. [This is a later version than that in the GenMetaFib.html link]
%H C. Deugau and F. Ruskey, <a href="http://www.cs.uvic.ca/~ruskey/Publications/MetaFib/GenMetaFib.html">Complete k-ary Trees and Generalized Meta-Fibonacci Sequences</a>
%H Nathaniel D. Emerson, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL9/Emerson/emerson6.html">A Family of Meta-Fibonacci Sequences Defined by Variable-Order Recursions</a>, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.8.
%H Nathan Fox, <a href="https://arxiv.org/abs/2203.09340">Connecting Slow Solutions to Nested Recurrences with Linear Recurrent Sequences</a>, arXiv:2203.09340 [math.CO], 2022.
%H J. Grytczuk, <a href="http://dx.doi.org/10.1016/j.disc.2003.10.022">Another variation on Conway's recursive sequence</a>, Discr. Math. 282 (2004), 149-161.
%H B. Jackson and F. Ruskey, <a href="http://www.cs.uvic.ca/~ruskey/Publications/MetaFib/MetaFib.html">Meta-Fibonacci Sequences, Binary Trees and Extremal Compact Codes</a>
%H B. Jackson and F. Ruskey, <a href="https://doi.org/10.37236/1052">Meta-Fibonacci Sequences, Binary Trees and Extremal Compact Codes</a>, Electronic Journal of Combinatorics, 13 (2006), R26.
%H Warren Page (editor), <a href="http://www.jstor.org/stable/2686442">Media Highlights: A well-behaved cousin of the Hofstadter sequence</a>, The College Math. Jnl., 24 (1993), p. 105.
%H F. Ruskey and C. Deugau, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Ruskey/ruskey6.html">The Combinatorics of Certain k-ary Meta-Fibonacci Sequences</a>, JIS 12 (2009) 09.4.3.
%H S. M. Tanny, <a href="http://dx.doi.org/10.1016/0012-365X(92)90145-6">A well-behaved cousin of the Hofstadter sequence</a>, Discr. Math. 105 (1992), 227-239. [See Higham-Tanny 1993 for updates and corrections.]
%H <a href="/index/Ho#Hofstadter">Index entries for Hofstadter-type sequences</a>
%F a(n) = a(n-1) + 0 or 1 for n > 0 and lim_{n -> infinity} a(n)/n = 1/2. - Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Jun 27 2003
%F G.f.: z + z * Sum_{n >= 1} Product_{k=1..n} (z + z^(2^k)). - _Frank Ruskey_ and Chris Deugau (deugaucj(AT)uvic.ca)
%F For an efficient way to compute this sequence for large n, see A120511.
%p A006949 := proc(n) option remember: if n<3 then 1 else A006949(n-1-A006949(n-1))+A006949(n-2-A006949(n-2)) fi end;
%t a[0] = a[1] = a[2] = 1; a[n_] := a[n] = a[n - 1 - a[n - 1]] + a[n - 2 - a[n - 2]]; Table[a@ n, {n, 0, 75}] (* _Michael De Vlieger_, Mar 24 2017 *)
%o (PARI) { n=20; v=vector(n); for (i=1,n,v[i]=vector(2^(i-1))); v[1][1]=1; for (i=2,n, k=length(v[i-1]); for (j=1,k, v[i][j]=v[i-1][j]+1; v[i][j+k]=v[i-1][j]+2^(i-1))); c=vector(n); for (i=1,n, for (j=1,2^(i-1), if (v[i][j]<=n, c[v[i][j]]++))); c } \\ _Jon Perry_, Jan 01 2004
%o (Haskell)
%o a006949 n = a006949_list !! n
%o a006949_list = 1 : 1 : 1 : zipWith (+) xs (tail xs)
%o where xs = map a006949 $ zipWith (-) [1..] $ tail a006949_list
%o -- _Reinhard Zumkeller_, Apr 17 2014
%Y See also A120511. A244478, A244479, A240807, A240808, A244483 have the same recurrence but different initial conditions.
%Y Cf. A241235 (run lengths).
%K nonn
%O 0,4
%A _N. J. A. Sloane_, _Jeffrey Shallit_
%E More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Jun 27 2003
|
