login
This site is supported by donations to The OEIS 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
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; refs; listen; history; text; internal format)
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 A006949. - N. J. A. Sloane, Jul 03 2014

REFERENCES

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.

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.

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

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.

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, 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 * A194814 A055748 A284520

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

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 19 14:52 EST 2018. Contains 317352 sequences. (Running on oeis4.)