A366494 - OEIS

%I #38 Apr 09 2024 14:20:39

%S 8,1,1,8,2,1,5,6,2,53,1,4,8,3,1,14,4,1,41,2,16,29,1,34,8,49,1,26,2,7,

%T 11,16,4,5,3,2,80,1,1,26,2,1,83,2,14,29,9,2,8,1,1,14,2,27,17,16,2,5,9,

%U 2,14,1,25,26,16,1,5,8,14,5,1,2,32,3,5,50,4,17,5,4,4,143

%N a(n) is the number of cycles of the map f(x) = 10*x mod (10*n - 1).

%C Taking the length of each orbit that starts from f(0)=1 gives the sequence A128858.

%C Equivalently, the number of cyclotomic cosets of 10 mod (10*n - 1). See A006694.

%C Map is the Multiply-with-carry algorithm with a=n, b=10, and c=1.

%H Hillel Wayne, <a href="/A366494/b366494.txt">Table of n, a(n) for n = 1..1002</a>

%H George Marsaglia, <a href="https://doi.org/10.22237/jmasm/1051747320">Random Number Generators</a>, Journal of Modern Applied Statistical Methods, Volume 2, Issue 1 (2003).

%H Kenneth Shum, <a href="https://mypage.cuhk.edu.cn/academics/wkshum/sage/cyclotomic_coset.html">Cyclotomic cosets</a>.

%e For a(4) the 8 cycles are:

%e   (1 10 22 25 16 4)

%e   (2 20 5 11 32 8)

%e   (3 30 27 36 9 12)

%e   (6 21 15 33 18 24)

%e   (7 31 37 19 34 28)

%e   (13)

%e   (14 23 35 38 29 17)

%e   (26)

%o (Python)

%o def get_num_orbits(n: int) -> int:

%o     orbits = 0

%o     mod = 10*n - 1

%o     seen = set()

%o     for i in range(1, mod):

%o         if i not in seen:

%o             seen.add(i)

%o             orbits += 1

%o         x = 10*i % mod

%o         while x != i:

%o             seen.add(x)

%o             x = 10*x % mod

%o     return orbits

%o (Python)

%o from sympy import totient, n_order, divisors

%o def A366494(n): return sum(totient(d)//n_order(10,d) for d in divisors(10*n-1,generator=True) if d>1) # _Chai Wah Wu_, Apr 09 2024

%o (PARI)

%o a(n)=sumdiv(10*n-1, d, eulerphi(d)/znorder(Mod(10, d)))-1;

%o vector(100, n, a(n-1)) \\ _Joerg Arndt_, Jan 22 2024

%Y Cf. A006694, A023142, A128858, A128857.

%K nonn

%O 1,1

%A _Hillel Wayne_, Oct 10 2023