cp's OEIS Frontend

A096555 Consecutive internal states of the linear congruential pseudo-random number generator RANDU that was used in the IBM Scientific Subroutine Library for IBM System/360 computers in the 1970's.

%I A096555 #36 Oct 16 2024 16:10:44
%S A096555 1,65539,393225,1769499,7077969,26542323,95552217,334432395,
%T A096555 1146624417,1722371299,14608041,1766175739,1875647473,1800754131,
%U A096555 366148473,1022489195,692115265,1392739779,2127401289,229749723,1559239569,845238963,1775695897,899541067,153401569
%N A096555 Consecutive internal states of the linear congruential pseudo-random number generator RANDU that was used in the IBM Scientific Subroutine Library for IBM System/360 computers in the 1970's.
%C A096555 Due to a poor choice of the multiplier the generator fails most 3-d criteria for randomness. 9*a(n-2)-6*a(n-1)+a(n) = 0 mod 2^31. This was first described by George Marsaglia. The animated gif in the link demonstrates the deficient behavior. The animation shows 10000 points, each of whose coordinate triples (x,y,z) were formed from successive outputs of the generator. From a suitable view angle, it can be seen that these points do not fill the 3-D space, but lie in a few planes parallel to each other.
%D A096555 D. E. Knuth, The Art of Computer Programming Third Edition. Vol. 2 Seminumerical Algorithms. Chapter 3.3.4 The Spectral Test, Page 107. Addison-Wesley 1997.
%H A096555 Alois P. Heinz, <a href="/A096555/b096555.txt">Table of n, a(n) for n = 1..10000</a>
%H A096555 Sarah Belet, <a href="https://web.archive.org/web/20170207170457/http://www.aums.org.au/talks/s_belet/SarahB_Round_the_Twist.pdf">'Round the Twist</a>, Blog Entry, Friday May 16 2014
%H A096555 George Marsaglia, <a href="https://doi.org/10.1073/pnas.61.1.25">Random numbers fall mainly in the planes</a>, Proceedings of the National Academy of Sciences, 61, 25-28, 1968.
%H A096555 Hugo Pfoertner, <a href="/A096555/a096555.gif">Animation showing the deficient 3-d behavior</a>, 2024.
%H A096555 <a href="/index/Ps#PRN">Index entries for sequences related to pseudo-random numbers.</a>
%H A096555 <a href="/index/Rec#order_536870912">Index entries for linear recurrences with constant coefficients</a>, order 536870912.
%F A096555 a(1)=1, a(n) = 65539*a(n-1) mod 2^31. The sequence is periodic with period length 2^29.
%p A096555 a:= proc(n) option remember; `if`(n<2, n,
%p A096555       irem(65539 *a(n-1), 2147483648))
%p A096555     end:
%p A096555 seq(a(n), n=1..30);  # _Alois P. Heinz_, Jun 10 2014
%t A096555 NestList[Mod[#*65539, 2^31] &, 1, 50] (* _Paolo Xausa_, Aug 29 2024 *)
%o A096555 (PARI) a(n)=lift(Mod(65539,2^31)^(n-1)) \\ _Charles R Greathouse IV_, Jan 13 2016
%Y A096555 Cf. A096550-A096561 for other pseudo-random number generators.
%K A096555 nonn,easy
%O A096555 1,2
%A A096555 _Hugo Pfoertner_, Jul 19 2004