A096264 -id:A096264 - cp's OEIS frontend

A007996 Primes that divide at least one term of Sylvester's sequence s = A000058: s(n+1) = s(n)^2 - s(n) + 1, s(0) = 2.

2, 3, 7, 13, 43, 73, 139, 181, 547, 607, 1033, 1171, 1459, 1861, 1987, 2029, 2287, 2437, 4219, 4519, 6469, 7603, 8221, 9829, 12763, 13147, 13291, 13999, 15373, 17881, 17977, 19597, 20161, 20479, 20641, 20857, 20929, 21661, 23689, 23773, 27031

Offset: 1

Bennett Battaile (bennett.battaile(AT)autodesk.com)

nonn

Or, let S_1 = [2] and let S_{n+1} = list formed by sorting the union of S_n together with all prime factors of 1 + Product_i S_n(i) into increasing order; sequence is limit as n -> infinity of S_n.
Prime divisors of the terms of Sylvester's sequence A000058. - Max Alekseyev, Jan 03 2004. Also of A007018. - N. J. A. Sloane, Jan 27 2007
Because all terms of the sequence s(n) are coprime, a prime can divide at most one term. Odoni shows that primes p > 3 in this sequence must satisfy p = 1 (mod 6). - T. D. Noe, Sep 25 2010
See A180871(n) for the index of the first term of A000058 (this is one less than the index of the s-sequence) divisible by a(n). - M. F. Hasler, Apr 24 2014

Max Alekseyev, Table of n, a(n) for n = 1..12046 (first 8181 terms are also given at the Andersen link)
J. K. Andersen, Factorization of Sylvester's sequence
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, 2012 - From N. J. A. Sloane, Jun 13 2012
R. W. K. Odoni, On the prime divisors of the sequence w_{n+1} = 1+w_1 ... w_n, J. London Math. Soc. 32 (1985), 1-11.
Filip Saidak, A New Proof of Euclid's Theorem, Amer. Math. Monthly, Dec 2006
Eric Weisstein's World of Mathematics, Sylvester's sequence

The missing primes form A096264.
Cf. A014546, A091335, A091336.
Cf. A180871 (k such that a(n) divides A000058(k)).
Cf. A323605 (smallest prime dividing A000058(n)).

n := 1; for p do if isprime(p) then x := 2 mod p; S := {}; while not member(x,S) do if x=0 then a[n] := p; n := n+1; break; fi; S := S union {x}; x := (x^2-x+1) mod p; od; fi; od;

t={}; p=1; While[Length[t]<100, p=NextPrime[p]; s=Mod[2,p]; k=0; modSet={}; While[s>0 && !MemberQ[modSet,s], AppendTo[modSet,s]; k++; s=Mod[s^2-s+1,p]]; If[s==0, AppendTo[t,{p,k}]]]; Transpose[t][[1]] (* T. D. Noe, Sep 25 2010 *)

is(n)=my(k=Mod(2,n)); for(i=1, n, k=(k-1)*k+1; if(k==0, return(isprime(n)))); n==2 \\ Charles R Greathouse IV, Sep 30 2015

More terms from Max Alekseyev, Jan 03 2004
Entry revised by N. J. A. Sloane, Jan 28 2007
Definition corrected (following a remark by Don Reble) by M. F. Hasler, Apr 24 2014

A375543 Sylvester primes. Yet another proof of the infinity of primes.

Original entry on oeis.org

2, 3, 7, 43, 13, 139, 547, 607, 1033, 181, 1987, 73, 2287, 29881, 13999, 17881, 31051, 52387, 67003, 74203, 128551, 352867, 635263, 74587, 1286773, 2271427, 27061, 164299, 20929, 1171, 298483, 1679143, 3229081, 3263443, 120823, 447841, 2408563, 333457, 30241, 4219

Offset: 1

Peter Luschny, Sep 02 2024

nonn

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.)
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).
To generate the sequence, select the smallest unchosen prime factor from all prime factors of S(0), S(1), ..., S(n-1). 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.
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.

			The generation of the sequence starts:
  n   selected       factors of S(i), i<n       a(n)
  [1] {}             {2}                     ->   2,
  [2] {2}            {2, 3}                  ->   3,
  [3] {2, 3}         {2, 3, 7}               ->   7,
  [4] {2, 3, 7}      {2, 3, 7, 43}           ->  43,
  [5] {2, 3, 7, 43}  {2, 3, 7, 13, 43, 139}  ->  13.

Jens Kruse Andersen, Factorization of Sylvester's sequence.
Chris Caldwell, Filip Saidak's Proof, PrimePages.
Filip Saidak, A New Proof of Euclid's Theorem, Amer. Math. Monthly, Vol. 113, No. 10 (Dec., 2006), pp. 937-938.

Cf. A000040, A000058, A007018, A007996, A014546, A091336, A096264, A375545 (indices in P).

Variants: A126263, A367020.

fact := n -> NumberTheory:-PrimeFactors(n):
SylvesterPrimes := proc(len) local p, d, w, n;
p := 1; d := {}; w := {};
for n from 1 to len do
   p := p*(p + 1);
   d := fact(p) minus w;
   w := w union {min(d)};
od end:
SylvesterPrimes(8);
isSylvesterPrime := proc(p) local s, M;
M := NULL: s := 2:
while not member(s, [M]) do
   M := M, s;
   s := (s^2 + s) mod p;
   if s = 0 then return true fi;
od: false end:

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] (* Paolo Xausa, Sep 03 2024 *)

from sympy import sieve
from itertools import count, islice
def smallest_new_primefactor(n, pf):
    return next(pi for i in count(1) if (pi:=sieve[i]) not in pf and n%pi==0)
def agen(): # generator of terms
    p, d, w, pf = 1, set(), set(), set()
    while True:
        p = p*(p + 1)
        m = smallest_new_primefactor(p, w)
        w |= {m}
        yield m
print(list(islice(agen(), 20)))
# Michael S. Branicky, Sep 02 2024 after Peter Luschny

# Returns the first 24 terms in less than 60 seconds.
def SylvesterPrimes(len: int) -> list[int]:
    M: list[int] = []
    p = q = 1
    for n in range(1, len + 1):
        p = p * (p + 1)
        pq = p // q
        for s in Primes():
            if pq % s == 0 and not s in M:
                M.append(s)
                q = q * s
                print(n, s)
                break
    return M
SylvesterPrimes(24)  # Peter Luschny, Sep 05 2024

a(21)-a(31) from Michael S. Branicky, Sep 03 2024
a(32) from Paolo Xausa, Sep 04 2024
a(33)-a(36) from Peter Luschny, Sep 05 2024
a(37)-a(40) from Jinyuan Wang, Jul 25 2025

cp's OEIS Frontend

A007996 Primes that divide at least one term of Sylvester's sequence s = A000058: s(n+1) = s(n)^2 - s(n) + 1, s(0) = 2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions