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
DOI:
https://doi.org/10.1090/S0025-5718-1959-0105784-2
MathSciNet review:
0105784
Full-text 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. 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 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/cjm-1949-025-4
- 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
