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

Author

Clark Kimberling, Feb 06 2015

Keywords

• nonn
• easy

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

Examples

			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.
		

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

Crossrefs

Cf. A000032, A080023, A169985, A252864.

Programs

Magma

m:=40; R:=PowerSeriesRing(Integers(), m); Coefficients(R!((1-x^4)/(1-x-x^2))); // G. C. Greubel, Sep 30 2018

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

PARI

x='x+O('x^40); Vec((1-x^4)/(1-x-x^2)) \\ G. C. Greubel, Sep 30 2018

Formula

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

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