login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000058 Sylvester's sequence: a(n+1) = a(n)^2 - a(n) + 1, with a(0) = 2.
(Formerly M0865 N0331)
76

%I M0865 N0331

%S 2,3,7,43,1807,3263443,10650056950807,113423713055421844361000443,

%T 12864938683278671740537145998360961546653259485195807

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

%C Also called Euclid numbers, because a(n) = a(0)*a(1)*...*a(n-1) + 1. - _Jonathan Sondow_, Jan 26 2014

%C Another version of this sequence is given by A129871, which starts with 1, 2, 3, 7, 43, 1807, ... .

%C The greedy Egyptian representation of 1 is 1 = 1/2 + 1/3 + 1/7 + 1/43 + 1/1807 + ... .

%C 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 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(1) + 1/a(2) + ... + 1/a(n-1) = (a(n)-2)/(a(n)-1). Thus we can also write a(n) = (1/a(1) + 1/a(2) + ... + 1/a(n-1) - 2 )/( 1/a(1) + 1/a(2) + ... + 1/a(n-1) - 1). - Frederick Magata (frederick.magata(AT)uni-muenster.de), May 10 2001

%C A greedy sequence: a(n+1) is the smallest integer > a(n) such that 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

%C 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 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 An infinite coprime sequence defined by recursion.

%C Apart from the initial 2, a subsequence of A002061. It follows that no term is a square.

%C 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 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.

%C Any prime factor of a(n) has -3 as its quadratic residue (Granville, exercise 1.2.3c in Pollack).

%C 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 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 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 (bhmd95(AT)yahoo.fr), Sep 01 2009

