A308828 Number of sequences that include all residues modulo n starting with x_0 = 0 and then x_i given recursively by x_{i+1} = a * x_i + c (mod n) where a and c are integers in the interval [0..n-1].

1, 1, 2, 2, 4, 2, 6, 8, 18, 4, 10, 4, 12, 6, 8, 32, 16, 18, 18, 8, 12, 10, 22, 16, 100, 12, 162, 12, 28, 8, 30, 128, 20, 16, 24, 36, 36, 18, 24, 32, 40, 12, 42, 20, 72, 22, 46, 64, 294, 100, 32, 24, 52, 162, 40, 48, 36, 28, 58, 16, 60, 30, 108, 512, 48, 20, 66, 32, 44, 24

Offset: 1

Author

Haris Ziko, Jun 27 2019

Keywords

• nonn

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)

Examples

			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.
		

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)

Crossrefs

Cf. A000010(phi), A026741, A003557, A046790, A049225, A135616.

Programs

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]};

Formula

Conjecture: a(n) = A135616(n)/n.

Conjecture: a(n) = phi(n)*A003557(n / gcd(n,2)). - Andrew Howroyd, Aug 20 2019