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

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 June 24 08:22 EDT 2017. Contains 288697 sequences.