who can solve this problem : x[n+1]=(a*x[n]+c)mod m; with how condition, x[n] shall have period. Find period.

Question

ironduke8159, you were wrong! Maybe less m, but i cannot show ! But have simple example : x0=1,a=3,m=6,c=1 will get 1,4,1,4,1,4.... =>period = 2 less m=3. Ok ?But i cannot
prove !

jonsmart, if series 5,5,5.... =>period will be 1, not 0. Ok ?

lewanj wrong !
a:=3;c:=1;m:=6;
try run on maple ...
> f:=unapply(x*a^n+(1-a^n)/(1-a)*c,[x,n]);
a := 3
c := 1
m := 6

n n
f := (x, n) -> x 3 - 1/2 + 1/2 3

> f(1,1);

4

> f(4,2) mod 6;

4
will get 1,4,4,4 but my problem will be 1,4,1,4...

Sorry, lewanj you're right !
I can show your formul is right !
But I can understand how do you find it ?
Can you show me !

Sorry, lewanj you're right !
I can prove your formul is right !
But I can understand how do you find it ?
Can you show me !

Answer 1

This is an interesting question.

The exact answer to x[n+1] = a*x[n]+c is

If a doesn't equal zero,
x[n] = x0*a^n + ( (1-a^n) / (1-a) )*c

If a=0
x[n] = x0 + n*c

The period will be dermined by finding the period of the exact solution mod m.

Added:
WHAT?

If you work out the exact solution mod 6 with a=3, c=1, and X0=1 you'll get

X0 = 1,
X1 = 4,
X2 = 13 mod 6 = 1,
x3 = 40 mod 6 = 4, ...

Answer 2

I think it will depend on the value of a, c, x0, and m. For example, if a=2 and c=1 then a*x[n]+c is always odd. If m is even, then the series will repeat itself but can never take on even values so it will be at most m/2. However in this example, if m is now odd then you will have at most m. But I dont know how you'd compute exactly what the period is given a, c and m. Take a=2, c=1, m=6 and x0=5 then you only get 5s and your period is 0!

Answer 3

x[n+1]=(a*x[n]+c)mod m
The period should simply be m.