

A000058


Sylvester's sequence: a(n+1) = a(n)^2  a(n) + 1, with a(0) = 2.
(Formerly M0865 N0331)


89




OFFSET

0,1


COMMENTS

Also called Euclid numbers, because a(n) = a(0)*a(1)*...*a(n1) + 1.  Jonathan Sondow, Jan 26 2014
Another version of this sequence is given by A129871, which starts with 1, 2, 3, 7, 43, 1807, ... .
The greedy Egyptian representation of 1 is 1 = 1/2 + 1/3 + 1/7 + 1/43 + 1/1807 + ... .
Take a square. Divide it into 2 equal rectangles by drawing a horizontal line. Divide the upper rectangle into 2 squares. Now you can divide the lower one into another 2 squares, but instead of doing so draw a horizontal line below the first one so you obtain a (2+1 = 3) X 1 rectangle which can be divided in 3 squares. Now you have a 6 X 1 rectangle at the bottom. Instead of dividing it into 6 squares, draw another horizontal line so you obtain a (6+1 = 7) X 1 rectangle and a 42 X 1 rectangle left, etc.  Néstor Romeral Andrés, Oct 29 2001
More generally one may define f(1) = x_1, f(2) = x_2, ..., f(k) = x_k, f(n) = f(1)*...*f(n1)+1 for n > k and natural numbers x_i (i = 1, ..., k) which satisfy gcd(x_i, x_j) = 1 for i <> j. By definition of the sequence we have that for each pair of numbers x, y from the sequence gcd(x, y) = 1. An interesting property of a(n) is that for n >= 2, 1/a(0) + 1/a(1) + 1/a(2) + ... + 1/a(n1) = (a(n)2)/(a(n)1). Thus we can also write a(n) = (1/a(0) + 1/a(1) + 1/a(2) + ... + 1/a(n1)  2 )/( 1/a(0) + 1/a(1) + 1/a(2) + ... + 1/a(n1)  1).  Frederick Magata (frederick.magata(AT)unimuenster.de), May 10 2001; [corrected by Michel Marcus, Mar 27 2019]
A greedy sequence: a(n+1) is the smallest integer > a(n) such that 1/a(0) + 1/a(1) + 1/a(2) + ... + 1/a(n+1) doesn't exceed 1. The sequence gives infinitely many ways of writing 1 as the sum of Egyptian fractions: Cut the sequence anywhere and decrement the last element. 1 = 1/2 + 1/3 + 1/6 = 1/2 + 1/3 + 1/7 + 1/42 = 1/2 + 1/3 + 1/7 + 1/43 + 1/1806 = ... .  Ulrich Schimke, Nov 17 2002; [corrected by Michel Marcus, Mar 27 2019]
Consider the mapping f(a/b) = (a^3 + b)/(a + b^3). Starting with a = 1, b = 2 and carrying out this mapping repeatedly on each new (reduced) rational number gives 1/2, 1/3, 4/28 = 1/7, 8/344 = 1/43, ..., i.e., 1/2, 1/3, 1/7, 1/43, 1/1807, ... . Sequence contains the denominators. Also the sum of the series converges to 1.  Amarnath Murthy, Mar 22 2003
a(1) = 2, then the smallest number == 1 (mod all previous terms). a(2n+6) == 443 (mod 1000) and a(2n+7) == 807 (mod 1000).  Amarnath Murthy, Sep 24 2003
An infinite coprime sequence defined by recursion.
Apart from the initial 2, a subsequence of A002061. It follows that no term is a square.
It appears that a(k)^2 + 1 divides a(k+1)^2 + 1.  David W. Wilson, May 30 2004. This is true since a(k+1)^2 + 1 = (a(k)^2  a(k) + 1)^2 +1 = (a(k)^22*a(k)+2)*(a(k)^2 + 1) (a(k+1)=a(k)^2a(k)+1 by definition).  Pab Ter (pabrlos(AT)yahoo.com), May 31 2004
In general, for any m > 0 coprime to a(0), the sequence a(n+1) = a(n)^2  ma(n) + m is infinite coprime (Mohanty). This sequence has (m,a(0))=(1,2); (2,3) is A000215; (1,4) is A082732; (3,4) is A000289; (4,5) is A000324.
Any prime factor of a(n) has 3 as its quadratic residue (Granville, exercise 1.2.3c in Pollack).
Note that values need not be prime, the first composites being 1807 = 13 * 139 and 10650056950807 = 547 * 19569939581.  Jonathan Vos Post, Aug 03 2008
If one takes any subset of the sequence comprising the reciprocals of the first n terms, with the condition that the first term is negated, then this subset has the property that the sum of its elements equals the product of its elements. Thus 1/2 = 1/2, 1/2 + 1/3 = 1/2 * 1/3, 1/2 + 1/3 + 1/7 = 1/2 * 1/3 * 1/7, 1/2 + 1/3 + 1/7 + 1/43 = 1/2 * 1/3 * 1/7 * 1/43, and so on.  Nick McClendon, May 14 2009
Apart the first term which is 2 we can easily prove that the number of units of a(n) is 3 or 7 alternately.  Mohamed Bouhamida, Sep 01 2009
(a(n) + a(n+1)) divides a(n)*a(n+1)1 because a(n)*a(n+1)  1 = a(n)*(a(n)^2  a(n) + 1)  1 = a(n)^3  a(n)^2 + a(n)  1 = (a(n)^2 + 1)*(a(n)  1) = (a(n) + a(n)^2  a(n) + 1)*(a(n)  1) = (a(n) + a(n+1))*(a(n)  1).  Mohamed Bouhamida, Aug 29 2009
This sequence is also related to the short side (or hypotenuse) of adjacent right triangles, (3, 4, 5), (5, 12, 13), (13, 84, 85), ... by A053630(n) = 2*a(n)  1.  Yuksel Yildirim, Jan 01 2013, edited by M. F. Hasler, May 19 2017
For n >= 4, a(n) mod 3000 alternates between 1807 and 2443.  Robert Israel, Jan 18 2015
The set of prime factors of a(n)'s is thin in the set of primes. Indeed, Odoni showed that the number of primes below x dividing some a(n) is O(x/(log x log log log x)).  Tomohiro Yamada, Jun 25 2018
Sylvester numbers when reduced modulo 864 form the 24term arithmetic progression 7, 43, 79, 115, 151, 187, 223, 259, 295, 331, ..., 763, 799, 835 which repeats itself until infinity. This was first noticed in March 2018 and follows from the work of Sondow and MacMillan (2017) regarding primary pseudoperfect numbers which similarly form an arithmetic progression when reduced modulo 288. Giuga numbers also form a sequence resembling an arithmetic progression when reduced modulo 288.  Mehran Derakhshandeh, Apr 26 2019


