login
A348338
a(n) is the number of distinct numbers of steps required for the last n digits of integers to repeat themselves by iterating the map m -> 2*m.
4
1, 4, 9, 15, 23, 33, 45, 59, 75, 93, 113, 135, 159, 185, 213, 243, 274, 307, 342, 379, 418, 459, 502, 547, 594, 643, 694, 747, 802, 859, 918, 979, 1042, 1107, 1174, 1243, 1314, 1387, 1462, 1539, 1618, 1699, 1782, 1867, 1954, 2043, 2134, 2227, 2322, 2419, 2518
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
Sequence in context: A184005 A194106 A004629 * A065893 A052116 A109641
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