Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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) ?
share|improve this question
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, about which there is a huge literature. –  André Nicolas Nov 29 '12 at 8:19
    
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 W –  Pam Nov 29 '12 at 8:27
    
@SandraB: Then you should write that; it's more usual and clearer than what you wrote in the question instead. –  joriki Nov 29 '12 at 8:48
    
@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$. –  André Nicolas Nov 29 '12 at 17:41
    
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 ? –  Pam Nov 29 '12 at 18:39
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.