A254729 Number of numbers j + k*sqrt(2) of length n, where the length is the least number of steps to reach 0, the allowable steps being x -> x + 1 and x -> x*sqrt(2).

1, 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,3

Comments

See the MathOverflow link for a proof that the sequence coincides with the Lucas sequence, A000032, beginning at 4.

Therefore also the same as A080023 (beginning at 2). - Georg Fischer, Oct 09 2018

Links

Clark Kimberling, Table of n, a(n) for n = 0..1000

MathOverflow, A possibly surprising appearance of Lucas numbers

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

Formula

a(n) = a(n-1) + a(n-2) for n >= 6.

G.f.: (-1 + x^4)/(-1 + x + x^2).

Example

One can view the minimal paths in a tree having generation g(0) = {0} followed by generations g(1) = {1}, g(2) = {2, sqrt(2)}, g(3) = {3, 2*sqrt(2), 1+sqrt(2)}, and so on. Duplicates are removed as they occur. Also, a(n) = |g(n)| for n >= 0.

Mathematica

t = NestList[DeleteDuplicates[Flatten[Map[{# + {0, 1}, {Last[#], 2*First[#]}} &, #], 1]] &, {{0, 0}}, 25] ; s[0] = t[[1]]; s[n_] := s[n] = Union[t[[n + 1]], s[n - 1]]; g[n_] := Complement[s[n], s[n - 1]]; g[0] = {{0, 0}}; Table[Length[g[z]], {z, 0, 25}]
CoefficientList[Series[(-1 + x^4)/(-1 + x + x^2), {x, 0, 39}], x] (* Robert G. Wilson v, Feb 28 2015 *)

Prog

(PARI) x='x+O('x^40); Vec((1-x^4)/(1-x-x^2)) \\ G. C. Greubel, Sep 30 2018
(Magma) m:=40; R<x>:=PowerSeriesRing(Integers(), m); Coefficients(R!((1-x^4)/(1-x-x^2))); // G. C. Greubel, Sep 30 2018

Crossrefs

Cf. A252864.

Essentially the same as A000032, A169985 and A080023.

Sequence in context: A222333 A080023 A169985 * A293544 A080074 A317767

Adjacent sequences: A254726 A254727 A254728 * A254730 A254731 A254732

Keyword

nonn,easy

Author

Clark Kimberling, Feb 06 2015

Status

approved