A294566 a(n) is the smallest positive integer of length (distance from origin) n in the Cayley graph of the integers generated by all powers of 5.

1, 2, 3, 8, 13, 38, 63, 188, 313, 938, 1563, 4688, 7813, 23438, 39063, 117188, 195313, 585938, 976563, 2929688, 4882813, 14648438, 24414063, 73242188, 122070313, 366210938, 610351563, 1831054688, 3051757813, 9155273438, 15258789063, 45776367188, 76293945313

Offset

1,2

Links

Colin Barker, Table of n, a(n) for n = 1..1000

G. Bell, A. Lawson, N. Pritchard, and D. Yasaki, Locally infinite Cayley graphs of the integers, arXiv:1711.00809 [math.GT], 2017.

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

Formula

Let r,q satisfy the division algorithm so that n = q*2 + r. If r= 0, then a(n) = (5^q - 2*5^(q-1) + 1)/2. Otherwise, a(n) = ((2*r-1)*5^q + 1)/2. (Proved)

From Colin Barker, Nov 02 2017: (Start)

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

a(n) = a(n-1) + 5*a(n-2) - 5*a(n-3) for n > 3.

a(n) = (3*5^(n/2) + 5)/10 for n even.

a(n) = (5^((n-1)/2) + 1)/2 for n odd.

(End)

Example

The Cayley graph of the integers generated by the powers of 5 is a graph whose vertices are integers and an edge between integers whenever they differ by a power of 5. The length of an integer in this graph is its edge distance from 0.
For example, 1 = 5^0 and thus has length 1. 2 = 5^0 + 5^0 and thus has length 2. The same pattern holds for 3. But 4 = 5 - 5^0 and thus has length 2. It does not appear in the sequence because there is a smaller positive integer of length 2 (namely 2).
We can see the smallest integer of length 4 is 8 = 5^1 + 5^0 + 5^0 + 5^0. 8 cannot be written as a sum of 3 or fewer powers of 5.

Mathematica

LinearRecurrence[{1, 5, -5}, Range@ 3, 30] (* or *)
Rest@ CoefficientList[Series[x (1 + x - 4 x^2)/((1 - x) (1 - 5 x^2)), {x, 0, 30}], x] (* Michael De Vlieger, Nov 03 2017 *)

Prog

(PARI) Vec(x*(1 + x - 4*x^2) / ((1 - x)*(1 - 5*x^2)) + O(x^40)) \\ Colin Barker, Nov 02 2017

Crossrefs

Sequence in context: A151889 A366020 A294151 * A129873 A025575 A077055

Adjacent sequences: A294563 A294564 A294565 * A294567 A294568 A294569

Keyword

nonn,easy

Author

Austin Lawson, Nov 02 2017

Status

approved