A sieve method for factoring numbers of the form $n^{2}+1$
HTML articles powered by AMS MathViewer
- by Daniel Shanks PDF
- Math. Comp. 13 (1959), 78-86 Request permission
References
-
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 10.2307/2305526
- S. D. Chowla and John Todd, The density of reducible integers, Canad. J. Math. 1 (1949), 297–299. MR 30558, DOI 10.4153/cjm-1949-025-4
- John Todd, Table of Arctangents of Rational Numbers, National Bureau of Standards Applied Mathematics Series, No. 11, U.S. 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
Additional Information
- © Copyright 1959 American Mathematical Society
- 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