|
Search: id:A006949
|
|
|
| A006949 |
|
A well-behaved cousin of the Hofstadter sequence.
(Formerly M0230)
|
|
+0
3
|
|
| 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, 15, 16, 16, 16, 16, 16, 16, 17, 18, 18, 19, 20, 20, 20, 21, 22, 22, 23, 24, 24, 24, 24, 25, 26, 26, 27, 28, 28, 28, 29, 30, 30, 31, 32, 32, 32, 32, 32, 32, 32, 33, 34, 34, 35, 36, 36
(list; graph; listen)
|
|
|
OFFSET
|
0,4
|
|
|
COMMENT
|
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)
|
|
REFERENCES
|
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.
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.
|
|
LINKS
|
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
|
|
FORMULA
|
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)
|
|
MAPLE
|
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;
|
|
PROGRAM
|
(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)
|
|
CROSSREFS
|
Sequence in context: A029131 A087816 A072000 this_sequence A055748 A090702 A029124
Adjacent sequences: A006946 A006947 A006948 this_sequence A006950 A006951 A006952
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
njas, Jeffrey Shallit
|
|
EXTENSIONS
|
More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Jun 27 2003
|
|
|
Search completed in 0.002 seconds
|