REFERENCES

Graham Everest, Alf van der Poorten, Igor Shparlinski and Thomas Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.
Steven R. Finch, Mathematical Constants, Cambridge, 2003, Section 6.7.
Ronald L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Mathematics. AddisonWesley, Reading, MA, 2nd. ed., 1994.
Richard K. Guy and Richard Nowakowski, Discovering primes with Euclid. Delta, Vol. 5 (1975), pp. 4963.
Amarnath Murthy, Smarandache Reciprocal partition of unity sets and sequences, Smarandache Notions Journal, Vol. 11, 123, Spring 2000.
Amarnath Murthy and Charles Ashbacher, Generalized Partitions and Some New Ideas on Number Theory and Smarandache Sequences, Hexis, Phoenix; USA 2005. See Section 1.1.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).


LINKS

N. J. A. Sloane, Table of n, a(n) for n = 0..12
David Adjiashvili, Sandro Bosio and Robert Weismantel, Dynamic Combinatorial Optimization: a complexity and approximability study, 2012.
A. V. Aho and N. J. A. Sloane, Some doubly exponential sequences, Fibonacci Quarterly, Vol. 11, No. 4 (1973), pp. 429437, alternative link.
Mohammad K. Azarian, Sylvester's Sequence and the Infinite Egyptian Fraction Decomposition of 1, Problem 958, College Mathematics Journal, Vol. 42, No. 4, September 2011, p. 330.
Mohammad K. Azarian, Sylvester's Sequence and the Infinite Egyptian Fraction Decomposition of 1, Solution College Mathematics Journal, Vol. 43, No. 4, September 2012, pp. 340342.
Gennady Bachman and Troy Kessler, On divisibility properties of certain multinomial coefficients—II, Journal of Number Theory, Volume 106, Issue 1, May 2004, Pages 112.
Kevin S. Brown, Odd, Greedy and Stubborn (Unit Fractions)
Eunice Y. S. Chan and Robert M. Corless, Minimal Height Companion Matrices for Euclid Polynomials, Mathematics in Computer Science, Vol. 13, No. 12 (2019), pp. 4156, arXiv preprint, arXiv:1712.04405 [math.NA], 2017.
Matthew Brendan Crawford, On the Number of Representations of One as the Sum of Unit Fractions, Master's Thesis, Virginia Polytechnic Institute and State University (2019).
D. R. Curtiss, On Kellogg's Diophantine problem, Amer. Math. Monthly, Vol. 29, No. 10 (1922), pp. 380387.
Mehran Derakhshandeh, Why do Sylvester numbers, when reduced modulo 864, form an arithmetic progression 7,43,79,115,151,187,223,...?
Paul Erdős and E. G. Straus, On the Irrationality of Certain Ahmes Series, J. Indian Math. Soc. (N.S.), 27(1964), pp. 129133.
Solomon W. Golomb, On the sum of the reciprocals of the Fermat numbers and related irrationalities, Canad. J. Math., 15 (1963), 475478.
Solomon W. Golomb, On certain nonlinear recurring sequences, Amer. Math. Monthly 70 (1963), 403405.
Richard K. Guy and Richard Nowakowski, Discovering primes with Euclid, Research Paper No. 260 (Nov 1974), The University of Calgary Department of Mathematics, Statistics and Computing Science.
János Kollár, Which powers of holomorphic functions are integrable?, arXiv:0805.0756 [math.AG], 2008.
Nick Lord, A uniform construction of some infinite coprime sequences, The Mathematical Gazette, vol. 92, no. 523, March 2008, pp.6670.
Romeo Meštrović, Euclid's theorem on the infinitude of primes: a historical survey of its proofs (300 BC2012) and another new proof, arXiv preprint arXiv:1202.3670 [math.HO], 2012.  N. J. A. Sloane, Jun 13 2012
Melvyn B. Nathanson, Underapproximation by Egyptian fractions, arXiv:2202.00191 [math.NT], 2022.
Benjamin Nill, Volume and lattice points of reflexive simplices, Discrete & Computational Geometry, Vol. 37, No. 2 (2007), pp. 301320, arXiv preprint, arXiv:math/0412480 [math.AG], 20042007.
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), 111.
Michael Penn, An intriguing integer sequence — Sylvester’s Sequence, YouTube video (2022).
Simon Plouffe, A set of formulas for primes, arXiv:1901.01849 [math.NT], 2019.
Paul Pollack, Analytic and Combinatorial Number Theory Course Notes, p. 5. [?Broken link]
Paul Pollack, Analytic and Combinatorial Number Theory Course Notes, p. 5.
Filip Saidak, A New Proof of Euclid's Theorem, Amer. Math. Monthly, Vol. 113, No. 10 (Dec., 2006), pp. 937938.
Jonathan Sondow and Kieren MacMillan, Primary pseudoperfect numbers, arithmetic progressions, and the ErdősMoser equation, Amer. Math. Monthly, Vol. 124, No. 3 (2017), pp. 232240, arXiv preprint, arXiv:math/1812.06566 [math.NT], 2018.
J. J. Sylvester, On a Point in the Theory of Vulgar Fractions, Amer. J. Math., Vol. 3, No. 4 (1880), pp. 332335.
Burt Totaro, The ACC conjecture for log canonical thresholds, Séminaire Bourbaki no. 1025 (juin 2010).
Burt Totaro and Chengxi Wang, Varieties of general type with small volume, arXiv:2104.12200 [math.AG], 2021.
Akiyoshi Tsuchiya, The deltavectors of reflexive polytopes and of the dual polytopes, Discrete Mathematics, Vol. 339, No. 10 (2016), pp. 24502456, arXiv preprint, arXiv:1411.2122 [math.CO], 20142016.
Stephan Wagner and Volker Ziegler, Irrationality of growth constants associated with polynomial recursions, arXiv:2004.09353 [math.NT], 2020.
Eric Weisstein's World of Mathematics, Sylvester's Sequence.
Eric Weisstein's World of Mathematics, Quadratic Recurrence Equation.
Wikipedia, Sylvester's sequence.
Bowen Yao, A note on fraction decompositions of integers, The American Mathematical Monthly, 127(10), 928932, Dec 2020.
Index entries for sequences of form a(n+1)=a(n)^2 + ...
Index entries for "core" sequences


