Number of distinct periods of LCG

24 Views Asked by At

I'm looking for the number of distinct periods of a LCG

$$ \lambda(a, c, m) := {X_{n+1}=\left(aX_{n}+c\right){\bmod {m}}} $$

A period $a = a_1, a_2, a_3 \ldots a_n$ is different from a period $b = b_1, b_2, b_3 \ldots b_m \iff a_i \neq b_j \forall i \in [1, 2 \ldots n], j \in [1, 2 \ldots m]$. In other words when $a$ and $b$ share no common number; if that was the case, then the next number in $a$ would be the same of the next number in $b$ and so on, resulting in $b$ being just a shifted version of $a$. The following if the plot of the number of distinct periods of $\lambda(a, 0, m)$ plot of number of distinct periods You read it like this: the number of distinct periods of $\lambda(13, 0, 14) = 8$ since

  • $x_0$ = $0$ generates the period: $0, \ldots$
  • $x_0$ = $1$ generates the period: $13, 1, \ldots$
  • $x_0$ = $2$ generates the period: $12, 2, \ldots$
  • $x_0$ = $3$ generates the period: $11, 3, \ldots$
  • $x_0$ = $4$ generates the period: $10, 4, \ldots$
  • $x_0$ = $5$ generates the period: $9, 5, \ldots$
  • $x_0$ = $6$ generates the period: $8, 6, \ldots$
  • $x_0$ = $7$ generates the period: $7, \ldots$
  • $x_0$ = $8$ generates the period: $6, 8, \ldots$
  • $x_0$ = $9$ generates the period: $5, 9, \ldots$
  • $x_0$ = $10$ generates the period: $4, 10, \ldots$
  • $x_0$ = $11$ generates the period: $3, 11, \ldots$
  • $x_0$ = $12$ generates the period: $2, 12, \ldots$
  • $x_0$ = $13$ generates the period: $1, 13, \ldots$

and so forth $\ldots$