A371880 - OEIS

%I #81 May 06 2024 18:58:22

%S 1,2,4,8,16,23,46,29,58,71,34,68,37,47,49,89,79,59,19,38,67,35,7,14,

%T 28,56,13,26,25,5,1,2,4,8,16,23,46,29,58,17,34,68,37,47,49,89,79,59,

%U 19,38,67,35,7,14,28,56,13,26,25,5,1,2,4,8,16,23,46,29,58,17

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

%C 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.

%C From _Michael S. Branicky_, Apr 14 2024: (Start)

%C 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?

%C 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)

%C 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

%C From _David A. Corneth_, Apr 15 2024: (Start)

%C a(n) == 2^n (mod 9).

%C 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)

%C Ultimately periodic sequence of period 30 with a(k+30)=a(k) for k != 9. - _David Wilson_, Apr 19 2024

%H David A. Corneth, <a href="/A371880/a371880.gp.txt">PARI program</a>.

%H Bryle Morga et al., <a href="https://math.stackexchange.com/questions/4899315/optimal-strategy-in-a-game-where-doubling-and-doublingreversing-are-the-allowed/4901445#4901445">Optimal strategy in a game where Doubling and Doubling+Reversing are the allowed moves</a>.

%H <a href="/index/Rec#order_30">Index entries for linear recurrences with constant coefficients</a>, 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).

%F 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)).

%F a(30k) = 1 for k >= 0. - _Michael S. Branicky_, Apr 14 2024

%F 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

%e 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.

%e 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.

%e 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

%o (Python)

%o def f(k, d):

%o       if d == 0:

%o             return k

%o       else:

%o             return min(f(2*k, d-1), f(int(str(2*k)[::-1]), d - 1))

%o def a(n):

%o       return f(1, n)

%o for n in range(25):

%o       print(a(n))

%o (Python)

%o from itertools import islice

%o def reverse(n): return int(str(n)[::-1])

%o def agen(): # generator of terms

%o     reach = {1}

%o     while True:

%o         yield min(reach)

%o         newreach = set()

%o         for q in reach: newreach.update([2*q, reverse(2*q)])

%o         reach = newreach

%o print(list(islice(agen(), 28))) # _Michael S. Branicky_, Apr 14 2024

%o (PARI) \\ See PARI link

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

%K nonn,base,easy

%O 0,2

%A _Bryle Morga_, Apr 14 2024

%E a(27)-a(34) from _Michael S. Branicky_, Apr 14 2024

%E a(35) and beyond from _David Wilson_, Apr 19 2024