FORMULA

a(n) = 1 + a(0)*a(1)*...*a(n1).
a(n) = a(n1)*(a(n1)1) + 1; Sum_{i>=0} 1/a(i) = 1.  Néstor Romeral Andrés, Oct 29 2001
Vardi showed that a(n) = floor(c^(2^(n+1)) + 1/2) where c = A076393 = 1.2640847353053011130795995...  Benoit Cloitre, Nov 06 2002 (But see the AhoSloane paper!)
a(n) = A007018(n+1)+1 = A007018(n+1)/A007018(n) [A007018 is a(n) = a(n1)^2 + a(n1), a(0)=1].  Gerald McGarvey, Oct 11 2004
a(n) = sqrt(A174864(n+1)/A174864(n)).  Giovanni Teofilatto, Apr 02 2010
a(n) = A014117(n+1)+1 for n = 0,1,2,3,4; a(n) = A054377(n)+1 for n = 1,2,3,4.  Jonathan Sondow, Dec 07 2013
a(n) = f(1/(1(1/a(0) + 1/a(1) + ... + 1/a(n1)))) where f(x) is the smallest integer > x (see greedy algorithm above).  Robert FERREOL, Feb 22 2019
From Amiram Eldar, Oct 29 2020: (Start)
Sum_{n>=0} (1)^n/(a(n)1) = A118227.
Sum_{n>=0} (1)^n/a(n) = 2 * A118227  1. (End)


