cp's OEIS Frontend

A128250 LCG periods: periods of the output sequences produced by multiplicative linear congruential generators (LCGs) with prime moduli, for all valid combinations of multiplier and modulus.

%I A128250 #12 Feb 12 2023 10:20:14
%S A128250 1,1,2,1,4,4,2,1,3,6,3,6,2,1,10,5,5,5,10,10,10,5,2,1,12,3,6,4,12,12,4,
%T A128250 3,6,12,2,1,8,16,4,16,16,16,8,8,16,16,16,4,16,8,2,1,18,18,9,9,9,3,6,9,
%U A128250 18,3,6,18,18,18,9,9,2
%N A128250 LCG periods: periods of the output sequences produced by multiplicative linear congruential generators (LCGs) with prime moduli, for all valid combinations of multiplier and modulus.
%C A128250 The periods of these output sequences need to be known when designing LCG-based pseudorandom number generators. The period of an LCG output is always 1 when a = 1, always 2 when a = m-1 and maximal (i.e. m-1) only if a is a totative of m. There is no fast method for finding totative values when m is large. The sample shows the terms generated by the first 8 moduli (i.e. primes from 2 to 19), as generated by: A = LCG_periods(19) (see program).
%C A128250 Apparently this is A086145 with a top row added. - _R. J. Mathar_, Jun 14 2008
%F A128250 Multiplicative LCG for modulus m, multiplier a: x(n+1) == a*x(n) mod m. Additional restriction: a < m (as assumed in many applications). The output sequence for any explicit combination of m,a,x0 is always periodic and the period is independent of x0. Therefore denote the period by p(m,a). Let Q be the lower triangular matrix that is produced by tabulating all p(m,a) values, such that the rows represent m values (successive primes) and the columns represent a values (from 1 to m-1). Then A is the sequence obtained by concatenating the rows of this matrix.
%e A128250 Q =
%e A128250 p(2,1) ..................................... [1]
%e A128250 p(3,1) p(3,2) .............................. [1 2]
%e A128250 p(5,1) p(5,2) p(5,3) p(5,4) ................ [1 4 4 2]
%e A128250 p(7,1) p(7,2) p(7,3) p(7,4) p(7,5) p(7,6) .. [1 3 6 3 6 2]
%e A128250 Therefore A = [1] [1 2] [1 4 4 2] [1 3 6 3 6 2] .....
%o A128250 (MATLAB) function A = LCG_periods(N); mlist = primes(N); nprimes = length(mlist); A = []; for i = 1:nprimes; m = mlist(i); for a = 1:m-1; x = 1; count = 0; while 1; count = count + 1; x = mod(a*x, m); if x == 1; break; end; end; A = [A count]; end; end
%Y A128250 Cf. A086145.
%K A128250 nonn,tabf
%O A128250 2,3
%A A128250 _Ross Drewe_, May 09 2007, May 11 2007, May 25 2007