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
Examples
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.
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).
Programs
-
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 *) -
PARI
Vec(x*(1 + x - 4*x^2) / ((1 - x)*(1 - 5*x^2)) + O(x^40)) \\ Colin Barker, Nov 02 2017
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)