1
$\begingroup$

Let $N, K, W$ be natural numbers

If I start from $R_0$, say any integer $r_0, 0 \lt r_0 \lt N$

and proceed with:

$$R_j = ( R_{j-1} + K ) \mod W,\quad j=1,2, \dots$$

(that is the remainder of the division $\frac{R_{j-1} + K }{W}$).

I can imagine that, when $R_j$ "returns" to the initial value $r_0$, a new "cycle" of identical remainders will start again: $R_0 = r_0 , R_1 , \dots , R_{p-1} = r_0$

Can we say something more about this sequence of remainders (does it have a name, etc.) ? In particular:

  • What is the (minimal) length $p$ of the cycle (period) in general ?
  • Can we express $R_j$ in a "non recursive" form ( $R_j$ = some function of the initial data) ?
  • 1
    I do not know what you mean by the notation, since typically $W$ will not divide $R(j-1)+K$. Something relatively close is the [Linear Congruential Generator](http://en.wikipedia.org/wiki/Linear_congruential_generator), about which there is a huge literature.2012-11-29
  • 0
    Thank you André. What notation is not clear? For sure there can be a remainder, in fact i am just considering the sequences of remainders. I am considering: ( R(j-1) + K ) mod W2012-11-29
  • 0
    @SandraB: Then you should write that; it's more usual and clearer than what you wrote in the question instead.2012-11-29
  • 0
    @SandraB: I wasn't reading carefully enough, the basically irrelevant $M$ together with "$M$ large" led me to think $M$ was a modulus, and you were doing operations modulo two numbers. So yes, what you have is a special case of the linear congruential generator, in a sense, but without the a multiplier in front of $R(j-1)$ it no longer has a pseudo-random character. Cycle length is easy, it is $W$ divided by the $gcd$ of $K$ and $W$.2012-11-29
  • 0
    Thanks a lot André. I will change M in N and remove the irrelevant adjective to avoid unnecessary ambiguities. It's interesting what you say about the cycle length. Can you give some easy to follow justification for that ?2012-11-29
  • 0
    And, since you note that "no longer has a pseudo-random character", do you think is it possible to come up with an expression (non recursive) for the R(j) ?2012-11-29
  • 0
    I have tried to tex it, but changed some notation ($r_0$, instead of $R_0$). Hope that does not confuse the comments above.2013-04-03

0 Answers 0