A046699 a(1) = a(2) = 1, a(n) = a(n - a(n-1)) + a(n-1 - a(n-2)) if n > 2.
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
Offset: 1
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).
- Michael Doob, The Canadian Mathematical Olympiad & L'Olympiade Mathématique du Canada 1969-1993, Canadian Mathematical Society & Société Mathématique du Canada, Problem 5, 1990, pp. 212-213, 1993.
- 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)
- Stephen M. Buckley, Wiring switches to more light bulbs, arXiv:2410.02460 [math.CO], 2024. See pp. 3, 12, 22.
- 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 and 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.
- Nathan Fox, Connecting Slow Solutions to Nested Recurrences with Linear Recurrent Sequences, arXiv:2203.09340 [math.CO], 2022.
- The IMO Compendium, Problem 5, 22nd Canadian Mathematical Olympiad 1990.
- 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.
- Thomas M. Lewis and Fabian Salinas, Optimal pebbling of complete binary trees and a meta-Fibonacci sequence, arXiv:2109.07328 [math.CO], 2021.
- Ramin Naimi and Eric Sundberg, A Combinatorial Problem Solved by a Meta-Fibonacci Recurrence Relation, arXiv:1902.02929 [math.CO], 2019.
- Index entries for Hofstadter-type sequences.
- Index to sequences related to Olympiads.
Crossrefs
Programs
-
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
-
Magma
[ n le 2 select 1 else Self(n - Self(n-1)) + Self(n-1 -Self(n-2)):n in [1..80]]; // Marius A. Burtea, Oct 17 2019
-
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 *) -
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 */
-
PARI
a(n)=if(n<0,1,s=1;while((2*s)!%2^(n-1)>0,s++);s) \\ Benoit Cloitre, Jan 19 2007
-
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 range(1, 101)]) # Indranil Ghosh, Jun 11 2017, after Benoit Cloitre
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
Conjecture: a(n+1) = a(n) + A215530(a(n) + n) for all n > 0. - Velin Yanev, Oct 17 2019
From Bernard Schott, Dec 03 2021: (Start)
a(n) <= a(n+1) <= a(n) +1.
For n > 1, if a(n) is odd, then a(n+1) = a(n) + 1.
a(2^n+1) = 2^(n-1) + 1 for n > 0.
Results coming from the 5th problem proposed during the 22nd Canadian Mathematical Olympiad in 1990 (link IMO Compendium and Doob reference). (End)
Comments