login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A046699 a(1) = a(2) = 1, a(n) = a(n - a(n-1)) + a(n-1 - a(n-2)) if n > 2. 17
1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 6, 7, 8, 8, 8, 8, 9, 10, 10, 11, 12, 12, 12, 13, 14, 14, 15, 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, 33, 34, 34, 35, 36, 36, 36, 37 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

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

Except for the first term, n occurs A001511(n) times. - Franklin T. Adams-Watters, Oct 22 2006

REFERENCES

Sequence was proposed by Reg Allenby.

B. W. Conolly, "Meta-Fibonacci sequences," in S. Vajda, editor, Fibonacci and Lucas Numbers and the Golden Section. Halstead Press, NY, 1989, pp. 127-138. See Eq. (2). - N. J. A. Sloane, Apr 16 2014

S. Vajda, Fibonacci and Lucas Numbers and the Golden Section, Wiley, 1989, see p. 129.

S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 129.

LINKS

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

Joerg Arndt, Matters Computational (The Fxtbook)

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 p. 794. - N. J. A. Sloane, Apr 16 2014

M. Celaya, F. Ruskey, Morphic Words and Nested Recurrence Relations, arXiv preprint arXiv:1307.0153 [math.CO], 2013.

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

A. Erickson, A. Isgur, B. W. Jackson, F. Ruskey and S. M. Tanny, Nested recurrence relations with Conolly-like solutions, See Table 2.

Nathan Fox, A Slow Relative of Hofstadter's Q-Sequence, arXiv:1611.08244 [math.NT], 2016.

Abraham Isgur, Mustazee Rahman, and Stephen Tanny, Solving non-homogeneous nested recursions using trees, Annals of Combinatorics 17.4 (2013): 695-710. See p. 695. - N. J. A. Sloane, Apr 16 2014

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, 13 pages.

Oliver Kullmann and Xishun Zhao, Parameters for minimal unsatisfiability: Smarandache primitive numbers and full clauses, arXiv preprint, arXiv:1505.02318 [cs.DM], 2015.

Index entries for Hofstadter-type sequences

FORMULA

First differences seem to be A079559. - Vladeta Jovovic, Nov 30 2003. This is correct and not too hard to prove, giving the generating function x + x^2(1+x)(1+x^3)(1+x^7)(1+x^15).../(1-x). - Paul Boddington, Jul 30 2004

G.f. x + x^2/(1-x) * Product_{n=1}^{infinity} (1 + x^(2^n-1)). - Frank Ruskey and Chris Deugau (deugaucj(AT)uvic.ca)

For n>=1, a(n)=w(n-1) where w(n) is the least k such that 2^n divides (2k)!. - Benoit Cloitre, Jan 19 2007

MAPLE

a := proc(n) option remember; if n <= 1 then return 1 end if; if n <= 2 then return 2 end if; return add(a(n - i + 1 - a(n - i)), i = 1 .. 2) end proc # Frank Ruskey and Chris Deugau (deugaucj(AT)uvic.ca)

a := proc(n) option remember; if n <= 2 then 1 else a(n - a(n-1)) + a(n-1 - a(n-2)); fi; end; # N. J. A. Sloane, Apr 16 2014

MATHEMATICA

a[n_] := (k = 1; While[ !Divisible[(2*++k)!, 2^(n-1)]]; k); a[1] = a[2] = 1; Table[a[n], {n, 1, 72}] (* Jean-Fran├žois Alcover, Oct 06 2011, after Benoit Cloitre *)

CoefficientList[ Series[1 + x/(1 - x)*Product[1 + x^(2^n - 1), {n, 6}], {x, 0, 80}], x] (* or *)

a[1] = a[2] = 1; a[n_] := a[n] = a[n - a[n - 1]] + a[n - 1 - a[n - 2]]; Array[a, 80] (* Robert G. Wilson v, Sep 08 2014 *)

PROG

(PARI) a(n)=if(n<0, 1, s=1; while((2*s)!%2^(n-1)>0, s++); s) \\ Benoit Cloitre, Jan 19 2007

(Haskell)

a046699 n = a046699_list !! (n-1)

a046699_list = 1 : 1 : zipWith (+) zs (tail zs) where

   zs = map a046699 $ zipWith (-) [2..] a046699_list

-- Reinhard Zumkeller, Jan 02 2012

(Maxima)

a[1]:1$

a[2]:1$

a[n]:=a[n-a[n-1]]+a[n-1-a[n-2]]$

makelist(a[n], n, 2, 60); /* Martin Ettl, Oct 29 2012 */

CROSSREFS

Cf. A001511, A005185, A079559, A182105, A226222.

Callaghan et al. (2005)'s sequences T_{0,k}(n) for k=1 through 7 are A000012, A046699, A046702, A240835, A241154, A241155, A240830.

Sequence in context: A269990 A159481 A194206 * A239105 A218446 A102548

Adjacent sequences:  A046696 A046697 A046698 * A046700 A046701 A046702

KEYWORD

nonn,nice

AUTHOR

R. K. Guy

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 March 25 11:34 EDT 2017. Contains 284076 sequences.