login
Euclid numbers: 1 + product of the first n primes.
(Formerly M2698)
66

%I M2698 #94 Aug 21 2024 12:26:33

%S 2,3,7,31,211,2311,30031,510511,9699691,223092871,6469693231,

%T 200560490131,7420738134811,304250263527211,13082761331670031,

%U 614889782588491411,32589158477190044731,1922760350154212639071,117288381359406970983271,7858321551080267055879091

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

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

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

%C Numbers n such that n/phi(n-1) is a record. - _Arkadiusz Wesolowski_, Nov 22 2012

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

%C It is an open question if there are an infinite number of prime Euclid numbers. - _Mike Winkler_, Feb 05 2017

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

%D J.-M. De Koninck, Ces nombres qui nous fascinent, Entry 211, p. 61, Ellipses, Paris 2008.

%D R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D F. Smarandache, Properties of numbers, Arizona State University Special Collections, 1973.

%D I. Vardi, Computational Recreations in Mathematica, Addison-Wesley, 1991, sections 5.1 and 5.2.

%D S. Wagon, Mathematica in Action, Freeman, NY, 1991, p. 35.

%H Derek Maciel, <a href="/A006862/b006862.txt">Table of n, a(n) for n = 0..348</a> (first 101 terms from T. D. Noe)

%H S. W. Golomb, <a href="http://www.jstor.org/stable/2689634">The evidence for Fortune's conjecture</a>, Math. Mag. 54 (1981), 209-210.

%H H. Ibstedt, <a href="http://vixra.org/abs/1403.0853">A Few Smarandache Sequences</a>, Smarandache Notions Journal, Vol. 8, No. 1-2-3, 1997, 170-183.

%H R. Mestrovic, <a href="http://arxiv.org/abs/1202.3670">Euclid's theorem on the infinitude of primes: a historical survey of its proofs (300 BC--2012) and another new proof</a>, arXiv preprint arXiv:1202.3670 [math.HO], 2012.

%H Hisanori Mishima, <a href="http://www.asahi-net.or.jp/~KC2H-MSM/mathland/matha1/matha102.htm">Factorizations of many number sequences</a>

%H Michael A. Nyblom, <a href="http://www.fq.math.ca/Papers1/46_47-4/Nyblom.pdf">On the construction of a family of almost power free sequences</a>, Fibonacci Quart. 46/47 (2008/2009), no. 4, 366-368.

%H Shubhankar Paul, <a href="https://www.erpublication.org/published_paper/IJETR011954.pdf">Ten Problems of Number Theory</a>, International Journal of Engineering and Technical Research (IJETR), ISSN: 2321-0869, Volume-1, Issue-9, November 2013.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/EuclidNumber.html">Euclid Number</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/FortunatePrime.html">Fortunate Prime</a>

%H R. G. Wilson v, <a href="/A038507/a038507.txt">Explicit factorizations</a>

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

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

%p with(numtheory): A006862 := proc(n) local i; if n=0 then 2 else 1+product('ithprime(i)','i'=1..n); fi; end;

%p # second Maple program:

%p a:= proc(n) option remember; `if`(n=0, 2,

%p 1+ithprime(n)*(a(n-1)-1))

%p end:

%p seq(a(n), n=0..20); # _Alois P. Heinz_, Feb 06 2021

%t Table[Product[Prime[k], {k, 1, n}] + 1, {n, 1, 18}]

%t 1 + FoldList[Times, 1, Prime@ Range@ 19] (* _Harvey P. Dale_, Dec 02 2015 and modified by _Robert G. Wilson v_, Mar 25 2017 *)

%o (PARI) a(n)=my(v=primes(n)); prod(i=1,#v,v[i])+1 \\ _Charles R Greathouse IV_, Nov 20 2012

%o (Magma) [2] cat [&*PrimesUpTo(p)+1: p in PrimesUpTo(70)]; // _Vincenzo Librandi_, Dec 03 2015

%o (Python)

%o from sympy import primorial

%o def A006862(n):

%o if n == 0: return 2

%o else: return 1 + primorial(n) # _Karl-Heinz Hofmann_, Aug 21 2024

%Y Cf. A014545, A057588, A018239 (primes), A005867, A007916.

%K nonn,nice,easy

%O 0,1

%A _Simon Plouffe_ and _N. J. A. Sloane_