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

Author

N. J. A. Sloane, Sep 26 2010

Keywords

• nonn
• easy

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

Examples

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

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

Crossrefs

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

Cf. A000126, A000296, A001610.

Programs

GAP

Concatenation([1,2], List([2..40], n-> Lucas(1,-1,n)[2] )); # G. C. Greubel, Jul 09 2019

Magma

[Round(Sqrt(Fibonacci(2*n) + 2*Fibonacci(2*n-1))): n in [0..40]]; // Vincenzo Librandi, Apr 16 2015

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

PARI

my(x='x+O('x^40)); Vec((1+x-x^3)/(1-x-x^2)) \\ G. C. Greubel, Feb 13 2019

Python

from gmpy2 import isqrt, fib2
def A169985(n): return int((m:=isqrt(k:=(lambda x:(x[1]<<1)+x[0])(fib2(n<<1))))+(k-m*(m+1)>=1)) # Chai Wah Wu, Jun 19 2024

Sage

[round(golden_ratio^n) for n in range(40)] # Danny Rorabaugh, Apr 16 2015

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