EXAMPLE

a(0)=2, a(1) = 2+1 = 3, a(2) = 2*3 + 1 = 7, a(3) = 2*3*7 + 1 = 43.


MAPLE

A[0]:= 2:
for n from 1 to 12 do
A[n]:= A[n1]^2  A[n1]+1
od:
seq(A[i], i=0..12); # Robert Israel, Jan 18 2015


MATHEMATICA

a[0] = 2; a[n_] := a[n  1]^2  a[n  1] + 1; Table[ a[ n ], {n, 0, 9} ]
NestList[#^2#+1&, 2, 10] (* Harvey P. Dale, May 05 2013 *)
RecurrenceTable[{a[n + 1] == a[n]^2  a[n] + 1, a[0] == 2}, a, {n, 0, 10}] (* Emanuele Munarini, Mar 30 2017 *)


PROG

(PARI) a(n)=if(n<1, 2*(n>=0), 1+a(n1)*(a(n1)1))
(PARI) A000058(n, p=2)={for(k=1, n, p=(p1)*p+1); p} \\ give Mod(2, m) as 2nd arg to calculate a(n) mod m.  M. F. Hasler, Apr 25 2014
(PARI) a=vector(20); a[1]=3; for(n=2, #a, a[n]=a[n1]^2a[n1]+1); concat(2, a) \\ Altug Alkan, Apr 04 2018
(Haskell)
a000058 0 = 2
a000058 n = a000058 m ^ 2  a000058 m + 1 where m = n  1
 James Spahlinger, Oct 09 2012
(Haskell)
a000058_list = iterate a002061 2  Reinhard Zumkeller, Dec 18 2013
(Python)
A000058 = [2]
for n in range(1, 10):
A000058.append(A000058[n1]*(A000058[n1]1)+1)
# Chai Wah Wu, Aug 20 2014
(Maxima) a(n) := if n = 0 then 2 else a(n1)^2a(n1)+1 $
makelist(a(n), n, 0, 8); # Emanuele Munarini, Mar 23 2017
(Julia)
a(n) = n == 0 ? BigInt(2) : a(n  1)*(a(n  1)  1) + 1
[a(n) for n in 0:8] > println # Peter Luschny, Dec 15 2020


CROSSREFS

Cf. A005267, A000945, A000946, A005265, A005266, A075442, A007018, A014117, A054377, A002061, A118227, A126263, A007996 (primes dividing some term), A323605 (smallest prime divisors), A129871 (a variant starting with 1).
Sequence in context: A133400 A113845 A072713 * A129871 A075442 A082993
Adjacent sequences: A000055 A000056 A000057 * A000059 A000060 A000061


KEYWORD

nonn,nice,core


AUTHOR

N. J. A. Sloane


STATUS

approved



