%I #56 Sep 05 2024 14:26:49
%S 2,3,7,43,13,139,547,607,1033,181,1987,73,2287,29881,13999,17881,
%T 31051,52387,67003,74203,128551,352867,635263,74587,1286773,2271427,
%U 27061,164299,20929,1171,298483,1679143,3229081,3263443,120823,447841
%N Sylvester primes. Yet another proof of the infinity of primes.
%C Sylvester's sequence can be defined recursively S(n) = S(n-1)*(S(n-1) + 1) for n >= 1 starting S(0) = 1. (A000058(n) = S(n) + 1.)
%C Since S(n) and S(n) + 1 have no common divisors, it follows that S(n) has at least one more prime factor than S(n-1), and thus by induction, S(n) has at least n distinct prime factors. This simple and constructive form of Euclid's proof of the infinity of primes was formulated by Filip Saidak (see links).
%C To generate the sequence, select the smallest among the prime factors of S(n) that has not yet been selected. We call the infinite sequence constructed this way the 'Sylvester primes'. The terms, when ordered by size, can be found in A007996; any prime not a Sylvester prime can be located in A096264.
%C As a procedure, the sequence can hardly be described more clearly than in the Maple program below. Compared to other variants (for example A126263), it has the advantage that the primes generated start relatively small.
%H Jens Kruse Andersen, <a href="http://primerecords.dk/sylvester-factors.htm">Factorization of Sylvester's sequence</a>.
%H Chris Caldwell, <a href="https://t5k.org/notes/proofs/infinite/Saidak.html">Filip Saidak's Proof</a>, PrimePages.
%H Filip Saidak, <a href="https://doi.org/10.2307/27642094">A New Proof of Euclid's Theorem</a>, Amer. Math. Monthly, Vol. 113, No. 10 (Dec., 2006), pp. 937-938.
%e The generation of the sequence starts:
%e n, selected, factors of S(n) a(n)
%e [1] {}, {2} -> 2,
%e [2] {2}, {2, 3} -> 3,
%e [3] {2, 3}, {2, 3, 7} -> 7,
%e [4] {2, 3, 7}, {2, 3, 7, 43} -> 43,
%e [5] {2, 3, 7, 43}, {2, 3, 7, 13, 43, 139} -> 13.
%p fact := n -> NumberTheory:-PrimeFactors(n):
%p SylvesterPrimes := proc(len) local p, d, w, n;
%p p := 1; d := {}; w := {};
%p for n from 1 to len do
%p p := p*(p + 1);
%p d := fact(p) minus w;
%p w := w union {min(d)};
%p od end:
%p SylvesterPrimes(8);
%p isSylvesterPrime := proc(p) local s, M;
%p M := NULL: s := 2:
%p while not member(s, [M]) do
%p M := M, s;
%p s := (s^2 + s) mod p;
%p if s = 0 then return true fi;
%p od: false end:
%t Module[{nmax = 20, a = {}, p = 1, f}, Do[p *= p + 1; f = 2; While[MemberQ[a,f] || !Divisible[p, f], f = NextPrime[f]]; AppendTo[a, f], nmax]; a]
%t (* _Paolo Xausa_, Sep 03 2024 *)
%o (Python)
%o from sympy import sieve
%o from itertools import count, islice
%o def smallest_new_primefactor(n, pf):
%o return next(pi for i in count(1) if (pi:=sieve[i]) not in pf and n%pi==0)
%o def agen(): # generator of terms
%o p, d, w, pf = 1, set(), set(), set()
%o while True:
%o p = p*(p + 1)
%o m = smallest_new_primefactor(p, w)
%o w |= {m}
%o yield m
%o print(list(islice(agen(), 20)))
%o # _Michael S. Branicky_, Sep 02 2024 after _Peter Luschny_
%o (SageMath) # Returns the first 24 terms in less than 60 seconds.
%o def SylvesterPrimes(len: int) -> list[int]:
%o M: list[int] = []
%o p = q = 1
%o for n in range(1, len + 1):
%o p = p * (p + 1)
%o pq = p // q
%o for s in Primes():
%o if pq % s == 0 and not s in M:
%o M.append(s)
%o q = q * s
%o print(n, s)
%o break
%o return M
%o SylvesterPrimes(24) # _Peter Luschny_, Sep 05 2024
%Y Cf. A000040, A000058, A007018, A007996, A096264, A014546, A091336, A375545 (indices in P).
%Y Variants: A126263, A367020.
%K nonn,more
%O 1,1
%A _Peter Luschny_, Sep 02 2024
%E a(21)-a(31) from _Michael S. Branicky_, Sep 03 2024
%E a(32) from _Paolo Xausa_, Sep 04 2024
%E a(33)-a(36) from _Peter Luschny_, Sep 05 2024