OFFSET
1,1
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.
LINKS
EXAMPLE
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.
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, 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
CROSSREFS
KEYWORD
nonn,base,more
AUTHOR
Ya-Ping Lu, Oct 13 2021
EXTENSIONS
a(10) from Martin Ehrenstein, Oct 20 2021
STATUS
approved