

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, 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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

2,3


COMMENTS

The periods of these output sequences need to be known when designing LCGbased pseudorandom number generators. The period of an LCG output is always 1 when a = 1, always 2 when a = m1 and maximal (i.e. m1) 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


LINKS

Table of n, a(n) for n=2..70.


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 m1). Then A is the sequence obtained by concatenating the rows of this matrix.


EXAMPLE

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


PROG

(MATLAB) function A = LCG_periods(N); mlist = primes(N); nprimes = length(mlist); A = []; for i = 1:nprimes; m = mlist(i); for a = 1:m1; 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


CROSSREFS

Sequence in context: A122440 A046943 A107728 * A086145 A261070 A249140
Adjacent sequences: A128247 A128248 A128249 * A128251 A128252 A128253


KEYWORD

nonn,tabl


AUTHOR

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


STATUS

approved



