0,4

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

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)

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.

J. Grytczuk, Another variation on Conway's recursive sequence, Discr. Math. 282 (2004), 149-161.

B. Jackson and F. Ruskey, Meta-Fibonacci Sequences, Binary Trees and Extremal Compact Codes, Electronic Journal of Combinatorics, 13 (2006), #R26, 13 pages.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

S. M. Tanny, A well-behaved cousin of the Hofstadter sequence, Discr. Math. 105 (1992), 227-239.

See also Two-Year College Math. Jnl., 24 (1993), p. 105.

C. Deugau and F. Ruskey, Complete k-ary Trees and Generalized Meta-Fibonacci Sequences, J. Integer Seq., Vol. 12. [This is a later version than that in the GenMetaFib.html link]

C. Deugau and F. Ruskey, Complete k-ary Trees and Generalized Meta-Fibonacci Sequences

B. Jackson and F. Ruskey, Meta-Fibonacci Sequences, Binary Trees and Extremal Compact Codes

Index entries for Hofstadter-type sequences

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

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)

For an efficient way to compute this sequence for large n, see A120511.

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;

(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)

See also A120511.

Sequence in context: A087816 A072000 A157477 this_sequence A055748 A090702 A029124

Adjacent sequences: A006946 A006947 A006948 this_sequence A006950 A006951 A006952

nonn

N. J. A. Sloane (njas(AT)research.att.com), Jeffrey Shallit

More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Jun 27 2003