Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

On the primality of $n! \pm 1$ and $2 \times 3 \times 5 \times \dotsm \times p \pm 1$


Authors: Chris K. Caldwell and Yves Gallot
Journal: Math. Comp. 71 (2002), 441-448
MSC (2000): Primary 11A41; Secondary 11N05, 11A51
DOI: https://doi.org/10.1090/S0025-5718-01-01315-1
Published electronically: May 11, 2001
MathSciNet review: 1863013
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract:

For each prime $p$, let $p\char93 $ be the product of the primes less than or equal to $p$. We have greatly extended the range for which the primality of $n! \pm 1$ and $p\char93 \pm 1$ are known and have found two new primes of the first form ( $6380!+1, 6917!-1$) and one of the second ($42209\char93 +1$). We supply heuristic estimates on the expected number of such primes and compare these estimates to the number actually found.


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

  • 1. E. Bach and J. Shallit, Algorithmic number theory, Foundations of Computing, vol. I: Efficient Algorithms, The MIT Press, 1996. MR 97e:11157
  • 2. D. Bailey, FFTs in external or hierarchical memory, Journal of Supercomputing 4:1 (1990), 23-35.
  • 3. P. T. Bateman and R. A. Horn, A heuristic asymptotic formula concerning the distribution of prime numbers, Math. Comp. 16 (1962), 363-367. MR 26:6139
  • 4. A. Björn and H. Riesel, Factors of generalized Fermat numbers, Math. Comp. 67 (1998), 441-446. MR 98e:11008
  • 5. A. Borning, Some results for $k! \pm 1$ and $2\cdot 3\cdot 5\cdots p \pm 1$, Math. Comp. 26 (1972), 567-570. MR 46:7133
  • 6. J. Brillhart, D. H. Lehmer, and J. L. Selfridge, New primality criteria and factorizations of $2^m \pm 1$, Math. Comp. 29 (1975), 620-647. MR 52:5546
  • 7. J. P. Buhler, R. E. Crandall, and M. A. Penk, Primes of the form $n! \pm 1$ and $2 \cdot 3\cdot 5 \cdots p \pm 1$, Math. Comp. 38 (1982), 639-643. Corrigendum in Math. Comp. 40 (1983), 727. MR 83c:10006; MR 85b:11119
  • 8. C. Caldwell, On the primality of $n! \pm 1$ and $2 \cdot 3 \cdot 5 \cdots p \pm 1$, Math. Comp. 64 (1995), 889-890. MR 93g:11003
  • 9. H. Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, New York, 1993. MR 94i:11105
  • 10. R. Crandall, Topics in advanced scientific computation, Springer-Verlag, 1996. MR 97g:65005
  • 11. R. Crandall, K. Dilcher, and C. Pomerance, A search for Wieferich and Wilson primes, Math. Comp. 66 (1997), 433-449. MR 97c:11004
  • 12. H. Dubner, The development of a powerful low-cost computer for number theory applications, J. Recreational Math. 18 (1985-86), 81-86.
  • 13. -, Factorial and primorial primes, J. Recreational Math. 19:3 (1987), 197-203.
  • 14. -, A new primorial prime, J. Recreational Math. 21:4 (1989), 276.
  • 15. -, Large Sophie Germain primes, Math. Comp. 65 (1996), 393-396. MR 96d:11008
  • 16. H. Dubner and Y. Gallot, Distribution of generalized Fermat prime numbers, Preprint, 1999.
  • 17. H. Dubner and W. Keller, New Fibonacci and Lucas primes, Math. Comp. 68 (1999), 417-427. MR 99c:11008
  • 18. P. Dusart, The $k^{th}$ prime is greater than $k(\ln k+\ln \ln k-1)$ for $k\geq 2$, Math. Comp. 68 (1999), 411-415. MR 99d:11133
  • 19. A. Ferrier, Les nombres premiers, Librairie Vuibert, Boulevard Saint-Germain, Paris, 1947. MR 9:134f
  • 20. Y. Gallot, Proth.exe: a windows program for finding very large primes, 1999, http://www.utm.edu/research/primes/programs/gallot/.
  • 21. G. H. Hardy and J. E. Littlewood, Some problems of 'partitio numerorum': III: On the expression of a number as a sum of primes, 44 (1922), 1-70, Reprinted in ``Collected Papers of G. H. Hardy,'' Vol. I, Clarendon Press, Oxford, 1966, pp. 561-630. MR 34:1151
  • 22. G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, 5th ed., Oxford University Press, 1979. MR 81i:10002
  • 23. W. Keller, New Cullen primes, Math. Comp. 64 (1995), 1733-1741. Supplement S39-S46. MR 95m:11015
  • 24. D. E. Knuth, The art of computer programming. Volume 1: Fundamental algorithms, Addison-Wesley, 1975, 2nd edition. MR 51:14624
  • 25. M. Kraitchik, Introduction à la théorie des nombres, Gauthier-Villars, Paris, 1952, pp. 2, 8. MR 14:525a
  • 26. P Mihailescu and C. Nash, Binary tree evaluation method for Lucas-Lehmer primality tests, preprint, 1999.
  • 27. C. Nash, 42209#+1 is prime, personal communication to the authors, May 1999.
  • 28. I. Peterson, Dubner's primes, Science News 144:21 (1993), 331. MR 85c:11010
  • 29. F. Proth, Théorèmes sur Les Nombres Premiers, C. R. Acad. Sci. Paris 85 (1877), 329-331.
  • 30. M. R. Schroeder, Where is the next Mersenne prime hiding?, Math. Intelligencer 5:3 (1983), 31-33. MR 85c:11010
  • 31. D. Shanks, Solved and unsolved problems in number theory, 2nd ed., Chelsea, New York, 1978. MR 80e:10003
  • 32. W. Sierpinski, Elementary theory of numbers, Monografie Mat., vol. 42, PWN, Warsaw, 1964, p. 202. MR 31:116
  • 33. M. Templer, On the primality of $k!+1$ and $2*3*5*\cdots*p+1$, Math. Comp. 34 (1980), 303-304. MR 80j:10010
  • 34. W. Vetterling W. Press, S. Teukolsky and B. Flannery, Numerical recipes in C: The art of scientific computing, 2nd ed., Cambridge University Press, 1992. MR 93i:65001b
  • 35. S Wagstaff, Divisors of Mersenne numbers, Math. Comp. 40 (1983), 385-397. MR 84j:10052

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11A41, 11N05, 11A51

Retrieve articles in all journals with MSC (2000): 11A41, 11N05, 11A51


Additional Information

Chris K. Caldwell
Affiliation: Department of Mathematics and Computer Science, University of Tennessee at Martin, Martin, Tennessee 38238
Email: caldwell@utm.edu

Yves Gallot
Affiliation: Department of Mathematics and Computer Science, University of Tennessee at Martin, Martin, Tennessee 38238
Address at time of publication: 12 bis rue Perrey, 31400 Toulouse, France
Email: galloty@wanadoo.fr

DOI: https://doi.org/10.1090/S0025-5718-01-01315-1
Keywords: Prime numbers, factorial primes, primality proving algorithms
Received by editor(s): March 21, 2000
Published electronically: May 11, 2001
Additional Notes: The first author would like to thank the fellow faculty members who allowed us to use their computers’ idle time over a period of months, especially David Ray and John Schommer.
Article copyright: © Copyright 2001 American Mathematical Society

American Mathematical Society