%I A006949 M0230
%S A006949 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 A006949 15,16,16,16,16,16,16,17,18,18,19,20,20,20,21,22,22,23,24,24,24,24,25,
%U A006949 26,26,27,28,28,28,29,30,30,31,32,32,32,32,32,32,32,33,34,34,35,36,36
%N A006949 A well-behaved cousin of the Hofstadter sequence.
%C A006949 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 
               (perry(AT)globalnet.co.uk), Jan 01 2004
%C A006949 Ignoring first term, this is the Meta-Fibonacci sequence for s=1. - Frank 
               Ruskey (http://www.cs.uvic.ca/~ruskey/) and Chris Deugau (deugaucj(AT)uvic.ca)
%D A006949 Nathaniel D. Emerson, A Family of Meta-Fibonacci Sequences Defined by 
               Variable-Order Recursions, Journal of Integer Sequences, Vol. 9 (2006), 
               Article 06.1.8.
%D A006949 J. Grytczuk, Another variation on Conway's recursive sequence, Discr. 
               Math. 282 (2004), 149-161.
%D A006949 B. Jackson and F. Ruskey, Meta-Fibonacci Sequences, Binary Trees and 
               Extremal Compact Codes, Electronic Journal of Combinatorics, 13 (2006), 
               #R26, 13 pages.
%D A006949 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%D A006949 S. M. Tanny, A well-behaved cousin of the Hofstadter sequence, Discr. 
               Math. 105 (1992), 227-239.
%D A006949 See also Two-Year College Math. Jnl., 24 (1993), p. 105.
%H A006949 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 A006949 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 A006949 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 A006949 <a href="Sindx_Ho.html#Hofstadter">Index entries for Hofstadter-type 
               sequences</a>
%F A006949 a(n) = a(n-1) + 0 or 1 for n>0 and lim n ->infinity a(n)/n = 1/2. Recurrence: 
               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. - 
               Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Jun 27 2003
%F A006949 g.f.: z + z * sum(prod(z + z^(2^k),k=1..n),n >= 1) - Frank Ruskey (http:/
               /www.cs.uvic.ca/~ruskey/) and Chris Deugau (deugaucj(AT)uvic.ca)
%F A006949 For an efficient way to compute this sequence for large n, see A120511.
%p A006949 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;
%o A006949 (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)
%Y A006949 See also A120511.
%Y A006949 Sequence in context: A087816 A072000 A157477 this_sequence A055748 A090702 
               A029124
%Y A006949 Adjacent sequences: A006946 A006947 A006948 this_sequence A006950 A006951 
               A006952
%K A006949 nonn
%O A006949 0,4
%A A006949 N. J. A. Sloane (njas(AT)research.att.com), Jeffrey Shallit
%E A006949 More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Jun 
               27 2003