OFFSET
0,2
COMMENTS
For n >= 1, the largest number of steps required is 4*5^(n-1) + n.
FORMULA
For n >= 1, a(n) = a(n-1) + 2*n - ceiling(log_5 ((n+1)/16)), or a(n) = n^2 + n + 2 - Sum_{2..n} ceiling(log_5 ((i+1)/16)).
EXAMPLE
a(1) = 4. As shown below, integers ending with 0, 5, {2, 4, 6 or 8}, and {1, 3, 7, or 9} require 1, 2, 4, and 5 steps to repeat the last digit, respectively. Therefore, the distinct numbers of steps are {1, 2, 4, 5} and a(1) = 4.
_ 1=>2===>4<=7
v \ ^ v
5==>0== 3=>6<===8<=9
a(2) = 9 because the distinct steps are {1, 2, 3, 4, 5, 6, 20, 21, 22}, as shown by the paths of the last two digits of integers.
_ 1,51 27,77 29,79 33,83 41,91 7,57
v \ v v v v v v
25,75==>50==>0== 2 54 58 66 82 14
v v v v v v
4=====>8=====>16====>32====>64====>28
5,55 35,85 ^ v
v v 13,63=>26=>52 56<=78<=39,89
10 70 ^ v
v v 19,69=>38=>76 12<==6<==3,53
20==>40 ^ v
^ v 47,97=>94=>88 24<=62<=31,81
60<==80 ^ v
^ ^ 11,61=>22=>44 48<=74<=37,87
30 90 ^ v
^ ^ 72<====36<====68<====84<====92<====96
15,65 45,95 ^ ^ ^ ^ ^ ^
86 18 34 42 46 98
^ ^ ^ ^ ^ ^
43,93 9,59 17,67 21,71 23,73 49,99
a(3) = 15 because the distinct steps for n = 3 are {1, 2, 3, 4, 5, 6, 7, 20, 21, 22, 23, 100, 101, 102, 103}.
PROG
(Python)
def tail(m):
global n; s = str(m)
return m if len(s) <= n else int(s[-n:])
for n in range(1, 9):
M = []
for i in range(10**n):
t = i; L = [t]
while i >= 0:
t = tail(2*t)
if t not in L: L.append(t)
else: break
d = len(L)
if d not in M: M.append(d)
print(len(M), end = ', ')
(Python)
def A348338(n):
m, s = 10**n, set()
for k in range(m):
c, k2, kset = 0, k, set()
while k2 not in kset:
kset.add(k2)
c += 1
k2 = 2*k2 % m
s.add(c)
return len(s) # Chai Wah Wu, Oct 19 2021
(PARI) a(n) = n + (n+1)*(n-1-t=(logint(5*(n+1)>>4+(n<3), 5))) + 4*5^t - (2-n)*(n<3); \\ Jinyuan Wang, Nov 02 2021
CROSSREFS
KEYWORD
nonn,base
AUTHOR
Ya-Ping Lu, Oct 13 2021
EXTENSIONS
a(9)-a(10) from Martin Ehrenstein, Oct 20 2021
a(0) prepended and a(11)-a(14) from Martin Ehrenstein, Oct 29 2021
More terms from Jinyuan Wang, Nov 02 2021
STATUS
approved