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