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.

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

Offset: 2

Author

Ross Drewe, May 09 2007, May 11 2007, May 25 2007

Keywords

• nonn
• tabf

Comments

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

Apparently this is A086145 with a top row added. - R. J. Mathar, Jun 14 2008

Examples

			Q =
p(2,1) ..................................... [1]
p(3,1) p(3,2) .............................. [1 2]
p(5,1) p(5,2) p(5,3) p(5,4) ................ [1 4 4 2]
p(7,1) p(7,2) p(7,3) p(7,4) p(7,5) p(7,6) .. [1 3 6 3 6 2]
Therefore A = [1] [1 2] [1 4 4 2] [1 3 6 3 6 2] .....
		

Crossrefs

Cf. A086145.

Programs

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

Formula

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.