login
A371880
Smallest number reachable starting from 1 and taking n steps either doubling or doubling+reversing.
2
1, 2, 4, 8, 16, 23, 46, 29, 58, 71, 34, 68, 37, 47, 49, 89, 79, 59, 19, 38, 67, 35, 7, 14, 28, 56, 13, 26, 25, 5, 1, 2, 4, 8, 16, 23, 46, 29, 58, 17, 34, 68, 37, 47, 49, 89, 79, 59, 19, 38, 67, 35, 7, 14, 28, 56, 13, 26, 25, 5, 1, 2, 4, 8, 16, 23, 46, 29, 58, 17
OFFSET
0,2
COMMENTS
At each step you are allowed to either double x -> 2*x or double and reverse x -> R(2*x), where R(x) = A004086(x) is decimal digit reversal.
From Michael S. Branicky, Apr 14 2024: (Start)
Since a(30) = 1 = a(0), a(n) <= a(n-30) for n >= 30. a(39) <= 17 < a(9) = 71 is the first term that strictly lowers the bound. Is it eventually periodic?
Under the map, a term k has preimage k/2 if k is even plus terms of the form R(k)*10^i/2 for i > 1 and for i=0 if R(k) is even. (End)
The condition above implies a(i+30k) is nonincreasing for k >= 0 for all i in 0..29, hence it is periodic (with period being a factor of 30). When does the periodic part of the sequence begin? - Bryle Morga, Apr 15 2024
From David A. Corneth, Apr 15 2024: (Start)
a(n) == 2^n (mod 9).
Because of this, all values 1 <= a(n) <= 9 have a(n + 30*k) = a(n). That is a(30*k) = 1, a(30*k + 1) = 2, a(30*k + 2) = 4, a(30*k + 3) = 8, a(30*k + 22) = 7, a(30*k + 29) = 5, for k >= 0. (End)
Ultimately periodic sequence of period 30 with a(k+30)=a(k) for k != 9. - David Wilson, Apr 19 2024
FORMULA
a(n) = f(1, n) where f(k, 0) = k and f(k, n) = min(f(2*k, n-1), f(R(2*k), n-1)).
a(30k) = 1 for k >= 0. - Michael S. Branicky, Apr 14 2024
a(9) = 71. For k != 9, a(k) is the minimum of the positive residues mod 99 of 2^k and 10*2^k. - David Wilson, Apr 19 2024
EXAMPLE
a(20) = 67 and here is the 20-move combination that reaches 67: 1, 2, 4, 8, 61, 221, 244, 884, 8671, 17342, 48643, 97286, 275491, 289055, 11875, 23750, 47500, 95000, 190000, 380000, 67.
a(21) = 35 and here is the 21-move combination that reaches 35: 1, 2, 4, 8, 61, 221, 244, 884, 8671, 17342, 48643, 97286, 275491, 289055, 11875, 23750, 47500, 95000, 91, 281, 265, 35.
a(30) = 1 using the path: 1, 2, 4, 8, 61, 122, 442, 488, 976, 2591, 2815, 365, 37, 47, 49, 98, 196, 392, 487, 479, 859, 1718, 3436, 2786, 2755, 155, 13, 26, 25, 5, 1. - Michael S. Branicky, Apr 14 2024
PROG
(Python)
def f(k, d):
if d == 0:
return k
else:
return min(f(2*k, d-1), f(int(str(2*k)[::-1]), d - 1))
def a(n):
return f(1, n)
for n in range(25):
print(a(n))
(Python)
from itertools import islice
def reverse(n): return int(str(n)[::-1])
def agen(): # generator of terms
reach = {1}
while True:
yield min(reach)
newreach = set()
for q in reach: newreach.update([2*q, reverse(2*q)])
reach = newreach
print(list(islice(agen(), 28))) # Michael S. Branicky, Apr 14 2024
(PARI) \\ See PARI link
CROSSREFS
KEYWORD
nonn,base,easy
AUTHOR
Bryle Morga, Apr 14 2024
EXTENSIONS
a(27)-a(34) from Michael S. Branicky, Apr 14 2024
a(35) and beyond from David Wilson, Apr 19 2024
STATUS
approved