A348338 -id:A348338 - 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.

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

Offset: 1

Ya-Ping Lu, Oct 13 2021

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.

			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.

Ya-Ping Lu, Illustration of the paths

Cf. A000290, A348338.

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 = ', ')

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

a(10) from Martin Ehrenstein, Oct 20 2021

A349744 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^3.

Original entry on oeis.org

2, 5, 7, 12, 15, 18, 29, 42, 57, 87, 108

Offset: 1

Ya-Ping Lu, Nov 28 2021

			a(1) = 2. The paths of the last digit of integers resulted from iterating the map, m -> m^3, are: 0->0; 1->1; 2->8->2; 3->7->3; 4->4; 5->5; 6->6; 7->3->7; 8->2->8; 9->9. Integers ending with 0, 1, 4, 5, 6 or 9 take 1 step to repeat the last digit. Integers ending with 2, 3, 7 or 8 takes 2 steps to repeat the last digit. Therefore, for n = 1, the distinct numbers of steps s(1) = {1, 2} and a(1) = 2.
a(2) = 5 because the distinct steps for the last two digits of integers to repeat themselves by iterating the map, m -> m^3, is s(2) = {1, 2, 3, 4, 5}.
a(3) = 7:  s(3) = s(2) + {20, 21}.
a(4) = 12: s(4) = s(3) + {6, 22, 100..102}.
a(5) = 15: s(5) = s(4) + {500..502}.
a(6) = 18: s(6) = s(5) + {2500..2502}.
a(7) = 29: s(7) = s(6) + {8..10, 40, 200, 1000, 5000, 12500..12502, 25000}
a(8) = 42: s(8) = s(7) + {16..18, 80, 400, 2000, 10000, 50000, 62500..62502, 125000, 250000}.
a(9) = 57: s(9) = s(8) + {32..34, 160, 800, 4000, 20000, 100000, 312500..312502, 500000, 625000, 1250000, 2500000}.
a(10)= 87: s(10)= s(9) + {7, 11, 19, 23, 35, 64..67, 103, 320, 503, 1600, 2503, 8000, 12503, 40000, 62503, 200000, 312503, 1000000, 1562500..1562503, 3125000, 5000000, 6250000, 12500000, 25000000}.
a(11)=108: s(11)=s(10) + {128..131, 640, 3200, 16000, 80000, 400000, 2000000, 7812500..7812503, 10000000, 15625000, 31250000, 50000000, 62500000, 125000000, 250000000}.

Cf. A000578, A348338, A348339.

for n in range(1, 12):
    b = 10**n; M = set()
    for i in range(b):
        t = i; L = set()
        while t not in L: L.add(t); t = (t**3)%b
        d = len(L)
        if d not in M: M.add(d)
    print(len(M), end = ', ')

A350588 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^5.

Original entry on oeis.org

1, 2, 3, 4, 6, 9, 14, 23, 33, 45, 59, 75, 93, 113, 135, 159, 184, 211, 240, 271, 304, 339, 376, 415, 456, 499, 544, 591, 640, 691, 744, 799, 855, 913, 973, 1035, 1099, 1165, 1233, 1303, 1375, 1449, 1525, 1603, 1683, 1765, 1849, 1935, 2023, 2113, 2205, 2299

Offset: 1

Ya-Ping Lu, Jan 07 2022

			a(1) = 1. It takes one step to repeat the last digit by iterating the map on an integer. For example, 2^5 = 32 and 9^5 = 59049. Thus, the distinct number of steps for n = 1 is {1} and a(1) = 1.
a(2) = 2. It takes 1 or 2 steps for an integer to repeat its last two digits. For example, 24 -> 7962624; 27 -> 14348907 -> 608266787713357709119683992618861307. Thus, a(2) = 2: {1, 2}.
a(3)  =  3: {1..3}.
a(4)  =  4: {1..4}.
a(5)  =  6: {1..6}.
a(6)  =  9: {1..9}.
a(7)  = 14: {1..14}.
a(8)  = 23: {1..23}.
a(9)  = 33: {1..24, 32..40}.
a(10) = 45: {1..25, 32..41, 64..73}.
a(11) = 59: {1..26, 32..42, 64..74, 128..138}.

Cf. A000584, A348338, A348339, A349744.

from math import log, ceil
def A350588(n):
    if n <= 8:
        b, S = 10**n, set()
        for i in range(b):
            t, s, T = i, 0, set()
            while t not in T: T.add(t); t = (t**5)%b; s += 1
            S.add(s)
        return(len(S))
    else: return n*n - 3*n - 17 - sum(ceil(log(i, 2)) for i in range(9, n+1))

For n >= 9, a(n) = a(n-1) + 2*n - 4 - ceiling(log_2 (n)) or a(n) = n^2 - 3*n - 17 - Sum_{i=9..n} ceiling(log_2 (i)).

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Python

Extensions

A349744 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^3.

Views

Author

Keywords

Examples

Crossrefs

Programs

Python

A350588 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^5.

Views

Author

Keywords

Examples

Crossrefs

Programs

Python

Formula