cp's OEIS Frontend

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

%I A308828 #40 Sep 13 2019 21:36:58
%S A308828 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 A308828 162,12,28,8,30,128,20,16,24,36,36,18,24,32,40,12,42,20,72,22,46,64,
%U A308828 294,100,32,24,52,162,40,48,36,28,58,16,60,30,108,512,48,20,66,32,44,24
%N 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].
%C A308828 All such sequences will be cyclic with period length n.
%C A308828 Different values of the integers a and c modulo n will always produce different sequences.
%C A308828 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 A308828 It appears that the set of distinct terms of this sequence gives A049225.
%C A308828 From _Andrew Howroyd_, Aug 21 2019: (Start)
%C A308828 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 A308828      1) c is relatively prime to n;
%C A308828      2) a - 1 is a multiple of p for every prime p dividing n;
%C A308828      3) a - 1 is a multiple of 4 if n is a multiple of 4.
%C A308828 (End)
%D A308828 D. E. Knuth, The Art of Computer Programming, Vol. 3, Random Numbers, Section 3.2.1.2, p. 16.
%H A308828 Andrew Howroyd, <a href="/A308828/b308828.txt">Table of n, a(n) for n = 1..500</a> (terms 1..100 from Jinyuan Wang)
%F A308828 Conjecture: a(n) = A135616(n)/n.
%F A308828 Conjecture: a(n) = phi(n)*A003557(n / gcd(n,2)). - _Andrew Howroyd_, Aug 20 2019
%e A308828 For n = 1:
%e A308828   a = 0, c = 0: [0];
%e A308828   #cycles = 1 -> a(1) = 1.
%e A308828 For n = 5:
%e A308828   a = 1, c = 1: [0, 1, 2, 3, 4];
%e A308828   a = 1, c = 2: [0, 2, 4, 1, 3];
%e A308828   a = 1, c = 3: [0, 3, 1, 4, 2];
%e A308828   a = 1, c = 4: [0, 4, 3, 2, 1];
%e A308828   #cycles = 4 -> a(5) = 4.
%e A308828 For n = 8:
%e A308828   a = 1, c = 1: [0, 1, 2, 3, 4, 5, 6, 7];
%e A308828   a = 1, c = 3: [0, 3, 6, 1, 4, 7, 2, 5];
%e A308828   a = 1, c = 5: [0, 5, 2, 7, 4, 1, 6, 3];
%e A308828   a = 1, c = 7: [0, 7, 6, 5, 4, 3, 2, 1];
%e A308828   a = 5, c = 1: [0, 1, 6, 7, 4, 5, 2, 3];
%e A308828   a = 5, c = 3: [0, 3, 2, 5, 4, 7, 6, 1];
%e A308828   a = 5, c = 5: [0, 5, 6, 3, 4, 1, 2, 7];
%e A308828   a = 5, c = 7: [0, 7, 2, 1, 4, 3, 6, 5];
%e A308828   #cycles = 8 -> a(8) = 8.
%o A308828 (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 A308828 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 A308828 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 A308828 a(n)={my(M=getCycles(n)); matsize(M)[1]};
%Y A308828 Cf. A000010(phi), A026741, A003557, A046790, A049225, A135616.
%K A308828 nonn
%O A308828 1,3
%A A308828 _Haris Ziko_, Jun 27 2019