login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 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

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 m-1). 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: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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 23 07:00 EDT 2019. Contains 323508 sequences. (Running on oeis4.)