Algorithm 357: an efficient prime number generator [A1]
Richard C. Singleton · Communications of the ACM · 1969
n, x, t, S); integer n, x, l; integer array S; comment Ising generates n-sequences ($1, "", S,) of zeros and ones where x = ~i~ S~ and t = ~,-~1 I S~+I -S~ I are given.The main idea is to interleave compositions of x and n --x objects and resort to a lexicographic generation of compositions.We call these sequences Ising configurations since we believe they first appeared in the study of the so-called Ising problem (See Hill [1], Ising [2]).The number R(n, x, t) of distinct configurations with fixed n, x, t is well known [1, 2]: Now define a block of l's (or zeros) in the sequence as a set of a maximum number of consecutive l's (or zeros) eventually consisting of a single element.For given n, x, t, the number p of blocks of l's may easily be deduced from t, as well as the number q of blocks of zeros.In fact, a block of l's including either $1 or S, yields one variation and each one of the others yields two variations; hence we get p = q ~ m + 1 when t = 2m + 1 (t odd requires $1 # S,) and either p = m + 1, q = m (S~ = S, = 1), or p = m, q = m+l ($1 = S, = 0) when t--2m.Clearly, there is a 1-1 correspondence between the compositions of x with p parts and the distributions of the x l's into p blocks.And for each distribution of l's, distinct distributions of the n -x zeros into g blocks correspond to distinct configurations.The main body of the algorithm is compose, which generates compositions of an integer x with k parts and stores them in the array L. The role of sort and bisort is to form the final sequence ($1 , ... , S,) from the structure of one-blocks Li and zeroblocks M~.The Ising problem was brought to my attention by Dr. B. Dejon during an informal visit to the IBM Research Laboratory in Zurich.Thanks are also due to Prof. Paul ErdSs for pointing out to me reference [1] and to Prof. A. A. Zykov for correspondence.The procedure was tested on the NCR 4130 of the Labora-tSrio de C£1culo Autom~tico, Universidade do Porto.Thanks are also due to the Director and his Staff.