A128250 - OEIS

%I #12 Feb 12 2023 10:20:14

%S 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 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 18,3,6,18,18,18,9,9,2

%N 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 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 Apparently this is A086145 with a top row added. - _R. J. Mathar_, Jun 14 2008

%F 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 Q =

%e p(2,1) ..................................... [1]

%e p(3,1) p(3,2) .............................. [1 2]

%e p(5,1) p(5,2) p(5,3) p(5,4) ................ [1 4 4 2]

%e 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 Therefore A = [1] [1 2] [1 4 4 2] [1 3 6 3 6 2] .....

%o (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 Cf. A086145.

%K nonn,tabf

%O 2,3

%A _Ross Drewe_, May 09 2007, May 11 2007, May 25 2007