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.
Original entry on oeis.org
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)
- 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
-
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
A091335
Number of prime divisors of n-th term of Sylvester's sequence A000058.
Original entry on oeis.org
1, 1, 1, 1, 2, 1, 4, 4, 3, 5, 4
Offset: 0
a(8) = 3 because A000058(8) = 5295435634831 * 31401519357481261 * 77366930214021991992277 is a product of 3 primes.
a(9) = 5 because A000058(9) = 181 * 1987 * 112374829138729 * 114152531605972711 * 35874380272246624152764569191134894955972560447869169859142453622851 is the product of 5 prime factors
a(10) = 4 because A000058(10) = 2287 * 2271427 * 21430986826194127130578627950810640891005487 * P156 is the product of 4 prime factors.
Here P156 = 24605022397522123277426691306421099608611770732459695261246331125\
73460100430857224101455594897691626456909430029315374035313628946949460093682\
49974883220589.
- Ilan Vardi, "Are All Euclid Numbers Squarefree?" and "PowerMod to the Rescue", Sections 5.1 and 5.2 in Computational Recreations in Mathematica. Reading, MA: Addison-Wesley, pp. 82-89, 1991.
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
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.
-
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
Showing 1-3 of 3 results.
Comments