cp's OEIS Frontend

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.

%I A348339 #27 Dec 24 2024 07:33:56
%S A348339 3,6,9,12,19,28,39,52,67,84
%N 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.
%C A348339 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.
%H A348339 Ya-Ping Lu, <a href="/A348339/a348339_1.pdf">Illustration of the paths</a>
%e A348339 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.
%e A348339 a(2) = 6 because the distinct steps are: {1, 2, 3, 4, 5, 6}.
%e A348339 a(3) = 9: {1, 2, 3, 4, 5, 6, 20, 21, 22}.
%e A348339 a(4) = 12: {1, 2, 3, 4, 5, 6, 20, 21, 22, 100, 101, 102}.
%e A348339 a(5) = 19: {1, 2, 3, 4, 5, 6, 7, 20, 21, 22, 23, 100, 101, 102, 103, 500, 501, 502, 503}.
%e A348339 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}.
%e A348339 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.
%o A348339 (Python)
%o A348339 def tail(m):
%o A348339     global n; s = str(m)
%o A348339     return m if len(s) <= n else int(s[-n:])
%o A348339 for n in range(1, 10):
%o A348339     M = []
%o A348339     for i in range(10**n):
%o A348339         t = i; L = [t]
%o A348339         while i >= 0:
%o A348339             t = tail(t*t)
%o A348339             if t not in L: L.append(t)
%o A348339             else: break
%o A348339         d = len(L)
%o A348339         if d not in M: M.append(d)
%o A348339     print(len(M), end = ', ')
%o A348339 (Python)
%o A348339 def A348339(n):
%o A348339     m, s = 10**n, set()
%o A348339     for k in range(m):
%o A348339         c, k2, kset = 0, k, set()
%o A348339         while k2 not in kset:
%o A348339             kset.add(k2)
%o A348339             c += 1
%o A348339             k2 = k2*k2 % m
%o A348339         s.add(c)
%o A348339     return len(s) # _Chai Wah Wu_, Oct 19 2021
%Y A348339 Cf. A000290, A348338.
%K A348339 nonn,base,more
%O A348339 1,1
%A A348339 _Ya-Ping Lu_, Oct 13 2021
%E A348339 a(10) from _Martin Ehrenstein_, Oct 20 2021