A000058 -id:A000058 - 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

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

Max Alekseyev, Dec 30 2003

All numbers less than 2.5*10^15 in Sylvester's sequence are squarefree and no squareful numbers in this sequence are known (Vardi 1991).

a(n) is currently unknown for all n > 10. - Jens Kruse Andersen, Jun 19 2014

			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.

Jens Kruse Andersen, Factorization of Sylvester's sequence
Eric Weisstein's World of Mathematics, Sylvester's sequence

Cf. A000058, A001221, A014546, A091336.

PrimeNu[NestList[#^2 - # + 1 &, 2, 7]] (* G. C. Greubel, May 09 2017 *)

a(n) = A001221(A000058(n)).

a(9) from T. D. Noe, Dec 31 2003

a(10) from Ken Takusagawa, Apr 11 2006

A126263 List of primes generated by factoring successive integers in Sylvester's sequence (A000058).

Original entry on oeis.org

2, 3, 7, 43, 13, 139, 3263443, 547, 607, 1033, 31051, 29881, 67003, 9119521, 6212157481, 5295435634831, 31401519357481261, 77366930214021991992277, 181, 1987, 112374829138729, 114152531605972711, 35874380272246624152764569191134894955972560447869169859142453622851

Offset: 1

Howard L. Warth (hlw6c2(AT)umr.edu), Dec 22 2006

nonn

The list is infinite and no term repeats since Sylvester's sequence is an infinite coprime sequence.

However, it appears to be unknown whether all terms in A000058 are squarefree. - Jeppe Stig Nielsen, Apr 23 2020

			2 = 2, 3 = 3, 7 = 7, 43 = 43, 1807 = 13 * 139, 3263443 = 3263443,
10650056950807 = 547 * 607 * 1033 * 31051,
113423713055421844361000443 = 29881 * 67003 * 9119521 * 6212157481,
12864938683278671740537145998360961546653259485195807 = 5295435634831 * 31401519357481261 * 77366930214021991992277.
165506647324519964198468195444439180017513152706377497841851388766535868639572406808911988131737645185443 = 181 * 1987 * 112374829138729 * 114152531605972711 * 35874380272246624152764569191134894955972560447869169859142453622851. - _Jonathan Sondow_, Jan 26 2014

Barry Mazur and William Stein, Prime Numbers and the Riemann Hypothesis, Cambridge University Press, 2016. See p. 9.

Ray Chandler, Table of n, a(n) for n = 1..28 (first 27 terms from William Stein)
J. K. Andersen, Factorization of Sylvester's sequence.
Filip Saidak, Proof of Euclid's Theorem.
Filip Saidak, A New Proof of Euclid's Theorem, Amer. Math. Monthly, Dec. 2006.

Cf. A000058, A007996, A236433.

a(0):=2; for n from 0 to 8 do a(n+1):=a(n)^2-a(n)+1;ifactor(%); od;

Flatten[FactorInteger[NestList[#^2 - # + 1 &, 2, 8]][[All, All, 1]]] (* Paolo Xausa, Sep 09 2024 *)

v=[2]; for(i=1,10, v=concat(v,Set(factor(vecprod(v)+1)[,1]))); v \\ Charles R Greathouse IV, Oct 02 2014

v = [2]
for n in range(12):
    v.append(v[-1]^2-v[-1]+1)
    print(prime_divisors(v[-1])) # William Stein, Aug 26 2009

Offset corrected by N. J. A. Sloane, Aug 20 2009
a(23)-a(27) from William Stein (wstein(AT)gmail.com), Aug 20 2009, Aug 21 2009
a(17) corrected by D. S. McNeil, Dec 10 2010
b-file updated at the suggestion of Hans Havermann by Ray Chandler, Feb 27 2015

A180871 Index of term in Sylvester's sequence A000058 divisible by prime A007996(n).

Original entry on oeis.org

0, 1, 2, 4, 3, 11, 4, 9, 6, 6, 6, 29, 64, 42, 9, 59, 10, 80, 39, 103, 140, 41, 137, 53, 69, 146, 104, 14, 92, 15, 117, 199, 75, 98, 316, 233, 28, 92, 281, 44, 136, 26, 258, 7, 38, 6, 176, 126, 74, 59, 89, 61, 45, 79, 13, 448, 119, 180, 290, 184, 348, 502, 508, 161, 7, 265, 229

Offset: 1

T. D. Noe, Sep 25 2010

nonn

Because all terms of Sylvester's sequence are coprime to each other, each prime in A007996 divides only one term of A000058. The Mathematica program computes both the primes in A007996 and the terms in this sequence. Using modular arithmetic, it is easy to see that if prime p divides A000058(k) for some k, then we must have k < p. In practice, k < 5*sqrt(p).

An open problem is to prove that all terms of Sylvester's sequence are squarefree or to find a counterexample. Using the p from A007996 and k found here, it is simple to determine whether A000058(k) = 0 (mod p^2). No p < 10^10 was found to have this property.

			A000058(4) = 1807 = 43 * 181 = A007996(4) * A007996(7), so a(4) = a(7) = 4. - _Jonathan Sondow_, Jan 26 2014

Max Alekseyev, Table of n, a(n) for n = 1..12046 (first 8181 terms are also given at the Andersen link)
Jens Kruse Andersen, Factorization of Sylvester's sequence

Cf. A000058, A007996, A126263.

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][[2]]

A000058(a(n)) == 0 (mod A007996(n)) implies a(n) < A007996(n). - Jonathan Sondow, Jan 26 2014

Definition clarified by Jonathan Sondow, Jan 26 2014

A014546 Primes in Sylvester's sequence A000058.

Original entry on oeis.org

2, 3, 7, 43, 3263443

Offset: 1

Eric W. Weisstein

nonn

No more primes up to 21st recurrence step. - Artur Jasinski, Sep 20 2008
Andersen's page shows that A000058(30) is the first number whose primality is unknown. Thus if a(6) exists it has over 218 million decimal digits.
Since 2019, according to Andersen's updated page, the first term with unknown status is A000058(32), showing that a(6), if it exists, has at least 874250789 digits. So it is safe to say it would be too huge to include. Andersen writes "According to heuristics based on the fast growth, it is unlikely that any s_i above s_5 is prime". Compare this to the possibility of a new Fermat prime A019434. - Jeppe Stig Nielsen, Jan 06 2025

Jens Kruse Andersen, Factorization of Sylvester's sequence
Eric Weisstein's World of Mathematics, Sylvester's Sequence

Cf. A000058, A091335.

a = {}; k = 2; Do[k = k^2 - k + 1; If[PrimeQ[k], AppendTo[a, k]], {n, 1, 15}]; a (* Artur Jasinski, Sep 20 2008 *)

A091336 Number of prime divisors of A000058(n)-1 = A000058(0)...A000058(n-1).

Original entry on oeis.org

0, 1, 2, 3, 4, 6, 7, 11, 15, 18, 23, 27

Offset: 0

Max Alekseyev, Dec 30 2003

All numbers less than 2.5*10^15 in Sylvester's sequence are squarefree and no squareful numbers in this sequence are known (Vardi 1991).

Vardi, I. "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.

Jens Kruse Andersen, Factorization of Sylvester's sequence
Eric Weisstein's World of Mathematics, Sylvester's sequence

Cf. A000058, A091335.

PrimeNu[NestList[#^2 - # + 1 &, 2, 10] - 1] (* G. C. Greubel, May 09 2017 *)

a(n) = A001221(A000058(n)-1) = A001221(A000058(0)*...*A000058(n-1)) = Sum_{i=0..(n-1)} A091335(i).

One more term from Max Alekseyev, Sep 11 2006

A123180 Even positions of Sylvester's sequence A000058; the denominators of the (greedy) Egyptian fraction expansion of Cahen's constant.

Original entry on oeis.org

2, 7, 1807, 10650056950807, 12864938683278671740537145998360961546653259485195807

Offset: 0

David Eppstein, Oct 03 2006

Amiram Eldar, Table of n, a(n) for n = 0..6
Eugène Cahen, Note sur un développement des quantités numériques, qui présente quelque analogie avec celui en fractions continues, Nouvelles Annales de Mathématiques, Vol. 10 (1891), pp. 508-514.
Eric Weisstein's World of Mathematics, Cahen's Constant.
Wikipedia, Cahen's constant.

Cf. A000058, A006279, A006280, A006281, A077125, A118227.

f[n_] := n*(n-1)*(n*(n-1)+1)+1; a[0] = 2; a[n_] := a[n] = f[a[n-1]]; Array[a, 5, 0] (* Amiram Eldar, Mar 19 2024 *)
1+NestList[#(#+1)(#^2+#+1) &, 1, 4] (* Oliver Seipel, Aug 25 2024 *)

a(n)=if(n, my(k=a(n-1));k*=k-1; k*(k+1)+1, 2) \\ Charles R Greathouse IV, Dec 12 2013

a(n) = a(n-1)*(a(n-1)-1)*(a(n-1)*(a(n-1)-1)+1)+1.
a(n) is approximately k^4^n with k = 1.5979102180318731783... (A077125). - Charles R Greathouse IV, Dec 12 2013
Sum_{n>=0} 1/a(n) = A118227. - Amiram Eldar, Mar 19 2024

a(4) from Charles R Greathouse IV, Dec 12 2013

A323605 Smallest prime divisor of A000058(n) = A007018(n) + 1 (Sylvester's sequence).

Original entry on oeis.org

2, 3, 7, 43, 13, 3263443, 547, 29881, 5295435634831, 181, 2287, 73

Offset: 0

Robert FERREOL, Jan 19 2019

a(n) is also the smallest prime divisor of A007018(n+1) that is not a divisor of A007018(n).
The prime numbers a(n) are all distinct, which proves the infinitude of the prime numbers (Saidak's proof).
a(12) <= 2589377038614498251653. - Daniel Suteu, Jan 20 2019
a(12)..a(50) = [?, 52387, 13999, 17881, 128551, 635263, ?, ?, 352867, 387347773, ?, 74587, ?, ?, 27061, 164299, 20929, 1171, ?, 1679143, ?, ?, 120823, 2408563, 38218903, 333457, 30241, 4219, 1085443, 7603, 1861, ?, 23773, 51769, 1285540933, 429547, ?, 8323570543, ?], where ? denote unknown values > 10^10. - Max Alekseyev, Oct 11 2023

Filip Saidak, A new proof of Euclid's theorem, Amer. Math. Monthly, 113:10 (2006) 937-938.
Wikipedia, Sylvester's sequence: Divisibility and factorizations.

Cf. A007018, A000058, A007996, A091335, A180871.

with(numtheory):
u:=1: P:=NULL: to 9 do P:=P,sort([op(divisors(u+1))])[2]: u:=u*(u+1) od:
P;

f(n)=if(n<1, n>=0, f(n-1)+f(n-1)^2); \\ A007018
a(n)=divisors(f(n)+1)[2]; \\ Michel Marcus, Jan 20 2019

a(n) = A007996(m), where m is the smallest index such that A180871(m) = n. - Max Alekseyev, Oct 11 2023

a(10)-a(11) from Daniel Suteu, Jan 20 2019

A367020 Largest prime factor of A000058(n) = A007018(n) + 1 (Sylvester's sequence).

Original entry on oeis.org

2, 3, 7, 43, 139, 3263443, 31051, 6212157481, 77366930214021991992277, 35874380272246624152764569191134894955972560447869169859142453622851

Offset: 0

Sean A. Irvine, Nov 01 2023

nonn

Amiram Eldar, Table of n, a(n) for n = 0..10
Filip Saidak, A new proof of Euclid's theorem, Amer. Math. Monthly, 113:10 (2006) 937-938.
Wikipedia, Sylvester's sequence: Divisibility and factorizations.

Cf. A000058, A007018, A006530, A091335, A323605.

a(n) = A006530(A000058(n)).

A367131 a(n) is the sum of the divisors of A000058(n) (Sylvester's sequence).

Original entry on oeis.org

3, 4, 8, 44, 1960, 3263444, 10697794573312, 113429214231136770625234912, 12864938683281101589385656009398714729057117020127552, 166504803622354833425112235578181474001920862856209391632362182416351065666575351284563698791731209336320

Offset: 0

Sean A. Irvine, Nov 05 2023

nonn

Amiram Eldar, Table of n, a(n) for n = 0..10
Wikipedia, Sylvester's sequence: Divisibility and factorizations.

Cf. A000058, A000203, A091335, A367130.

a000058[0] = 2; a000058[n_Integer?NonNegative] := a000058[n] = a000058[n - 1]^2 - a000058[n - 1] + 1; a[n_Integer?NonNegative] := a[n] = DivisorSigma[1, a000058[n]]; Table[a[n], {n, 0, 9}] (* Robert P. P. McKone, Nov 05 2023 *)

from sympy import divisor_sigma
memo = {0: 2}
def a000058(n):
    if n not in memo:
        memo[n] = a000058(n - 1)**2 - a000058(n - 1) + 1
    return memo[n]
a = lambda n: divisor_sigma(a000058(n))
print([a(n) for n in range(10)])
# Robert P. P. McKone, Nov 05 2023

a(n) = sigma(A000058(n)) = A000203(A000058(n)).

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

A091335 Number of prime divisors of n-th term of Sylvester's sequence A000058.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A126263 List of primes generated by factoring successive integers in Sylvester's sequence (A000058).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Extensions

A180871 Index of term in Sylvester's sequence A000058 divisible by prime A007996(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A014546 Primes in Sylvester's sequence A000058.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A091336 Number of prime divisors of A000058(n)-1 = A000058(0)*...*A000058(n-1).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A123180 Even positions of Sylvester's sequence A000058; the denominators of the (greedy) Egyptian fraction expansion of Cahen's constant.

Views

Author

Keywords

Links

Crossrefs

A091336 Number of prime divisors of A000058(n)-1 = A000058(0)...A000058(n-1).