%I A000058 M0865 N0331
%S A000058 2,3,7,43,1807,3263443,10650056950807,113423713055421844361000443,
%T A000058 12864938683278671740537145998360961546653259485195807,
%U A000058 165506647324519964198468195444439180017513152706377497841851388766535868639572406808911988131737645185443
%N A000058 Sylvester's sequence: a(n+1) = a(n)^2 - a(n) + 1, with a(0) = 2.
%C A000058 Also called Euclid numbers.
%C A000058 Another version begins 1, 2, 3, 7, 43, 1807, ..., but the initial 1 seems 
               artificial.
%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)x1 rectangle 
               which can be divided in 3 squares. Now you have a 6x1 rectangle at 
               the bottom. Instead of dividing it into 6 squares, draw another horizontal 
               line so you obtain a (6+1=7)x1 rectangle and a 42x1 rectangle left. 
               Etc... - Nestor Romeral Andres (cashogor(AT)yahoo.com), 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(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 (fmagata(AT)mi.uni-koeln.de), May 
               10 2001
%C A000058 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. - Ulrich Schimke, 
               Nov 17, 2002
%C A000058 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 A000058 Consider the mapping f(a/b) = (a^3 + b)/(a +b^3). Taking a = 1 b = 2 
               to start with and carrying out this mapping repeatedly on each new 
               (reduced) rational number gives the following sequence 1/2,1/3,4/
               28=1/7,8/344=1/43,... 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 (amarnath_murthy(AT)yahoo.com), 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 
               (amarnath_murthy(AT)yahoo.com), 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 (davidwwilson(AT)comcast.net), 
               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 
               -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 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. [From Jonathan Vos 
               Post (jvospost3(AT)gmail.com), Aug 03 2008]
%C A000058 Comment from Nick McClendon, May 14 2009: 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.
%C A000058 Apart the first term which is 2 we can easily prove that the number of 
               units of a(n) is 3 or 7 alternately. [From Mohamed Bouhamida (bhmd95(AT)yahoo.fr), 
               Sep 01 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). [From Mohamed Bouhamida (bhmd95(AT)yahoo.fr), Aug 29 2009]
%D A000058 D. R. Curtiss, "On Kellogg's Diophantine problem" Amer Math. Monthly, 
               29, (1922), 380-387.
%D A000058 G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence 
               Sequences, Amer. Math. Soc., 2003; see esp. p. 255.
%D A000058 S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 6.7.
%D A000058 S. W. Golomb, On the sum of the reciprocals of the Fermat numbers and 
               related irrationalities, Canad. J. Math., 15 (1963), 475-478.
%D A000058 S. W. Golomb, On certain nonlinear recurring sequences, Amer. Math. Monthly 
               70 (1963), 403-405.
%D A000058 R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, 
               Reading, MA, 2nd. ed., 1994.
%D A000058 Guy, R. K. & Nowakowski, R., Discovering primes with Euclid. Delta, 1975, 
               5. p. 49-63. [From Artur Jasinski (grafix(AT)csl.pl), Dec 28 2008]
%D A000058 Nick Lord, A uniform construction of some infinite coprime sequences, 
               The Mathematical Gazette, vol. 92, no. 523, March 2008, pp.66-70. 
               [From Jonathan Vos Post (jvospost3(AT)gmail.com), Aug 03 2008]
%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 Filip Saidak, A New Proof of Euclid's Theorem, Amer. Math. Monthly, Dec 
               2006
%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="b000058.txt">Table of n, a(n) for n = 0..12</
               a>
%H A000058 A. V. Aho and N. J. A. Sloane, <a href="http://www.research.att.com/~njas/
               doc/doubly.html">Some doubly exponential sequences</a>, Fib. Quart., 
               11 (1973), 429-437.
%H A000058 K. S. Brown, <a href="http://www.mathpages.com/home/kmath454.htm">Odd, 
               Greedy and Stubborn (Unit Fractions)</a>
%H A000058 B. Nill, <a href="http://arXiv.org/math.AG/0412480">Volume and lattice 
               points of reflexive simplices</a>
%H A000058 P. Pollack, <a href="http://www.math.dartmouth.edu/~ppollack/notes.pdf">
               Analytic and Combinatorial Number Theory Course Notes</a>, p. 5.
%H A000058 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               SylvestersSequence.html">Link to a section of The World of Mathematics.</
               a>
%H A000058 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               QuadraticRecurrenceEquation.html">Quadratic Recurrence Equation</
               a>
%H A000058 Wikipedia, <a href="http://en.wikipedia.org/wiki/Sylvester%27s_sequence">
               Sylvester's sequence</a>
%H A000058 <a href="Sindx_Aa.html#AHSL">Index entries for sequences of form a(n+1)=a(n)^2 
               + ...</a>
%H A000058 <a href="Sindx_Cor.html#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 to oo) 1/a(i) = 1. - Nestor Romeral 
               Andres (cashogor(AT)yahoo.com), Oct 29 2001
%F A000058 Vardi showed that a(n) = floor(c^(2^(n+1))+1/2) where c=1.2640847353053011130795995... 
               - Benoit Cloitre (benoit7848c(AT)orange.fr), 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 (Gerald.McGarvey(AT)comcast.net), 
               Oct 11 2004
%e A000058 a(0)=2, a(1)=2+1=3, a(2)=2*3+1=7, a(3)=2*3*7+1=43
%t A000058 a[0] = 2; a[n_] := a[n - 1]^2 - a[n - 1] + 1; Table[ a[ n ], {n, 0, 9} 
               ]
%t A000058 a = {}; k = 1; m = 1; Do[k = k m; AppendTo[a, k + 1]; m = k + 1, {n, 
               1, 10}]; a [From Artur Jasinski (grafix(AT)csl.pl), Dec 28 2008]
%o A000058 (PARI) a(n)=if(n<1,2*(n>=0),1+a(n-1)*(a(n-1)-1))
%Y A000058 Cf. A005267, A000945, A000946, A005265, A005266, A075442, A007018.
%Y A000058 Sequence in context: A113845 A072713 A129871 this_sequence A075442 A082993 
               A071580
%Y A000058 Adjacent sequences: A000055 A000056 A000057 this_sequence A000059 A000060 
               A000061
%K A000058 nonn,nice,core
%O A000058 0,1
%A A000058 N. J. A. Sloane (njas(AT)research.att.com).