A006949 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. (Formerly M0230)

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

Offset

0,4

Comments

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

Ignoring first term, this is the Meta-Fibonacci sequence for s=1. - Frank Ruskey and Chris Deugau (deugaucj(AT)uvic.ca)

Comment from N. J. A. Sloane, Jul 03 2014: (Start)

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

X Y Z

3 1 0 A244483

2 1 0 A240808

2 1 1 A240807

2 0 2 A244478

1 0 2 A240808 again

1 1 1 A006949 (this sequence).

Most other initial values do not produce a nontrivial sequence. (End)

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

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

References

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.

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.

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

Links

N. J. A. Sloane, Table of n, a(n) for n = 0..20000

Altug Alkan, On a Generalization of Hofstadter's Q-Sequence: A Family of Chaotic Generational Structures, Complexity (2018) Article ID 8517125.

Joseph Callaghan, John J. Chew III, and Stephen M. Tanny, On the behavior of a family of meta-Fibonacci sequences, SIAM Journal on Discrete Mathematics 18.4 (2005): 794-824. See Eq. (1.4). - N. J. A. Sloane, Apr 16 2014

A. Das, A combinatorial approach to the Tanny sequence, Discr. Math. Theor. Comp. Sci. 13 (2) (2011) 97-108.

Jonathan H. B. Deane and Guido Gentile, A diluted version of the problem of the existence of the Hofstadter sequence, arXiv:2311.13854 [math.NT], 2023.

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

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.

Nathan Fox, Connecting Slow Solutions to Nested Recurrences with Linear Recurrent Sequences, arXiv:2203.09340 [math.CO], 2022.

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

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

Warren Page (editor), Media Highlights: A well-behaved cousin of the Hofstadter sequence, The College Math. Jnl., 24 (1993), p. 105.

F. Ruskey and C. Deugau, The Combinatorics of Certain k-ary Meta-Fibonacci Sequences, JIS 12 (2009) 09.4.3.

S. M. Tanny, A well-behaved cousin of the Hofstadter sequence, Discr. Math. 105 (1992), 227-239. [See Higham-Tanny 1993 for updates and corrections.]

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. - Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Jun 27 2003

G.f.: z + z * Sum_{n >= 1} Product_{k=1..n} (z + z^(2^k)). - Frank Ruskey and Chris Deugau (deugaucj(AT)uvic.ca)

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

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;

Mathematica

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

Prog

(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
(Haskell)
a006949 n = a006949_list !! n
a006949_list = 1 : 1 : 1 : zipWith (+) xs (tail xs)
   where xs = map a006949 $ zipWith (-) [1..] $ tail a006949_list
-- Reinhard Zumkeller, Apr 17 2014

Crossrefs

See also A120511. A244478, A244479, A240807, A240808, A244483 have the same recurrence but different initial conditions.

Cf. A241235 (run lengths).

Sequence in context: A072000 A157477 A248801 * A359536 A194814 A055748

Adjacent sequences: A006946 A006947 A006948 * A006950 A006951 A006952

Keyword

nonn

Author

N. J. A. Sloane, Jeffrey Shallit

Extensions

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

Status

approved