cp's OEIS Frontend

A000058 Sylvester's sequence: a(n+1) = a(n)^2 - a(n) + 1, with a(0) = 2.

%I A000058 M0865 N0331 #373 Mar 22 2025 06:35:49
%S A000058 2,3,7,43,1807,3263443,10650056950807,113423713055421844361000443,
%T A000058 12864938683278671740537145998360961546653259485195807
%N A000058 Sylvester's sequence: a(n+1) = a(n)^2 - a(n) + 1, with a(0) = 2.
%C A000058 Also called Euclid numbers, because a(n) = a(0)*a(1)*...*a(n-1) + 1 for n>0, with a(0)=2. - _Jonathan Sondow_, Jan 26 2014
%C A000058 Another version of this sequence is given by A129871, which starts with 1, 2, 3, 7, 43, 1807, ... .
%C A000058 The greedy Egyptian representation of 1 is 1 = 1/2 + 1/3 + 1/7 + 1/43 + 1/1807 + ... .
%C A000058 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
%C A000058 More generally one may define f(1) = x_1, f(2) = x_2, ..., f(k) = x_k, f(n) = f(1)*...*f(n-1)+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(n-1) = (a(n)-2)/(a(n)-1). Thus we can also write a(n) = (1/a(0) + 1/a(1) + 1/a(2) + ... + 1/a(n-1) - 2 )/( 1/a(0) + 1/a(1) + 1/a(2) + ... + 1/a(n-1) - 1). - Frederick Magata (frederick.magata(AT)uni-muenster.de), May 10 2001; [corrected by _Michel Marcus_, Mar 27 2019]
%C A000058 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]
%C A000058 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
%C A000058 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
%C A000058 An infinite coprime sequence defined by recursion.
%C A000058 Apart from the initial 2, a subsequence of A002061. It follows that no term is a square.
%C A000058 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)^2-2*a(k)+2)*(a(k)^2 + 1) (a(k+1)=a(k)^2-a(k)+1 by definition). - Pab Ter (pabrlos(AT)yahoo.com), May 31 2004
%C A000058 In general, for any m > 0 coprime to a(0), the sequence a(n+1) = a(n)^2 - m*a(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.
%C A000058 Any prime factor of a(n) has -3 as its quadratic residue (Granville, exercise 1.2.3c in Pollack).
%C A000058 Note that values need not be prime, the first composites being 1807 = 13 * 139 and 10650056950807 = 547 * 19569939581. - _Jonathan Vos Post_, Aug 03 2008
%C A000058 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
%C A000058 (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
%C A000058 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
%C A000058 For n >= 4, a(n) mod 3000 alternates between 1807 and 2443. - _Robert Israel_, Jan 18 2015
%C A000058 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
%C A000058 Sylvester numbers when reduced modulo 864 form the 24-term 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
%C A000058 Named after the English mathematician James Joseph Sylvester (1814-1897). - _Amiram Eldar_, Mar 09 2024
%C A000058 Guy askes if it is an irrationality sequence (see Guy, 1981). - _Stefano Spezia_, Oct 13 2024
%D A000058 Graham Everest, Alf van der Poorten, Igor Shparlinski and Thomas Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.
%D A000058 Steven R. Finch, Mathematical Constants, Cambridge, 2003, Section 6.7.
%D A000058 Ronald L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 2nd. ed., 1994.
%D A000058 Richard K. Guy, Unsolved Problems in Number Theory, Springer, 1st edition, 1981. See section E24.
%D A000058 Richard K. Guy and Richard Nowakowski, Discovering primes with Euclid. Delta, Vol. 5 (1975), pp. 49-63.
%D A000058 Amarnath Murthy, Smarandache Reciprocal partition of unity sets and sequences, Smarandache Notions Journal, Vol. 11, 1-2-3, Spring 2000.
%D A000058 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.
%D A000058 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000058 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A000058 N. J. A. Sloane, <a href="/A000058/b000058.txt">Table of n, a(n) for n = 0..12</a>
%H A000058 David Adjiashvili, Sandro Bosio and Robert Weismantel, <a href="http://www.iasi.cnr.it/aussois/web/uploads/2012/papers/bosios.pdf">Dynamic Combinatorial Optimization: a complexity and approximability study</a>, 2012.
%H A000058 A. V. Aho and N. J. A. Sloane, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/11-4/aho-a.pdf">Some doubly exponential sequences</a>, Fibonacci Quarterly, Vol. 11, No. 4 (1973), pp. 429-437.
%H A000058 A. V. Aho and N. J. A. Sloane, <a href="/A000058/a000058.pdf">Some doubly exponential sequences</a>, Fibonacci Quarterly, Vol. 11, No. 4 (1973), pp. 429-437 (original plus references that F.Q. forgot to include - see last page!)
%H A000058 Mohammad K. Azarian, <a href="http://www.jstor.org/stable/10.4169/college.math.j.42.4.329">Sylvester's Sequence and the Infinite Egyptian Fraction Decomposition of 1, Problem 958</a>, College Mathematics Journal, Vol. 42, No. 4, September 2011, p. 330.
%H A000058 Mohammad K. Azarian, <a href="http://www.jstor.org/stable/10.4169/college.math.j.43.4.337">Sylvester's Sequence and the Infinite Egyptian Fraction Decomposition of 1, Solution</a> College Mathematics Journal, Vol. 43, No. 4, September 2012, pp. 340-342.
%H A000058 Gennady Bachman and Troy Kessler, <a href="http://dx.doi.org/10.1016/j.jnt.2003.12.001">On divisibility properties of certain multinomial coefficients—II</a>, Journal of Number Theory, Volume 106, Issue 1, May 2004, Pages 1-12.
%H A000058 Andreas Bäuerle, <a href="https://arxiv.org/abs/2308.12719">Sharp volume and multiplicity bounds for Fano simplices</a>, arXiv:2308.12719 [math.CO], 2023.
%H A000058 Kevin S. Brown, <a href="http://www.mathpages.com/home/kmath454.htm">Odd, Greedy and Stubborn (Unit Fractions)</a>.
%H A000058 Eunice Y. S. Chan and Robert M. Corless, <a href="https://doi.org/10.1007/s11786-018-0364-2">Minimal Height Companion Matrices for Euclid Polynomials</a>, Mathematics in Computer Science, Vol. 13, No. 1-2 (2019), pp. 41-56, <a href="https://arxiv.org/abs/1712.04405">arXiv preprint</a>, arXiv:1712.04405 [math.NA], 2017.
%H A000058 Hung Viet Chu, <a href="https://arxiv.org/abs/2306.12564">A Threshold for the Best Two-term Underapproximation by the Greedy Algorithm</a>, arXiv:2306.12564 [math.NT], 2023.
%H A000058 Matthew Brendan Crawford, <a href="https://vtechworks.lib.vt.edu/handle/10919/90573">On the Number of Representations of One as the Sum of Unit Fractions</a>, Master's Thesis, Virginia Polytechnic Institute and State University (2019).
%H A000058 D. R. Curtiss, <a href="http://www.jstor.org/stable/2299023">On Kellogg's Diophantine problem</a>, Amer. Math. Monthly, Vol. 29, No. 10 (1922), pp. 380-387.
%H A000058 Mehran Derakhshandeh, <a href="https://math.stackexchange.com/questions/2686116/why-do-sylvester-numbers-when-reduced-modulo-864-form-an-arithmetic-progress">Why do Sylvester numbers, when reduced modulo 864, form an arithmetic progression 7,43,79,115,151,187,223,...?</a>
%H A000058 Paul Erdős and E. G. Straus, <a href="https://www.renyi.hu/~p_erdos/1964-19.pdf">On the Irrationality of Certain Ahmes Series</a>, J. Indian Math. Soc. (N.S.), 27(1964), pp. 129-133.
%H A000058 Steven Finch, <a href="https://arxiv.org/abs/2411.16062">Exercises in Iterational Asymptotics</a>, arXiv:2411.16062 [math.NT], 2024. See p. 10.
%H A000058 Solomon W. Golomb, <a href="http://dx.doi.org/10.4153/CJM-1963-051-0">On the sum of the reciprocals of the Fermat numbers and related irrationalities</a>, Canad. J. Math., 15 (1963), 475-478.
%H A000058 Solomon W. Golomb, <a href="http://www.jstor.org/stable/2311857">On certain nonlinear recurring sequences</a>, Amer. Math. Monthly 70 (1963), 403-405.
%H A000058 Richard K. Guy and Richard Nowakowski, <a href="/A000945/a000945_5.pdf">Discovering primes with Euclid</a>, Research Paper No. 260 (Nov 1974), The University of Calgary Department of Mathematics, Statistics and Computing Science.
%H A000058 János Kollár, <a href="http://arxiv.org/abs/0805.0756">Which powers of holomorphic functions are integrable?</a>, arXiv:0805.0756 [math.AG], 2008.
%H A000058 E. Lemoine, <a href="https://gallica.bnf.fr/ark:/12148/bpt6k201185m/f76.vertical">Sur la décomposition d'un nombre en ses carrés maxima</a>, Assoc. Française pour L'Avancement des Sciences (1896), 73-77.
%H A000058 Zheng Li and Quanyu Tang, <a href="https://arxiv.org/abs/2503.12277">On a conjecture of Erdős and Graham about the Sylvester's sequence</a>, arXiv:2503.12277 [math.NT], 2025. See p. 2.
%H A000058 Nick Lord, <a href="http://www.jstor.org/stable/27821719">A uniform construction of some infinite coprime sequences</a>, The Mathematical Gazette, vol. 92, no. 523, March 2008, pp.66-70.
%H A000058 Romeo Meštrović, <a href="http://arxiv.org/abs/1202.3670">Euclid's theorem on the infinitude of primes: a historical survey of its proofs (300 BC--2012) and another new proof</a>, arXiv preprint arXiv:1202.3670 [math.HO], 2012. - _N. J. A. Sloane_, Jun 13 2012
%H A000058 Melvyn B. Nathanson, <a href="https://arxiv.org/abs/2202.00191">Underapproximation by Egyptian fractions</a>, arXiv:2202.00191 [math.NT], 2022.
%H A000058 Benjamin Nill, <a href="http://doi.org/10.1007/s00454-006-1299-y">Volume and lattice points of reflexive simplices</a>, Discrete & Computational Geometry, Vol. 37, No. 2 (2007), pp. 301-320, <a href="http://arxiv.org/abs/math/0412480">arXiv preprint</a>, arXiv:math/0412480 [math.AG], 2004-2007.
%H A000058 R. W. K. Odoni, <a href="https://doi.org/10.1112/jlms/s2-32.1.1">On the prime divisors of the sequence w_{n+1}=1+w_1 ... w_n</a>, J. London Math. Soc. 32 (1985), 1-11.
%H A000058 Michael Penn, <a href="https://www.youtube.com/watch?v=pP4o6I2OJTU">An intriguing integer sequence — Sylvester’s Sequence</a>, YouTube video (2022).
%H A000058 Simon Plouffe, <a href="https://arxiv.org/abs/1901.01849">A set of formulas for primes</a>, arXiv:1901.01849 [math.NT], 2019.
%H A000058 Paul Pollack, <a href="http://www.math.dartmouth.edu/~ppollack/notes.pdf">Analytic and Combinatorial Number Theory Course Notes</a>, p. 5. [?Broken link]
%H A000058 Paul Pollack, <a href="http://alpha01.dm.unito.it/personalpages/cerruti/ac/notes.pdf">Analytic and Combinatorial Number Theory Course Notes</a>, p. 5.
%H A000058 Filip Saidak, <a href="http://www.jstor.org/stable/27642094">A New Proof of Euclid's Theorem</a>, Amer. Math. Monthly, Vol. 113, No. 10 (Dec., 2006), pp. 937-938.
%H A000058 N. J. A. Sloane, <a href="https://www.youtube.com/watch?v=3RAYoaKMckM">A Nasty Surprise in a Sequence and Other OEIS Stories</a>, Experimental Mathematics Seminar, Rutgers University, Oct 10 2024, Youtube video; <a href="https://sites.math.rutgers.edu/~zeilberg/expmath/sloane85BD.pdf">Slides</a> [Mentions this sequence]
%H A000058 Jonathan Sondow and Kieren MacMillan, <a href="http://www.jstor.org/stable/10.4169/amer.math.monthly.124.3.232">Primary pseudoperfect numbers, arithmetic progressions, and the Erdős-Moser equation</a>, Amer. Math. Monthly, Vol. 124, No. 3 (2017), pp. 232-240, <a href="http://arxiv.org/abs/1812.06566">arXiv preprint</a>, arXiv:math/1812.06566 [math.NT], 2018.
%H A000058 J. J. Sylvester, <a href="http://www.jstor.org/stable/2369261">On a Point in the Theory of Vulgar Fractions</a>, Amer. J. Math., Vol. 3, No. 4 (1880), pp. 332-335.
%H A000058 Burt Totaro, <a href="http://www.bourbaki.ens.fr/TEXTES/1025.pdf">The ACC conjecture for log canonical thresholds</a>, Séminaire Bourbaki no. 1025 (juin 2010).
%H A000058 Burt Totaro and Chengxi Wang, <a href="https://arxiv.org/abs/2104.12200">Varieties of general type with small volume</a>, arXiv:2104.12200 [math.AG], 2021.
%H A000058 Akiyoshi Tsuchiya, <a href="https://doi.org/10.1016/j.disc.2016.04.011">The delta-vectors of reflexive polytopes and of the dual polytopes</a>, Discrete Mathematics, Vol. 339, No. 10 (2016), pp. 2450-2456, <a href="http://arxiv.org/abs/1411.2122">arXiv preprint</a>, arXiv:1411.2122 [math.CO], 2014-2016.
%H A000058 Stephan Wagner and Volker Ziegler, <a href="https://arxiv.org/abs/2004.09353">Irrationality of growth constants associated with polynomial recursions</a>, arXiv:2004.09353 [math.NT], 2020.
%H A000058 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/QuadraticRecurrenceEquation.html">Quadratic Recurrence Equation</a>.
%H A000058 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/SylvestersSequence.html">Sylvester's Sequence</a>.
%H A000058 Wikipedia, <a href="http://en.wikipedia.org/wiki/Sylvester%27s_sequence">Sylvester's sequence</a>.
%H A000058 Bowen Yao, <a href="https://doi.org/10.1080/00029890.2020.1815481">A note on fraction decompositions of integers</a>, The American Mathematical Monthly, 127(10), 928-932, Dec 2020.
%H A000058 <a href="/index/Aa#AHSL">Index entries for sequences of form a(n+1)=a(n)^2 + ...</a>.
%H A000058 <a href="/index/Cor#core">Index entries for "core" sequences</a>.
%F A000058 a(n) = 1 + a(0)*a(1)*...*a(n-1).
%F A000058 a(n) = a(n-1)*(a(n-1)-1) + 1; Sum_{i>=0} 1/a(i) = 1. - _Néstor Romeral Andrés_, Oct 29 2001
%F A000058 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 Aho-Sloane paper!)
%F A000058 a(n) = A007018(n+1)+1 = A007018(n+1)/A007018(n) [A007018 is a(n) = a(n-1)^2 + a(n-1), a(0)=1]. - _Gerald McGarvey_, Oct 11 2004
%F A000058 a(n) = sqrt(A174864(n+1)/A174864(n)). - _Giovanni Teofilatto_, Apr 02 2010
%F A000058 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
%F A000058 a(n) = f(1/(1-(1/a(0) + 1/a(1) + ... + 1/a(n-1)))) where f(x) is the smallest integer > x (see greedy algorithm above). - _Robert FERREOL_, Feb 22 2019
%F A000058 From _Amiram Eldar_, Oct 29 2020: (Start)
%F A000058 Sum_{n>=0} (-1)^n/(a(n)-1) = A118227.
%F A000058 Sum_{n>=0} (-1)^n/a(n) = 2 * A118227 - 1. (End)
%e A000058 a(0)=2, a(1) = 2+1 = 3, a(2) = 2*3 + 1 = 7, a(3) = 2*3*7 + 1 = 43.
%p A000058 A[0]:= 2:
%p A000058 for n from 1 to 12 do
%p A000058 A[n]:= A[n-1]^2 - A[n-1]+1
%p A000058 od:
%p A000058 seq(A[i],i=0..12); # _Robert Israel_, Jan 18 2015
%t A000058 a[0] = 2; a[n_] := a[n - 1]^2 - a[n - 1] + 1; Table[ a[ n ], {n, 0, 9} ]
%t A000058 NestList[#^2-#+1&,2,10] (* _Harvey P. Dale_, May 05 2013 *)
%t A000058 RecurrenceTable[{a[n + 1] == a[n]^2 - a[n] + 1, a[0] == 2}, a, {n, 0, 10}] (* _Emanuele Munarini_, Mar 30 2017 *)
%o A000058 (PARI) a(n)=if(n<1,2*(n>=0),1+a(n-1)*(a(n-1)-1))
%o A000058 (PARI) A000058(n,p=2)={for(k=1,n,p=(p-1)*p+1);p} \\ give Mod(2,m) as 2nd arg to calculate a(n) mod m. - _M. F. Hasler_, Apr 25 2014
%o A000058 (PARI) a=vector(20); a[1]=3; for(n=2, #a, a[n]=a[n-1]^2-a[n-1]+1); concat(2, a) \\ _Altug Alkan_, Apr 04 2018
%o A000058 (Haskell)
%o A000058 a000058 0 = 2
%o A000058 a000058 n = a000058 m ^ 2 - a000058 m + 1 where m = n - 1
%o A000058 -- _James Spahlinger_, Oct 09 2012
%o A000058 (Haskell)
%o A000058 a000058_list = iterate a002061 2  -- _Reinhard Zumkeller_, Dec 18 2013
%o A000058 (Python)
%o A000058 A000058 = [2]
%o A000058 for n in range(1, 10):
%o A000058     A000058.append(A000058[n-1]*(A000058[n-1]-1)+1)
%o A000058 # _Chai Wah Wu_, Aug 20 2014
%o A000058 (Maxima) a(n) := if n = 0 then 2 else a(n-1)^2-a(n-1)+1 $
%o A000058 makelist(a(n),n,0,8); /* _Emanuele Munarini_, Mar 23 2017 */
%o A000058 (Julia)
%o A000058 a(n) = n == 0 ? BigInt(2) : a(n - 1)*(a(n - 1) - 1) + 1
%o A000058 [a(n) for n in 0:8] |> println # _Peter Luschny_, Dec 15 2020
%Y A000058 Cf. A005267, A000945, A000946, A005265, A005266, A075442, A007018, A014117, A054377, A002061, A118227, A126263, A007996 (primes dividing some term), A323605 (smallest prime divisors), A091335 (number of prime divisors), A129871 (a variant starting with 1).
%K A000058 nonn,nice,core
%O A000058 0,1
%A A000058 _N. J. A. Sloane_