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^{2}+1$

Author: Daniel Shanks
Journal: Math. Comp. 13 (1959), 78-86
MSC: Primary 65.00; Secondary 10.00
MathSciNet review: 0105784
Full-text PDF Free Access

References | Similar Articles | Additional Information

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

    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. 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. 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. 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. Fortune, June, 1958, p. 140.
  • John Todd, A problem on arc tangent relations, Amer. Math. Monthly 56 (1949), 517–528. MR 31496, DOI
  • S. D. Chowla and John Todd, The density of reducible integers, Canad. J. Math. 1 (1949), 297–299. MR 30558, DOI
  • John Todd, Table of Arctangents of Rational Numbers, National Bureau of Standards, Applied Mathematics Series, No. 11, United States Government Printing Office, Washington, D. C., 1951. MR 0040796
  • Cyrus Colton MacDuffee, An Introduction to Abstract Algebra, John Wiley & Sons, Inc., New York, 1940. MR 0003591

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

Article copyright: © Copyright 1959 American Mathematical Society