A006862 Euclid numbers: 1 + product of the first n primes.

2, 3, 7, 31, 211, 2311, 30031, 510511, 9699691, 223092871, 6469693231, 200560490131, 7420738134811, 304250263527211, 13082761331670031, 614889782588491411, 32589158477190044731, 1922760350154212639071, 117288381359406970983271, 7858321551080267055879091

Offset: 0

Author

Simon Plouffe and N. J. A. Sloane

Keywords

• nonn
• nice
• easy

Comments

It is an open question whether all terms of this sequence are squarefree.

a(n) is the smallest x > 1 such that x^prime(n) == 1 (mod prime(i)) i=1,2,3,...,n-1. - Benoit Cloitre, May 30 2002

Numbers n such that n/phi(n-1) is a record. - Arkadiusz Wesolowski, Nov 22 2012

Nyblom (theorem 2.3) proves that this sequence contains no proper powers, e.g., is a subsequence of A007916. - Charles R Greathouse IV, Mar 02 2016

It is an open question if there are an infinite number of prime Euclid numbers. - Mike Winkler, Feb 05 2017

These numbers are not pairwise relatively prime; the first example is gcd(a(7), a(17)) = 277. Also gcd(a(47), a(131)) = 1051, which is probably the second example (wrt. greater index which is here 131). It is easy to find other primes like 277 and 1051. - Jeppe Stig Nielsen, Mar 24 2017

Subsequence of A048103. Proof: For all primes p, when i >= A000720(p), neither p itself nor p^p divides a(i), but neither does p^p divide a(i) when i < A000720(p), as p^p > 1 + A034386(p). - Antti Karttunen, Nov 17 2024

Examples

			It is a universal convention that an empty product is 1 (just as an empty sum is 0), and since this sequence has offset 0, the first term is 1+1 = 2. - _N. J. A. Sloane_, Dec 02 2015
		

References

• John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See p. 134.
• J.-M. De Koninck, Ces nombres qui nous fascinent, Entry 211, p. 61, Ellipses, Paris 2008.
• R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
• F. Smarandache, Properties of numbers, Arizona State University Special Collections, 1973.
• I. Vardi, Computational Recreations in Mathematica, Addison-Wesley, 1991, sections 5.1 and 5.2.
• S. Wagon, Mathematica in Action, Freeman, NY, 1991, p. 35.

Links

• Derek Maciel, Table of n, a(n) for n = 0..348 (first 101 terms from T. D. Noe)
• S. W. Golomb, The evidence for Fortune's conjecture, Math. Mag. 54 (1981), 209-210.
• H. Ibstedt, A Few Smarandache Sequences, Smarandache Notions Journal, Vol. 8, No. 1-2-3, 1997, 170-183.
• R. Mestrovic, Euclid's theorem on the infinitude of primes: a historical survey of its proofs (300 BC--2012) and another new proof, arXiv preprint arXiv:1202.3670 [math.HO], 2012.
• Hisanori Mishima, Factorizations of many number sequences
• Michael A. Nyblom, On the construction of a family of almost power free sequences, Fibonacci Quart. 46/47 (2008/2009), no. 4, 366-368.
• Shubhankar Paul, Ten Problems of Number Theory, International Journal of Engineering and Technical Research (IJETR), ISSN: 2321-0869, Volume-1, Issue-9, November 2013.
• Eric Weisstein's World of Mathematics, Euclid Number
• Eric Weisstein's World of Mathematics, Fortunate Prime
• R. G. Wilson v, Explicit factorizations

Crossrefs

Cf. A005867, A007916, A014545, A018239 (primes in sequence), A034386, A057588, A377871.

Subsequence of A048103.

Programs

Magma

[2] cat [&*PrimesUpTo(p)+1: p in PrimesUpTo(70)]; // Vincenzo Librandi, Dec 03 2015

Maple

with(numtheory): A006862 := proc(n) local i; if n=0 then 2 else 1+product('ithprime(i)','i'=1..n); fi; end;
# second Maple program:
a:= proc(n) option remember; `if`(n=0, 2,
      1+ithprime(n)*(a(n-1)-1))
    end:
seq(a(n), n=0..20);  # Alois P. Heinz, Feb 06 2021

Mathematica

Table[Product[Prime[k], {k, 1, n}] + 1, {n, 1, 18}]
1 + FoldList[Times, 1, Prime@ Range@ 19] (* Harvey P. Dale, Dec 02 2015 and modified by Robert G. Wilson v, Mar 25 2017 *)

PARI

a(n)=my(v=primes(n)); prod(i=1,#v,v[i])+1 \\ Charles R Greathouse IV, Nov 20 2012

Python

from sympy import primorial
def A006862(n):
    if n == 0: return 2
    else: return 1 + primorial(n) # Karl-Heinz Hofmann, Aug 21 2024

Formula

a(n) = A002110(n) + 1.

For n >= 1, a(n) = A057588(n) + 2. - Antti Karttunen, Nov 17 2024