A sieve method for factoring numbers of the form $n^{2}+1$
Author:
Daniel Shanks
Journal:
Math. Comp. 13 (1959), 7886
MSC:
Primary 65.00; Secondary 10.00
DOI:
https://doi.org/10.1090/S00255718195901057842
MathSciNet review:
0105784
Fulltext PDF Free Access
References  Similar Articles  Additional Information

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. 3132 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. 108109. 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 https://doi.org/10.2307/2305526
 S. D. Chowla and John Todd, The density of reducible integers, Canad. J. Math. 1 (1949), 297â€“299. MR 30558, DOI https://doi.org/10.4153/cjm19490254
 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
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