A348339 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 -> m^2.

3, 6, 9, 12, 19, 28, 39, 52, 67, 84

Offset: 1

Author

Ya-Ping Lu, Oct 13 2021

Keywords

• nonn
• base
• more

Comments

Conjecture: For n >= 5, a(n) = a(n-1) + 2*n - 3 - ceiling(log_5 ((n-1)/16)), or a(n) = (n-1)^2 + 3 - Sum_{5..n} ceiling(log_5 ((i-1)/16)). The largest number of steps required is 4*5^(n-2) + (n-2) for n >= 4.

Examples

			a(1) = 3. Integers ending with 0, 1, 5 or 6 take 1 step to repeat the last digit. Integers ending with 4 or 9 require 2 steps and 2, 3, 7 or 8 require 3 steps to repeat their last digit. Thus, the distinct numbers of steps for n = 1 are {1, 2, 3} and a(1) = 3.
a(2) = 6 because the distinct steps are: {1, 2, 3, 4, 5, 6}.
a(3) = 9: {1, 2, 3, 4, 5, 6, 20, 21, 22}.
a(4) = 12: {1, 2, 3, 4, 5, 6, 20, 21, 22, 100, 101, 102}.
a(5) = 19: {1, 2, 3, 4, 5, 6, 7, 20, 21, 22, 23, 100, 101, 102, 103, 500, 501, 502, 503}.
a(6) = 28: {1, 2, 3, 4, 5, 6, 7, 8, 20, 21, 22, 23, 24, 100, 101, 102, 103, 104, 500, 501, 502, 503, 504, 2500, 2501, 2502, 2503, 2504}.
The paths of the last 1, 2, and 3 digits of integers resulted from iterating the map, m -> m*m, are shown in the Links.
		

Links

• Ya-Ping Lu, Illustration of the paths

Crossrefs

Cf. A000290, A348338.

Programs

Python

def tail(m):
    global n; s = str(m)
    return m if len(s) <= n else int(s[-n:])
for n in range(1, 10):
    M = []
    for i in range(10**n):
        t = i; L = [t]
        while i >= 0:
            t = tail(t*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 A348339(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 = k2*k2 % m
        s.add(c)
    return len(s) # Chai Wah Wu, Oct 19 2021

Extensions

a(10) from Martin Ehrenstein, Oct 20 2021