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. 23

%I

%S 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,

%T 16,16,16,16,17,18,18,19,20,20,20,21,22,22,23,24,24,24,24,25,26,26,27,

%U 28,28,28,29,30,30,31,32,32,32,32,32,32,33,34,34,35,36,36,36,37

%N a(1) = a(2) = 1, a(n) = a(n - a(n-1)) + a(n-1 - a(n-2)) if n > 2.

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

%C Except for the first term, n occurs A001511(n) times. - _Franklin T. Adams-Watters_, Oct 22 2006

%D Sequence was proposed by Reg Allenby.

%D 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).

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

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

%H N. J. A. Sloane, <a href="/A046699/b046699.txt">Table of n, a(n) for n = 1..20000</a>

%H Altug Alkan, <a href="https://doi.org//10.1155/2018/8517125">On a Generalization of Hofstadter's Q-Sequence: A Family of Chaotic Generational Structures</a>, Complexity (2018) Article ID 8517125.

%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>

%H Joseph Callaghan, John J. Chew III, and Stephen M. Tanny, <a href="http://dx.doi.org/10.1137/S0895480103421397">On the behavior of a family of meta-Fibonacci sequences</a>, SIAM Journal on Discrete Mathematics 18.4 (2005): 794-824. See p. 794. - _N. J. A. Sloane_, Apr 16 2014

%H M. Celaya, F. Ruskey, <a href="http://arxiv.org/abs/1307.0153">Morphic Words and Nested Recurrence Relations</a>, arXiv preprint arXiv:1307.0153 [math.CO], 2013.

%H C. Deugau and F. Ruskey, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL12/Ruskey/ruskey6.pdf">Complete k-ary Trees and Generalized Meta-Fibonacci Sequences</a>, J. Integer Seq., Vol. 12. [This is a later version than that in the GenMetaFib.html link]

%H C. Deugau and F. Ruskey, <a href="http://www.cs.uvic.ca/~ruskey/Publications/MetaFib/GenMetaFib.html">Complete k-ary Trees and Generalized Meta-Fibonacci Sequences</a>

%H A. Erickson, A. Isgur, B. W. Jackson, F. Ruskey and S. M. Tanny, <a href="http://webhome.cs.uvic.ca/~ruskey/Publications/MetaFib/ConollyLikeMay14.pdf">Nested recurrence relations with Conolly-like solutions</a>, See Table 2.

%H Nathan Fox, <a href="https://arxiv.org/abs/1611.08244">A Slow Relative of Hofstadter's Q-Sequence</a>, arXiv:1611.08244 [math.NT], 2016.

%H Nathan Fox, <a href="https://vimeo.com/322291024">Trees, Fibonacci Numbers, and Nested Recurrences</a>, Rutgers University Experimental Math Seminar, Mar 07, 2019

%H Abraham Isgur, Mustazee Rahman, and Stephen Tanny, <a href="http://dx.doi.org/10.1007/s00026-013-0202-9">Solving non-homogeneous nested recursions using trees</a>, Annals of Combinatorics 17.4 (2013): 695-710. See p. 695. - _N. J. A. Sloane_, Apr 16 2014

%H A. Isgur, R. Lech, S. Moore, S. Tanny, Y. Verberne, and Y. Zhang, <a href="http://dx.doi.org/10.1137/15M1040505">Constructing New Families of Nested Recursions with Slow Solutions</a>, SIAM J. Discrete Math., 30(2), 2016, 1128-1147. (20 pages); DOI:10.1137/15M1040505.

%H B. Jackson and F. Ruskey, <a href="http://www.cs.uvic.ca/~ruskey/Publications/MetaFib/MetaFib.html">Meta-Fibonacci Sequences, Binary Trees and Extremal Compact Codes</a>

%H B. Jackson and F. Ruskey, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v13i1r26">Meta-Fibonacci Sequences, Binary Trees and Extremal Compact Codes</a>, Electronic Journal of Combinatorics, 13 (2006), #R26, 13 pages.

%H Oliver Kullmann and Xishun Zhao, <a href="http://arxiv.org/abs/1505.02318">Parameters for minimal unsatisfiability: Smarandache primitive numbers and full clauses</a>, arXiv preprint, arXiv:1505.02318 [cs.DM], 2015.

%H Ramin Naimi, Eric Sundberg, <a href="https://arxiv.org/abs/1902.02929">A Combinatorial Problem Solved by a Meta-Fibonacci Recurrence Relation</a>, arXiv:1902.02929 [math.CO], 2019.

%H <a href="/index/Ho#Hofstadter">Index entries for Hofstadter-type sequences</a>

%F 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

%F 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)

%F 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

%p 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)

%p 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

%t 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_ *)

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

%t 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 *)

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

%o (Haskell)

%o a046699 n = a046699_list !! (n-1)

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

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

%o -- _Reinhard Zumkeller_, Jan 02 2012

%o (Maxima)

%o a[1]:1$

%o a[2]:1$

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

%o makelist(a[n],n,2,60); /* _Martin Ettl_, Oct 29 2012 */

%o (Python)

%o from sympy import factorial

%o def a(n):

%o if n<3: return 1

%o s=1

%o while factorial(2*s)%(2**(n - 1))>0: s+=1

%o return s

%o print [a(n) for n in xrange(1, 101)] # _Indranil Ghosh_, Jun 11 2017, after _Benoit Cloitre_

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

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

%K nonn,nice

%O 1,3

%A _R. K. Guy_

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 19 00:55 EDT 2019. Contains 324217 sequences. (Running on oeis4.)