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

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

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)
66
2, 3, 7, 43, 1807, 3263443, 10650056950807, 113423713055421844361000443, 12864938683278671740537145998360961546653259485195807 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,1

COMMENTS

Also called Euclid numbers, because a(n) = a(0)*a(1)*...*a(n-1) + 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(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

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

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

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, 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)^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

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

This sequence is also called Ahmes (or Ahmose) series.  Ahmes was an ancient Egyptian scribe who wrote the Rhind Mathematical Papyrus around 1650 BC (see the paper by P. Erdos and E. G. Straus in the reference section below). - Mohammad K. Azarian, Mar 08 2012

Comment from Yuksel Yildirim, Jan 01 2013: (Start)

This sequence is also related to the short side (or hypotenuse) of adjacent right triangles:

3  4    5

5  12   13

13 84   85

85 3612 3613

.....

as follows:

a0=1, a1=2; an=a0.a1.a2...an + 1

a(n)   h(n) [ h(n) = 2*a(n) - 1 ]

----  ---------------------------

2     3

3     5

7     13

43    85

1807  3613

... (End)

REFERENCES

D. Adjiashvili, S. Bosio and R. Weismantel, Dynamic Combinatorial Optimization: a complexity and approximability study; http://www.iasi.cnr.it/aussois/web/uploads/2012/papers/sbosio.pdf, 2012. - From N. J. A. Sloane, Jan 03 2013

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.  Solution published in Vol. 43, No. 4, September 2012, pp. 340-342.

D. R. Curtiss, On Kellogg's Diophantine problem, Amer Math. Monthly, 29 (1922), 380-387.

P. Erdos and E. G. Straus, On the Irrationality of Certain Ahmes Series, J. Indian Math. Soc. (N.S.), 27(1964), pp. 129-133.

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

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

S. W. Golomb, On the sum of the reciprocals of the Fermat numbers and related irrationalities, Canad. J. Math., 15 (1963), 475-478.

S. W. Golomb, On certain nonlinear recurring sequences, Amer. Math. Monthly 70 (1963), 403-405.

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

Guy, R. K. & Nowakowski, R., Discovering primes with Euclid. Delta, 1975, 5. p. 49-63. [From Artur Jasinski, Dec 28 2008]

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, Aug 03 2008]

Amarnath Murthy, Smarandache Reciprocal partition of unity sets and sequences, Smarandache Notions Journal, Vol. 11, 1-2-3, 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.

Filip Saidak, A New Proof of Euclid's Theorem, Amer. Math. Monthly, Dec 2006

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

A. V. Aho and N. J. A. Sloane, Some doubly exponential sequences, Fib. Quart., 11 (1973), 429-437.

K. S. Brown, Odd, Greedy and Stubborn (Unit Fractions)

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

B. Nill, Volume and lattice points of reflexive simplices

P. Pollack, Analytic and Combinatorial Number Theory Course Notes, p. 5. [?Broken link]

P. Pollack, Analytic and Combinatorial Number Theory Course Notes, p. 5.

J. J. Sylvester, On a Point in the Theory of Vulgar Fractions, Amer. J. Math., 3 (1880), 332-335.

Eric Weisstein's World of Mathematics, Sylvester's Sequence

Eric Weisstein's World of Mathematics, Quadratic Recurrence Equation

Wikipedia, Sylvester's sequence

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(n-1).

a(n) = a(n-1)*(a(n-1)-1)+1; Sum(i=0 to oo) 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=1.2640847353053011130795995... - Benoit Cloitre, Nov 06 2002 (But see the Aho-Sloane paper!)

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

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

EXAMPLE

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

MATHEMATICA

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

a = {}; k = 1; m = 1; Do[k = k m; AppendTo[a, k + 1]; m = k + 1, {n, 1, 10}]; a (* From Artur Jasinski, Dec 28 2008 *)

a=1; lst={a}; Do[b=(a+1)*a; AppendTo[lst, b]; a=b, {n, 1, 9}]; lst+1 (* From Vladimir Joseph Stephan Orlovsky, Mar 16 2010 *)

NestList[#^2-#+1&, 2, 10] (* Harvey P. Dale, May 05 2013 *)

PROG

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

(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

(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[n-1]*(A000058[n-1]-1)+1)

# Chai Wah Wu, Aug 20 2014

CROSSREFS

Cf. A005267, A000945, A000946, A005265, A005266, A075442, A007018.

Cf. A007996 (primes dividing some term)

Cf. A129871 (a variant starting with 1)

Cf. A014117, A054377.

Cf. A002061.

Cf. A126263.

Sequence in context: A113845 A072713 * A129871 A075442 A082993 A071580

Adjacent sequences:  A000055 A000056 A000057 * A000059 A000060 A000061

KEYWORD

nonn,nice,core

AUTHOR

N. J. A. Sloane

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified November 22 18:41 EST 2014. Contains 249807 sequences.