login
The OEIS is supported by the many generous donors 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. 25
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).

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)

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.

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)

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

(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

Cf. A001511, A005185, A005187, A007843, A055938, A079559, A080578, A101925, A182105, A213714, A226222, A234016, A275363, A324473, A324475, A324477.

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

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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 2 15:19 EDT 2022. Contains 357226 sequences. (Running on oeis4.)