Mathematics of Computation

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

Author(s): Chris K. Caldwell; Yves Gallot.
Journal: Math. Comp. 71 (2002), 441-448.
MSC (2000): Primary 11A41; Secondary 11N05, 11A51
Posted: May 11, 2001
Retrieve article in: PDF DVI PostScript
This article is available free of charge

For each prime

, let $p\char93$ be the product of the primes less than or equal to

. 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 (

) 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.

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 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

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

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: 10.1090/S0025-5718-01-01315-1
PII: S 0025-5718(01)01315-1
Keywords: Prime numbers, factorial primes, primality proving algorithms
Received by editor(s): March 21, 2000
Posted: 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.
Copyright of article: Copyright 2001, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS