A096551 Consecutive internal states of a linear congruential pseudo-random number generator with a parameter proposed by George Marsaglia as a "candidate for the best of all multipliers".

1, 69069, 475559465, 2801775573, 1790562961, 3104832285, 4238970681, 2135332261, 381957665, 1744831853, 1303896393, 1945705589, 2707602097, 4198202557, 3820321881, 201201733, 2583294017, 4003049741, 2417848425, 1454463253, 3332335313, 2360275549, 2093206905, 2813570789

Offset: 1

Author

Hugo Pfoertner, Jul 18 2004

Keywords

• nonn
• easy

Comments

The period length of 2^30 is only achieved if the starting value a(1) is odd. Even starting values lead to shorter periods, i.e., a starting value that is a multiple of 2^k leads to a sequence with period length 2^(30-k). - Hugo Pfoertner, Nov 21 2024

References

• D. E. Knuth, The Art of Computer Programming Third Edition. Vol. 2 Seminumerical Algorithms. Chapter 3.3.4 The Spectral Test, Page 108. Addison-Wesley 1997.
• G. Marsaglia, The structure of linear congruential sequences, in Applications of Number Theory to Numerical Analysis, (edited by S. K. Zaremba), Academic Press, New York, 249-286, 1972.

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..10000
• George S. Fishman, Multiplicative Congruential Random Number Generators with Modulus 2^beta: An Exhaustive Analysis for beta = 32 and a Partial Analysis for beta = 48, Math. Comp., 54, 189 (1990), 331-344.
• Index entries for sequences related to pseudo-random numbers.

Crossrefs

Cf. A096550-A096561 (for other pseudo-random number generators).

Cf. A385127 (same multiplier).

Programs

Maple

a:= proc(n) option remember; `if`(n<2, n,
      irem(69069 *a(n-1), 4294967296))
    end:
seq(a(n), n=1..30);  # Alois P. Heinz, Jun 10 2014

Mathematica

NestList[Mod[#*69069, 2^32] &, 1, 50] (* Paolo Xausa, Aug 29 2024 *)

PARI

a(n)=lift(Mod(69069,2^32)^(n-1)) \\ Charles R Greathouse IV, Jan 14 2016

Formula

a(1)=1, a(n) = 69069 * a(n-1) mod 2^32. The sequence is periodic with period length 2^30. - corrected by Hugo Pfoertner, Aug 10 2011

a(n) == 1 (mod 4). Hugo Pfoertner, Nov 21 2024