A308828 - OEIS

%I #40 Sep 13 2019 21:36:58

%S 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,

%T 162,12,28,8,30,128,20,16,24,36,36,18,24,32,40,12,42,20,72,22,46,64,

%U 294,100,32,24,52,162,40,48,36,28,58,16,60,30,108,512,48,20,66,32,44,24

%N 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].

%C All such sequences will be cyclic with period length n.

%C Different values of the integers a and c modulo n will always produce different sequences.

%C 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.

%C It appears that the set of distinct terms of this sequence gives A049225.

%C From _Andrew Howroyd_, Aug 21 2019: (Start)

%C 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:

%C      1) c is relatively prime to n;

%C      2) a - 1 is a multiple of p for every prime p dividing n;

%C      3) a - 1 is a multiple of 4 if n is a multiple of 4.

%C (End)

%D D. E. Knuth, The Art of Computer Programming, Vol. 3, Random Numbers, Section 3.2.1.2, p. 16.

%H Andrew Howroyd, <a href="/A308828/b308828.txt">Table of n, a(n) for n = 1..500</a> (terms 1..100 from Jinyuan Wang)

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

%F Conjecture: a(n) = phi(n)*A003557(n / gcd(n,2)). - _Andrew Howroyd_, Aug 20 2019

%e For n = 1:

%e   a = 0, c = 0: [0];

%e   #cycles = 1 -> a(1) = 1.

%e For n = 5:

%e   a = 1, c = 1: [0, 1, 2, 3, 4];

%e   a = 1, c = 2: [0, 2, 4, 1, 3];

%e   a = 1, c = 3: [0, 3, 1, 4, 2];

%e   a = 1, c = 4: [0, 4, 3, 2, 1];

%e   #cycles = 4 -> a(5) = 4.

%e For n = 8:

%e   a = 1, c = 1: [0, 1, 2, 3, 4, 5, 6, 7];

%e   a = 1, c = 3: [0, 3, 6, 1, 4, 7, 2, 5];

%e   a = 1, c = 5: [0, 5, 2, 7, 4, 1, 6, 3];

%e   a = 1, c = 7: [0, 7, 6, 5, 4, 3, 2, 1];

%e   a = 5, c = 1: [0, 1, 6, 7, 4, 5, 2, 3];

%e   a = 5, c = 3: [0, 3, 2, 5, 4, 7, 6, 1];

%e   a = 5, c = 5: [0, 5, 6, 3, 4, 1, 2, 7];

%e   a = 5, c = 7: [0, 7, 2, 1, 4, 3, 6, 5];

%e   #cycles = 8 -> a(8) = 8.

%o (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;};

%o 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_;};

%o 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))};

%o a(n)={my(M=getCycles(n)); matsize(M)[1]};

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

%K nonn

%O 1,3

%A _Haris Ziko_, Jun 27 2019