Sieving Procedures on a Digital Computer

ABSTRACT

Many sequences are most efficiently generated on a digital computer with a sieving procedure in which one represents in the main memory of the machine a set of elements known to contain the desired sequence and then systematically sieves out elements not in the desired sequence. In this expository paper, the technical aspects of programming such sieves are discussed. Special attention is given to the most efficient methods of representing sets in the main memory of the machine as well as the programming difficulties encountered when sieving on these sets. The paper concludes with a discussion of four examples in which sieving procedures were employed.

REFERENCES

• 1: BRIGGS, W. E. Prime-like sequences generated by a sieve process. Duke Math. J. 50 (1963), 297-312.
• 2: BUSCHMAN, R. G., AND WUNDERLICtt, M.C. Sieves with generalized intervals. Boll. Un. Mat. Ital. (to appear).
• 3: -- AND --. Sieve generated sequences with translated intervals. Can. J. Math. (to appear).
• 4: CANTOR, D. G., ESTRIN, G., FRAENKEL, A. S., AND TURN, R. A very high-speed digital number sieve. Math. Comput. 16, 78 (April 1962), 141-154.
• 5: CHILTON, B., AND WUNDERLICH, M.C. The enumeration of nine-gons. (In preparation.)
• 6: COHN, JOHN H.E. Square Fibonacci numbers. Fibonacci Quart. 2 (1964), 109-113.
• 7: ERDOS, P., AND JAROTINSKY, E. On sequences generated by a sieving process. Ned. Akad. Wetensch. Indag. Math. 61 (1958), 115-128.
• 8: GARDINER, V., LAZARUS, R., METROPOLIS, M., AND ULAM, S. On certain sequences of integers defined by sieves. Math. Mag. 29 (1955--1956), 117-122.
• 9: GOLOMB, S. W., AND WEIGH, L.R. On the enumeration of polygons. Amer. Math. Mort. 67 (1960), 349-353.
• 10: HALL, F.B. Boolean implicants by the binary sieve method. Comm. Elec. 58 (Jan. 1962), 709-713.
• 11: HAWXINS, D., AND BRIGGS, W.E. The lucky number theorem. Math. Mag. 31 (1957- 1958), 277-280.
• 12: LEHMER, D.H. The machine tools of combinatories. Chap. 1 in Applied Combinatorial Mathematics. U. of California Eng. and Phys. Sci. Ext. Series, Berkeley, Calif., 1964.
• 13: MULLER, PETER. On certain properties of unique summation sequences. (In preparation.)
• 14: SHANKS, DANIEL. A sieve method for factoring numbers of the formms- 1. Math. Tables Aids Comput. 13 (1959), 78-86.
• 15: SrRYKW'rCH, D. Research on prime numbers on a binary computer. Revs. Franc. Traitement de l'Inf. 6, 3 (July 1963), 171-173 (in French). See 6780, Computing Revs. 5, 6 (1964), 394-395.
• 16: WELLS, MARK Aspects of language design for combinatorial computing. Trans. TEEB EC-18 (1964), 431-438.
• 17: WUNDERLICH, M C. Sieve generated sequences. Can. J. Math. 18 (1966), 291-299.
• 18: --. Oa the non-existence of F{bonacci squares. Math. Comput. 17 (1963), 455--457.
• 19: -- AND BRIGGS, W.E. Second and third term approximations of sieve generated sequences. Ill. or . Math. (to appear).
• 20: CILTON, B. The 202 octagons. Math. Mag. (to appear).

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Procedures, functions, and subroutines

General Terms:
Performance, Theory