Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

A sieve method for factoring numbers of the form $ n\sp{2}+1$


Author: Daniel Shanks
Journal: Math. Comp. 13 (1959), 78-86
MSC: Primary 65.00; Secondary 10.00
DOI: https://doi.org/10.1090/S0025-5718-1959-0105784-2
MathSciNet review: 0105784
Full-text PDF

References | Similar Articles | Additional Information

References [Enhancements On Off] (What's this?)

  • [1] L. E. Dickson, History of the Theory of Numbers, Stechert, New York, 1934, v. 1, Ch. XVI. For example, Euler (1752) gave $ P(1500) = 161$ See also D.H. Lehmer, Guide to Tables in the Theory of Numbers, National Research Council, Washington, D. C., 1941, p. 31-32 and p. 45.
  • [2] The most extensive table of all the prime factors of $ {n^2} + 1$ ( up to $ n = 31,622$) is the unpublished table of J. W. Wrench, Jr. See UMT 1, MTAC, v. I, 1943, p. 26. Recently a 704 program by the author in collaboration with Dr. Wrench raised this limit to 50,000 for a table of the greatest prime factor. However, we now consider that type of program (with trial divisions) to be superseded by the present sieve method.
  • [3] G. H. Hardy & J. E. Littlewood, ``Partitio numerorum III: On the expression of a number as a sum of primes,'' Acta Math., v. XLIV, 1923, p. 48.
  • [4] A. E. Western, ``Note on the number of primes of the form $ {n^2} + 1$,'' Cambridge Phil. Soc., Proc., v. XXI, 1922, p. 108-109. Western assumes $ P(15000) = 1199$ following Cunningham, who omits $ 2 = {1^2} + 1$. The correct value of $ P(15000)$ is 1200.
  • [5] Fortune, June, 1958, p. 140.
  • [6] John Todd, ``A problem on arc tangent relations,'' American Math Monthly, v. LVI, 1949, p. 517-528. MR 0031496 (11:159d)
  • [7] S. D. Chowla & J. Todd, ``The density of reducible integers,'' Canadian Jour. of Math, v. I, 1949, p. 297-299. The table of $ R(N)$ to $ N = 5000$ has many errors. It indicates $ R(5000) = 1453$. A mimeographed errata sheet later circulated stated $ R(5000) = 1458$, but the correct value is 1467. MR 0030558 (11:14d)
  • [8] John Todd, Table of Arctangents of Rational Numbers, NBS, Applied Math. Series 11, Washington, D. C., 1951. MR 0040796 (12:750e)
  • [10] C. C. MacDuffee, An Introduction to Abstract Algebra, Wiley, New York, 1940, p. 193-202. MR 0003591 (2:241b)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65.00, 10.00

Retrieve articles in all journals with MSC: 65.00, 10.00


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1959-0105784-2
Article copyright: © Copyright 1959 American Mathematical Society

American Mathematical Society