|
%I #141 Aug 26 2022 10:25:59
%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 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.
%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 and 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="https://cs.uwaterloo.ca/journals/JIS/VOL12/Ruskey/ruskey6.html">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 Nathan Fox, <a href="https://arxiv.org/abs/2203.09340">Connecting Slow Solutions to Nested Recurrences with Linear Recurrent Sequences</a>, arXiv:2203.09340 [math.CO], 2022.
%H The IMO Compendium, <a href="https://imomath.com/othercomp/Can/CanMO90.pdf">Problem 5</a>, 22nd Canadian Mathematical Olympiad 1990.
%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="https://doi.org/10.37236/1052">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 Thomas M. Lewis and Fabian Salinas, <a href="https://arxiv.org/abs/2109.07328">Optimal pebbling of complete binary trees and a meta-Fibonacci sequence</a>, arXiv:2109.07328 [math.CO], 2021.
%H Ramin Naimi and 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>.
%H <a href="/index/O#Olympiads">Index to sequences related to Olympiads</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
%F Conjecture: a(n+1) = a(n) + A215530(a(n) + n) for all n > 0. - _Velin Yanev_, Oct 17 2019
%F From _Bernard Schott_, Dec 03 2021: (Start)
%F a(n) <= a(n+1) <= a(n) +1.
%F For n > 1, if a(n) is odd, then a(n+1) = a(n) + 1.
%F a(2^n+1) = 2^(n-1) + 1 for n > 0.
%F Results coming from the 5th problem proposed during the 22nd Canadian Mathematical Olympiad in 1990 (link IMO Compendium and Doob reference). (End)
%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 range(1, 101)]) # _Indranil Ghosh_, Jun 11 2017, after _Benoit Cloitre_
%o (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
%Y Cf. A001511, A005185, A005187, A007843, A055938, A079559, A080578, A101925, A182105, A213714, A226222, A234016, A275363, A324473, A324475, A324477.
%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_
|
