I am investing the randomness properties of the sequence $y_n=\bmod(x_n,c)$ with $c=2$ and

$$x_{n+1} = x_n +\sum_{k=1}^r a_k\bmod(x_n,p_k)+\sum_{k=1}^r b_k\bmod(n+1,p_k).$$

The initial value is $x_1$, and $p_1,p_2$ and so on are the prime numbers, with $p_1=2$. Also, $a_k,b_k\in \{-1, 0, 1\}$. I've spent a bit of time on the case $r=8, x_1=3$, with the following coefficients:

\begin{array}{|c|cccccccc|} \hline k & 1& 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \hline p_k & 2& 3 & 5 & 7 & 11 & 13 & 17 & 19\\ a_k& -1 & 1 & 1 & 1 & -1 & -1 & 0 & 1\\ b_k& -1 & -1 & -1 & -1& 1& 1 & 0 & -1\\ \hline \end{array}

Very little memory is needed to generate the $x_n$'s. So far I run only a few tests to check randomness (mostly the runs test). It seems to do fine and period-free up until some very large $n$. Then, all of a sudden the difference $x_{n+1}-x_n$ becomes permanently constant. In my example, I don't know when that happens, it must be for $n>10^8$ and maybe much larger. But with smaller values of $r$ (say $r=3$) this becomes apparent quite early.

My question

Is the behavior described above always the case regardless of the coefficients, $x_1$ and $r$? In other words, is it impossible to build a non-periodic generator with my method, even though the very short period may kick in after a very large number of iterations (just like the binary digits of a rational number may not start showing a period until after a lot of digits)? And of course, I'd like to know when exactly (or get some bounds) on the value of $n$ when the period starts, especially in the example discussed above.

  • 2
    $\begingroup$ I've checked your $r=8$ case and found a period of at most $19\#$. The $r=3$ case with $p=\{2, 3, 5\}$ also shows a period of $30=5\#$. It's possible that your PRNG with output $x_{n+1}-x_n$ will eventually enter a period of $\prod p_k$ regardless of the coefficients. $\endgroup$ Nov 17, 2021 at 2:08
  • $\begingroup$ You are right, the period seems to be $2\times 3 \times 5 \times 7 \times 11 \times 13 \times 19$. But if you remove $19$ and use $17$ with $a_7=1,b_7=-1$, the period is only $2$, but it starts after more than $7\times 10^6$ iterations. If you keep $19$ unchanged with same coefficients, do not use $17$, and add $23$ with $a_9=-1, b_9=1$, I have no idea what the period is, how big or small it is or even if there is one. But if there is one, it must starts after $10^9$ iterations. $\endgroup$ Nov 17, 2021 at 5:17
  • 1
    $\begingroup$ For the case with additional $\{p_9=23, a_9=-1, b_9=1\}$, the period is $643032390=2\times3\times5\times7^3\times11\times13\times19\times23$. The scaling factor of $49$ comes from nowhere. $\endgroup$ Nov 17, 2021 at 7:31

1 Answer 1


This is a partial solution too long for a comment, but too incomplete to be an answer.

Considering the second summation over a period of $P=\prod p_k$: $$ \begin{align*} \sum_{i=1}^P\sum_{k=1}^r b_k\operatorname{mod}(n+i, p_k)&=\sum_{k=1}^r\left(b_k\sum_{i=1}^P\operatorname{mod}(n+i, p_k)\right)\\ &=\sum_{k=1}^r\left(b_k\cdot\frac{P}{p_k}\cdot\frac{p_k(p_k-1)}2\right)\\ &=\sum_{k=1}^r\frac{b_kP(p_k-1)}2 \end{align*} $$ which is a constant derivable from the coefficients.

Considering again the whole iteration formula over a period of $P$, $$ \begin{align*} x_{n+P}&=x_n+\sum_{i=1}^P\sum_{k=1}^r a_k\operatorname{mod}(x_{n+i-1}, p_k)+\sum_{i=1}^P\sum_{k=1}^r b_k\operatorname{mod}(n+i, p_k)\\ &=x_n+\sum_{i=1}^P\sum_{k=1}^r a_k\operatorname{mod}(x_{n+i-1}, p_k)+\text{some constant} \end{align*} $$ then what's left is to prove that whether the first summation turns out to be constant.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .