Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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
MathSciNet review: 0105784
Full-text PDF Free Access

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, Amer. Math. Monthly 56 (1949), 517–528. MR 0031496 (11,159d)
  • [7] S. D. Chowla and John Todd, The density of reducible integers, Canadian J. Math. 1 (1949), 297–299. MR 0030558 (11,14d)
  • [8] 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 (12,750e)
  • [10] Cyrus Colton MacDuffee, An Introduction to Abstract Algebra, John Wiley & Sons Inc., New York, 1940. 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: http://dx.doi.org/10.1090/S0025-5718-1959-0105784-2
PII: S 0025-5718(1959)0105784-2
Article copyright: © Copyright 1959 American Mathematical Society