login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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)
10

%I M0230

%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 Higham, J.; Tanny, S. 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 Higham, Jeff and Tanny, Stephen, 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="http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/1320">A combinatorial approach to the Tanny sequence</a>, Discr. Math. Theor. Comp. Sci. 13 (2) (2011) 97-108

%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 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="http://www.combinatorics.org/Volume_13/Abstracts/v13i1r26.html">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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 23 04:23 EDT 2021. Contains 343199 sequences. (Running on oeis4.)