cp's OEIS Frontend

A014217 a(n) = floor(phi^n), where phi = (1+sqrt(5))/2 is the golden ratio.

%I A014217 #197 Apr 03 2025 23:06:58
%S A014217 1,1,2,4,6,11,17,29,46,76,122,199,321,521,842,1364,2206,3571,5777,
%T A014217 9349,15126,24476,39602,64079,103681,167761,271442,439204,710646,
%U A014217 1149851,1860497,3010349,4870846,7881196,12752042,20633239,33385281,54018521,87403802
%N A014217 a(n) = floor(phi^n), where phi = (1+sqrt(5))/2 is the golden ratio.
%C A014217 a(n) = floor(lim_{k->oo} Fibonacci(k)/Fibonacci(k-n)). - _Jon Perry_, Jun 10 2003
%C A014217 For n > 1, a(n) is the maximum element in the continued fraction for A000045(n)*phi. - _Benoit Cloitre_, Jun 19 2005
%C A014217 a(n) is also the curvature (rounded down) of the circle inscribed in the n-th kite arranged in a spiral, starting with a unit circle, as shown in the illustration in the links section. - _Kival Ngaokrajang_, Aug 29 2013
%C A014217 a(n) is the n-th Lucas number (A000032) if n is odd, and a(n) is the n-th Lucas number minus 1 if n is even. (Mario Catalani's formula below expresses this fact.) This is related to the fact that the powers of phi approach the values of the Lucas numbers, the odd powers from above and the even powers from below. - _Geoffrey Caveney_, Apr 18 2014
%C A014217 a(n) is the sum of the last summands over all Arndt compositions of n (see the Checa link). - _Daniel Checa_, Dec 25 2023
%C A014217 a(n) is the number of (saturated or unsaturated) substituted N-heterocycles in chemistry (N = nitrogen). That means the number of matchings in a cycle graph when the two maximum matchings in every cycle with an even number of vertices are indistinguishable (because the corresponding resonance structures in the molecule are equivalent). - _Stefan Schuster_, Mar 20 2025
%H A014217 Alois P. Heinz, <a href="/A014217/b014217.txt">Table of n, a(n) for n = 0..4784</a> (first 301 terms from T. D. Noe)
%H A014217 Mohammad K. Azarian, <a href="http://www.math-cs.ucmo.edu/~mjms/1998.3/prob.ps">Problem 123</a>, Missouri Journal of Mathematical Sciences, Vol. 10, No. 3, Fall 1998, p. 176.  <a href="http://www.math-cs.ucmo.edu/~mjms/2000.1/soln.ps">Solution</a> published in Vol. 12, No. 1, Winter 2000, pp. 61-62.
%H A014217 Daniel F. Checa, <a href="https://github.com/dfcheca/Arndt-Compositions">Arndt Compositions: Connections with Fibonacci Numbers, Statistics, and Generalizations</a>, 2023. p. 29.
%H A014217 Daniel F. Checa and José L. Ramírez, <a href="http://math.colgate.edu/~integers/y35/y35.pdf">Arndt Compositions: A Generating Functions Approach</a>, Integers (2024) Vol. 24, A35. See p. 14.
%H A014217 G. Harman, <a href="http://at.yorku.ca/c/a/d/x/39.htm">One hundred years of normal numbers</a>
%H A014217 Kival Ngaokrajang, <a href="/A014217/a014217.pdf">Illustration for n = 0..7</a>
%H A014217 Stefan Schuster and Tatjana Malycheva, <a href="https://arxiv.org/abs/2309.02343">Enumeration of saturated and unsaturated substituted N-heterocycles</a>, arXiv:2309.02343 [q-bio.BM], 2023.
%H A014217 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (1,2,-1,-1).
%F A014217 a(n) = a(n-1) + 2*a(n-2) - a(n-3) - a(n-4).
%F A014217 a(n) = a(n-1) + a(n-2) + (1-(-1)^n)/2 = a(n-1) + a(n-2) + A000035(n).
%F A014217 a(n) = A000032(n) - (1 + (-1)^n)/2. - Mario Catalani (mario.catalani(AT)unito.it), Jan 17 2003
%F A014217 G.f.: (1-x^2+x^3)/((1+x)*(1-x)*(1-x-x^2)). - _R. J. Mathar_, Sep 06 2008
%F A014217 a(2n-1) = (Fibonacci(4n+1)-2)/Fibonacci(2n+2). - _Gary Detlefs_, Feb 16 2011
%F A014217 a(n) = floor(Fibonacci(2n+3)/Fibonacci(n+3)). - _Gary Detlefs_, Feb 28 2011
%F A014217 a(2n) = Fibonacci(2*n-1) + Fibonacci(2*n+1) - 1. - _Gary Detlefs_, Mar 10 2011
%F A014217 a(n+2*k) - a(n) = A203976(k)*A000032(n+k) if k odd, a(n+2*k) - a(n) = A203976(k)*A000045(n+k) if k even, for k > 0. - _Paul Curtz_, Jun 05 2013
%F A014217 a(n) = A052952(n) - A052952(n-2) + A052952(n-3). - _R. J. Mathar_, Jun 13 2013
%F A014217 a(n+6) - a(n-6) = 40*A000045(n), case k=6 of my formula above. - _Paul Curtz_, Jun 13 2013
%F A014217 From _Paul Curtz_, Jun 17 2013: (Start)
%F A014217 a(n-3) + a(n+3) = A153382(n).
%F A014217 a(n-1) + a(n+2) = A022319(n). (End)
%F A014217 For k > 0, a(2k) = A169985(2k)-1 and a(2k+1) = A169985(2k+1) (which is equivalent to Catalani's 2003 formula). - _Danny Rorabaugh_, Apr 15 2015
%F A014217 a(n) = ((-1)^(1+n)-1)/2 + ((1-sqrt(5))/2)^n + ((1+sqrt(5))/2)^n. - _Colin Barker_, Nov 05 2017
%F A014217 a(n) = floor(2*sinh(n*arccsch(2))). - _Federico Provvedi_, Feb 23 2022
%F A014217 E.g.f.: 2*exp(x/2)*cosh(sqrt(5)*x/2) - cosh(x). - _Stefano Spezia_, Jul 26 2022
%F A014217 a(n) = floor(Fibonacci(n)*phi) + Fibonacci(n-1) = A074331(n) + A000045(n-1) = A052952(n-1) + A000045(n-1). This is the case k=1 of the formula (also found in A128440): floor(k * phi^n) = floor(Fibonacci(n)*k*phi) + Fibonacci(n-1) * k. - _Chunqing Liu_, Oct 03 2023
%p A014217 A014217 := proc(n)
%p A014217     option remember;
%p A014217     if n <= 3 then
%p A014217         op(n+1,[1,1,2,4]) ;
%p A014217     else
%p A014217         procname(n-1)+2*procname(n-2)-procname(n-3)-procname(n-4) ;
%p A014217     end if;
%p A014217 end proc: # _R. J. Mathar_, Jun 23 2013
%p A014217 #
%p A014217 a:= n-> (<<0|1|0|0>, <0|0|1|0>, <0|0|0|1>, <-1|-1|2|1>>^n. <<1, 1, 2, 4>>)[1, 1]:
%p A014217 seq(a(n), n=0..40);  # _Alois P. Heinz_, Oct 12 2017
%t A014217 Table[Floor[GoldenRatio^n], {n, 0, 36}] (* _Vladimir Joseph Stephan Orlovsky_, Dec 12 2008 *)
%t A014217 LinearRecurrence[{1, 2, -1, -1}, {1, 1, 2, 4}, 40] (* _Jean-François Alcover_, Nov 05 2017 *)
%o A014217 (PARI) my(x='x+O('x^44)); Vec((1-x^2+x^3)/((1+x)*(1-x)*(1-x-x^2))) \\ _Joerg Arndt_, Jul 10 2023
%o A014217 (Magma) [Floor( ((1+Sqrt(5))/2)^n ): n in [0..100]]; // _Vincenzo Librandi_, Apr 16 2011
%o A014217 (Haskell)
%o A014217 a014217 n = a014217_list !! n
%o A014217 a014217_list = 1 : 1 : zipWith (+)
%o A014217    a000035_list (zipWith (+) a014217_list $ tail a014217_list)
%o A014217 -- _Reinhard Zumkeller_, Jan 06 2012
%o A014217 (Sage) [floor(golden_ratio^n) for n in range(37)] # _Danny Rorabaugh_, Apr 19 2015
%o A014217 (Python)
%o A014217 from sympy import floor, sqrt
%o A014217 def A014217(n): return floor(((1+sqrt(5))/2)**n) # _Chai Wah Wu_, Dec 17 2021
%Y A014217 Cf. A000032, A000045, A001622, A020956, A022319, A052952, A057146, A062114, A128440, A153382, A169985, A169986, A203976, A226328.
%Y A014217 First differences give A181716.
%K A014217 nonn,easy,nice
%O A014217 0,3
%A A014217 _Clark Kimberling_
%E A014217 Corrected by _T. D. Noe_, Nov 09 2006
%E A014217 Edited by _N. J. A. Sloane_, Aug 29 2008 at the suggestion of _R. J. Mathar_