A371880 Smallest number reachable starting from 1 and taking n steps either doubling or doubling+reversing.

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

Author

Bryle Morga, Apr 14 2024

Keywords

• nonn
• base
• easy

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

Examples

			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
		

Links

• David A. Corneth, PARI program.
• Bryle Morga et al., Optimal strategy in a game where Doubling and Doubling+Reversing are the allowed moves.
• Index entries for linear recurrences with constant coefficients, signature (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1).

Crossrefs

Cf. A000079, A004086, A004094, A036447, A371966.

Programs

PARI

\\ See PARI link

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

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

Extensions

a(27)-a(34) from Michael S. Branicky, Apr 14 2024

a(35) and beyond from David Wilson, Apr 19 2024