cp's OEIS Frontend

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

%I A366494 #38 Apr 09 2024 14:20:39
%S A366494 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 A366494 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 A366494 2,14,1,25,26,16,1,5,8,14,5,1,2,32,3,5,50,4,17,5,4,4,143
%N A366494 a(n) is the number of cycles of the map f(x) = 10*x mod (10*n - 1).
%C A366494 Taking the length of each orbit that starts from f(0)=1 gives the sequence A128858.
%C A366494 Equivalently, the number of cyclotomic cosets of 10 mod (10*n - 1). See A006694.
%C A366494 Map is the Multiply-with-carry algorithm with a=n, b=10, and c=1.
%H A366494 Hillel Wayne, <a href="/A366494/b366494.txt">Table of n, a(n) for n = 1..1002</a>
%H A366494 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 A366494 Kenneth Shum, <a href="https://mypage.cuhk.edu.cn/academics/wkshum/sage/cyclotomic_coset.html">Cyclotomic cosets</a>.
%e A366494 For a(4) the 8 cycles are:
%e A366494   (1 10 22 25 16 4)
%e A366494   (2 20 5 11 32 8)
%e A366494   (3 30 27 36 9 12)
%e A366494   (6 21 15 33 18 24)
%e A366494   (7 31 37 19 34 28)
%e A366494   (13)
%e A366494   (14 23 35 38 29 17)
%e A366494   (26)
%o A366494 (Python)
%o A366494 def get_num_orbits(n: int) -> int:
%o A366494     orbits = 0
%o A366494     mod = 10*n - 1
%o A366494     seen = set()
%o A366494     for i in range(1, mod):
%o A366494         if i not in seen:
%o A366494             seen.add(i)
%o A366494             orbits += 1
%o A366494         x = 10*i % mod
%o A366494         while x != i:
%o A366494             seen.add(x)
%o A366494             x = 10*x % mod
%o A366494     return orbits
%o A366494 (Python)
%o A366494 from sympy import totient, n_order, divisors
%o A366494 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 A366494 (PARI)
%o A366494 a(n)=sumdiv(10*n-1, d, eulerphi(d)/znorder(Mod(10, d)))-1;
%o A366494 vector(100, n, a(n-1)) \\ _Joerg Arndt_, Jan 22 2024
%Y A366494 Cf. A006694, A023142, A128858, A128857.
%K A366494 nonn
%O A366494 1,1
%A A366494 _Hillel Wayne_, Oct 10 2023