|
|
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, 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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
See the MathOverflow link for a proof that the sequence coincides with the Lucas sequence, A000032, beginning at 4.
|
|
LINKS
|
|
|
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
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|