%C (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 (bhmd95(AT)yahoo.fr), Aug 29 2009

%C 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 For n >= 4, a(n) mod 3000 alternates between 1807 and 2443. - _Robert Israel_, Jan 18 2015

%D G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.

%D S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 6.7.

%D R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 2nd. ed., 1994.

%D Guy, R. K. & Nowakowski, R., Discovering primes with Euclid. Delta, 1975, 5. p. 49-63.

%D Amarnath Murthy, Smarandache Reciprocal partition of unity sets and sequences, Smarandache Notions Journal, Vol. 11, 1-2-3, Spring 2000.

%D 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 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H N. J. A. Sloane, <a href="/A000058/b000058.txt">Table of n, a(n) for n = 0..12</a>

%H D. Adjiashvili, S. Bosio and R. Weismantel, <a href="http://www.iasi.cnr.it/aussois/web/uploads/2012/papers/sbosio.pdf">Dynamic Combinatorial Optimization: a complexity and approximability study</a>, 2012.

%H 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 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 A. V. Aho and N. J. A. Sloane, <a href="http://neilsloane.com/doc/doubly.html">Some doubly exponential sequences</a>, Fib. Quart., 11 (1973), 429-437.

%H G. Bachman, T. 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 K. S. Brown, <a href="http://www.mathpages.com/home/kmath454.htm">Odd, Greedy and Stubborn (Unit Fractions)</a>

%H Eunice Y. S. Chan, Robert M. Corless, <a href="https://arxiv.org/abs/1712.04405">Minimal height companion matrices for Euclid polynomials</a>, arXiv:1712.04405 [math.NA], 2017.

%H D. R. Curtiss, <a href="http://www.jstor.org/stable/2299023">On Kellogg's Diophantine problem</a>, Amer. Math. Monthly 29 (1922), pp. 380-387.

%H P. 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 S. 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 S. W. Golomb, <a href="http://www.jstor.org/stable/2311857">On certain nonlinear recurring sequences</a>, Amer. Math. Monthly 70 (1963), 403-405.

%H R. K. Guy and R. 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 J. Kollar, <a href="http://arxiv.org/abs/0805.0756">Which powers of holomorphic functions are integrable?</a>, arXiv:0805.0756 [math.AG], 2008.

%H 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 R. Mestrovic, <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 B. Nill, <a href="http://arxiv.org/abs/math/0412480">Volume and lattice points of reflexive simplices</a>, arXiv:math/0412480 [math.AG], 2004-2007.

%H P. Pollack, <a href="http://www.math.dartmouth.edu/~ppollack/notes.pdf">Analytic and Combinatorial Number Theory Course Notes</a>, p. 5. [?Broken link]

%H P. Pollack, <a href="http://alpha01.dm.unito.it/personalpages/cerruti/ac/notes.pdf">Analytic and Combinatorial Number Theory Course Notes</a>, p. 5.

%H Filip Saidak, <a href="http://www.jstor.org/stable/27642094">A New Proof of Euclid's Theorem</a>, Amer. Math. Monthly, Dec 2006.

%H J. Sondow and K. 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, 124 (2017) 232-240.

%H J. J. Sylvester, <a href="http://www.jstor.org/stable/2369261">On a Point in the Theory of Vulgar Fractions</a>, Amer. J. Math., 3 (1880), 332-335.

%H B. 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 A. Tsuchiya, <a href="http://arxiv.org/abs/1411.2122">The delta-vectors of reflexive polytopes and of the dual polytopes</a>, arXiv preprint arXiv:1411.2122 [math.CO], 2014-2016.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/SylvestersSequence.html">Sylvester's Sequence</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/QuadraticRecurrenceEquation.html">Quadratic Recurrence Equation</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Sylvester%27s_sequence">Sylvester's sequence</a>

%H <a href="/index/Aa#AHSL">Index entries for sequences of form a(n+1)=a(n)^2 + ...</a>

%H <a href="/index/Cor#core">Index entries for "core" sequences</a>

%F a(n) = 1 + a(0)*a(1)*...*a(n-1).

%F 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 Vardi showed that a(n) = floor(c^(2^(n+1)) + 1/2) where c = 1.2640847353053011130795995... - _Benoit Cloitre_, Nov 06 2002 (But see the Aho-Sloane paper!)

%F 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 a(n) = sqrt(A174864(n+1)/A174864(n)). - _Giovanni Teofilatto_, Apr 02 2010

%F 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

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

%p A[0]:= 2:

%p for n from 1 to 12 do

%p A[n]:= A[n-1]^2 - A[n-1]+1

%p od:

%p seq(A[i],i=0..12); # _Robert Israel_, Jan 18 2015

%t a[0] = 2; a[n_] := a[n - 1]^2 - a[n - 1] + 1; Table[ a[ n ], {n, 0, 9} ]

%t a = {}; k = 1; m = 1; Do[k = k m; AppendTo[a, k + 1]; m = k + 1, {n, 1, 10}]; a (* _Artur Jasinski_, Dec 28 2008 *)

%t a=1;lst={a};Do[b=(a+1)*a;AppendTo[lst,b];a=b,{n,1,9}];lst+1 (* _Vladimir Joseph Stephan Orlovsky_, Mar 16 2010 *)

%t NestList[#^2-#+1&,2,10] (* _Harvey P. Dale_, May 05 2013 *)

%t RecurrenceTable[{a[n + 1] == a[n]^2 - a[n] + 1, a[0] == 2}, a, {n, 0, 10}] (* _Emanuele Munarini_, Mar 30 2017 *)

%o (PARI) a(n)=if(n<1,2*(n>=0),1+a(n-1)*(a(n-1)-1))

%o (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 (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 (Haskell)

%o a000058 0 = 2

%o a000058 n = a000058 m ^ 2 - a000058 m + 1 where m = n - 1

%o -- _James Spahlinger_, Oct 09 2012

%o (Haskell)

%o a000058_list = iterate a002061 2 -- _Reinhard Zumkeller_, Dec 18 2013

%o (Python)

%o A000058 = [2]

%o for n in range(1,10):

%o ....A000058.append(A000058[n-1]*(A000058[n-1]-1)+1)

%o # _Chai Wah Wu_, Aug 20 2014

%o (Maxima) a(n) := if n = 0 then 2 else a(n-1)^2-a(n-1)+1 $

%o makelist(a(n),n,0,8); _Emanuele Munarini_, Mar 23 2017

%Y Cf. A005267, A000945, A000946, A005265, A005266, A075442, A007018, A014117, A054377, A002061, A126263, A007996 (primes dividing some term), A129871 (a variant starting with 1).

%K nonn,nice,core

%O 0,1

%A _N. J. A. Sloane_

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified May 21 19:34 EDT 2018. Contains 304400 sequences. (Running on oeis4.)