A169985 Round phi^n to the nearest integer.

1, 2, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, 9349, 15127, 24476, 39603, 64079, 103682, 167761, 271443, 439204, 710647, 1149851, 1860498, 3010349, 4870847, 7881196, 12752043, 20633239, 33385282, 54018521, 87403803

Offset

0,2

Comments

Phi = (1+sqrt(5))/2, see A001622.

a(n) is the number of subsets of {1,2,...,n} with no two consecutive elements where n and 1 are considered to be consecutive. - Geoffrey Critzer, Sep 23 2013

Equals the Lucas sequence beginning at 1 (A000204) with 2 inserted between 1 and 3.

The Lucas sequence beginning at 2 (A000032) can be written as L(n) = phi^n + (-1/phi)^n. Since |(-1/phi)^n|<1/2 for n>1, this sequence is {L(n)} (with the first two terms switched). As a consequence, for n>1: a(n) is obtained by rounding phi^n up for even n and down for odd n; a(n) is also the nearest integer to 1/|phi^n - a(n)|. - Danny Rorabaugh, Apr 15 2015

Links

Danny Rorabaugh, Table of n, a(n) for n = 0..4000

John Machacek and George D. Nasr, Transversal and Paving Positroids, arXiv:2401.02053 [math.CO], 2024. See p. 23.

Shaoxiong (Steven) Yuan, Generalized Identities of Certain Continued Fractions, arXiv:1907.12459 [math.NT], 2019.

Index entries for linear recurrences with constant coefficients, signature (1,1).

Formula

O.g.f.: (1 + x - x^3)/(1 - x - x^2). - Geoffrey Critzer, Sep 23 2013

a(n) = round(sqrt(F(2n) + 2*F(2n-1))), for n >= 0, allowing F(-1) = 1. Also phi^n -> sqrt(F(2n) + 2*F(2n-1)), within < 0.02% by n = 4, therefore converging rapidly. - Richard R. Forberg, Jun 23 2014

For k > 0, a(2k) = A169986(2k) and a(2k+1) = A014217(2k+1). - Danny Rorabaugh, Apr 15 2015

For n > 1, a(n) = A001610(n - 1) + 1. - Gus Wiseman, Feb 12 2019

a(n) = A000032(n) for n>=2. - G. C. Greubel, Jul 09 2019

Example

a(4) = 7 because we have: {}, {1}, {2}, {3}, {4}, {1,3}, {2,4}. - Geoffrey Critzer, Sep 23 2013

Mathematica

nn=34; CoefficientList[Series[(1+x-x^3)/(1-x-x^2), {x, 0, nn}], x] (* Geoffrey Critzer, Sep 23 2013 *)
Round[GoldenRatio^Range[0, 40]] (* Harvey P. Dale, Jul 13 2014 *)
Table[If[n<=1, n+1, LucasL[n]], {n, 0, 40}] (* G. C. Greubel, Jul 09 2019 *)

Prog

(Magma) [Round(Sqrt(Fibonacci(2*n) + 2*Fibonacci(2*n-1))): n in [0..40]]; // Vincenzo Librandi, Apr 16 2015
(Sage) [round(golden_ratio^n) for n in range(40)] # Danny Rorabaugh, Apr 16 2015
(PARI) my(x='x+O('x^40)); Vec((1+x-x^3)/(1-x-x^2)) \\ G. C. Greubel, Feb 13 2019
(GAP) Concatenation([1, 2], List([2..40], n-> Lucas(1, -1, n)[2] )); # G. C. Greubel, Jul 09 2019

Crossrefs

Cf. A000032, A000045, A000204, A001622, A014217, A169986.

Cf. A000126, A000296, A001610.

Sequence in context: A222332 A222333 A080023 * A254729 A293544 A080074

Adjacent sequences: A169982 A169983 A169984 * A169986 A169987 A169988

Keyword

nonn,easy

Author

N. J. A. Sloane, Sep 26 2010

Status

approved