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.

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

Author

Ya-Ping Lu, Oct 13 2021

Keywords

• nonn
• base

Comments

For n >= 1, the largest number of steps required is 4*5^(n-1) + n.

Examples

			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}.
		

Crossrefs

Cf. A005843, A348339.

Programs

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

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

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

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