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

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, 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, 2, 14, 1, 25, 26, 16, 1, 5, 8, 14, 5, 1, 2, 32, 3, 5, 50, 4, 17, 5, 4, 4, 143

Offset

1,1

Comments

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

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

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

Links

Hillel Wayne, Table of n, a(n) for n = 1..1002

George Marsaglia, Random Number Generators, Journal of Modern Applied Statistical Methods, Volume 2, Issue 1 (2003).

Kenneth Shum, Cyclotomic cosets.

Example

For a(4) the 8 cycles are:
  (1 10 22 25 16 4)
  (2 20 5 11 32 8)
  (3 30 27 36 9 12)
  (6 21 15 33 18 24)
  (7 31 37 19 34 28)
  (13)
  (14 23 35 38 29 17)
  (26)

Prog

(Python)
def get_num_orbits(n: int) -> int:
    orbits = 0
    mod = 10*n - 1
    seen = set()
    for i in range(1, mod):
        if i not in seen:
            seen.add(i)
            orbits += 1
        x = 10*i % mod
        while x != i:
            seen.add(x)
            x = 10*x % mod
    return orbits
(Python)
from sympy import totient, n_order, divisors
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
(PARI)
a(n)=sumdiv(10*n-1, d, eulerphi(d)/znorder(Mod(10, d)))-1;
vector(100, n, a(n-1)) \\ Joerg Arndt, Jan 22 2024

Crossrefs

Cf. A006694, A023142, A128858, A128857.

Sequence in context: A178163 A197110 A109571 * A133823 A168643 A173742

Adjacent sequences: A366491 A366492 A366493 * A366495 A366496 A366497

Keyword

nonn

Author

Hillel Wayne, Oct 10 2023

Status

approved