OFFSET
1,3
COMMENTS
All such sequences will be cyclic with period length n.
Different values of the integers a and c modulo n will always produce different sequences.
Only sequences starting with x_0 = 0 are included here. However using any other fixed number in the interval [0..n-1] for x_0 will result in the same cycles.
It appears that the set of distinct terms of this sequence gives A049225.
From Andrew Howroyd, Aug 21 2019: (Start)
Knuth calls these sequences linear congruential sequences. Theorem A in section 3.2.1.2 of the reference states that the period has length n if and only if:
1) c is relatively prime to n;
2) a - 1 is a multiple of p for every prime p dividing n;
3) a - 1 is a multiple of 4 if n is a multiple of 4.
(End)
REFERENCES
D. E. Knuth, The Art of Computer Programming, Vol. 3, Random Numbers, Section 3.2.1.2, p. 16.
LINKS
Andrew Howroyd, Table of n, a(n) for n = 1..500 (terms 1..100 from Jinyuan Wang)
FORMULA
Conjecture: a(n) = A135616(n)/n.
Conjecture: a(n) = phi(n)*A003557(n / gcd(n,2)). - Andrew Howroyd, Aug 20 2019
EXAMPLE
For n = 1:
a = 0, c = 0: [0];
#cycles = 1 -> a(1) = 1.
For n = 5:
a = 1, c = 1: [0, 1, 2, 3, 4];
a = 1, c = 2: [0, 2, 4, 1, 3];
a = 1, c = 3: [0, 3, 1, 4, 2];
a = 1, c = 4: [0, 4, 3, 2, 1];
#cycles = 4 -> a(5) = 4.
For n = 8:
a = 1, c = 1: [0, 1, 2, 3, 4, 5, 6, 7];
a = 1, c = 3: [0, 3, 6, 1, 4, 7, 2, 5];
a = 1, c = 5: [0, 5, 2, 7, 4, 1, 6, 3];
a = 1, c = 7: [0, 7, 6, 5, 4, 3, 2, 1];
a = 5, c = 1: [0, 1, 6, 7, 4, 5, 2, 3];
a = 5, c = 3: [0, 3, 2, 5, 4, 7, 6, 1];
a = 5, c = 5: [0, 5, 6, 3, 4, 1, 2, 7];
a = 5, c = 7: [0, 7, 2, 1, 4, 3, 6, 5];
#cycles = 8 -> a(8) = 8.
PROG
(PARI) checkFullSet(v, n)={my(v2=vector(n), unique=1); for(i=1, n, my(j=v[i]+1); if(v2[j]==1, unique=0; break, v2[j]=1; ); ); unique; };
doCycle(a, c, m)={my(v_=vector(m), x=c); v_[1]=c; for(i=1, m-1, v_[i+1]=(a*v_[i]+c)%m; ); v_; };
getCycles(m)={my(L=List()); for(a=0, m-1, for(c=0, m-1, my(v1=doCycle(a, c, m)); if(checkFullSet(v1, m), listput(L, v1)); ); ); Mat(Col(L))};
a(n)={my(M=getCycles(n)); matsize(M)[1]};
CROSSREFS
KEYWORD
nonn
AUTHOR
Haris Ziko, Jun 27 2019
STATUS
approved