# Period or lack of, for a (probably new) pseudo-random number generator

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.

• 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. Nov 17, 2021 at 2:08
• 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. Nov 17, 2021 at 5:17
• 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. Nov 17, 2021 at 7:31

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.