This site is supported by donations to The OEIS Foundation. 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. 23
 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). 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 Altug Alkan, On a Generalization of Hofstadter's Q-Sequence: A Family of Chaotic Generational Structures, Complexity (2018) Article ID 8517125. 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. Nathan Fox, Trees, Fibonacci Numbers, and Nested Recurrences, Rutgers University Experimental Math Seminar, Mar 07, 2019 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 A. Isgur, R. Lech, S. Moore, S. Tanny, Y. Verberne, and Y. Zhang, Constructing New Families of Nested Recursions with Slow Solutions, SIAM J. Discrete Math., 30(2), 2016, 1128-1147. (20 pages); DOI:10.1137/15M1040505. 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. Ramin Naimi, Eric Sundberg, A Combinatorial Problem Solved by a Meta-Fibonacci Recurrence Relation, arXiv:1902.02929 [math.CO], 2019. 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 = a = 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 = a = 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\$ a: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 */ (Python) from sympy import factorial def a(n):     if n<3: return 1     s=1     while factorial(2*s)%(2**(n - 1))>0: s+=1     return s print [a(n) for n in xrange(1, 101)] # Indranil Ghosh, Jun 11 2017, after Benoit Cloitre 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: A159481 A194206 A307482 * A239105 A302255 A218446 Adjacent sequences:  A046696 A046697 A046698 * A046700 A046701 A046702 KEYWORD nonn,nice AUTHOR 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
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified June 19 16:48 EDT 2019. Contains 324222 sequences. (Running on oeis4.)