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).
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).
Olivier Bodini, Antoine Genitrini, and Khaydar Nurligareev, Growing binary trees, ResearchGate (2026). See p. 14 (Eq. 9).
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 J. Disc. Math. 18.4 (2005): 794-824. See p. 794. - N. J. A. Sloane, Apr 16 2014
Marcel Celaya and Frank Ruskey, Morphic Words and Nested Recurrence Relations, arXiv preprint arXiv:1307.0153 [math.CO], 2013.
Chris Deugau and Frank Ruskey, Complete k-ary Trees and Generalized Meta-Fibonacci Sequences, J. Int. Seq. 12 (2009), Art. 09.4.3. [This is a later version than that in the GenMetaFib.html link]
Chris Deugau and Frank Ruskey, Complete k-ary Trees and Generalized Meta-Fibonacci Sequences
Alejandro Erickson, Abraham Isgur, Bradley W. Jackson, Frank Ruskey, and Stephen M. Tanny, Nested recurrence relations with Conolly-like solutions, (2010). 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.
Brad Jackson and Frank Ruskey, Meta-Fibonacci Sequences, Binary Trees and Extremal Compact Codes
Brad Jackson and Frank Ruskey, Meta-Fibonacci Sequences, Binary Trees and Extremal Compact Codes, Elect. J. Comb. 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.
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)
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)
# Alternative:
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 */
(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
(Python)
from itertools import count
def A046699(n):
if n == 1: return 1
c = 0
for k in count(2, 2):
c += (~k&k-1).bit_length()
if c+k+2 >= n:
return max(k, n-c-1) if n>2 else n-c # Chai Wah Wu, Feb 24 2026
(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
CROSSREFS
KEYWORD
nonn,nice
AUTHOR
STATUS
approved