A003010 A Lucas-Lehmer sequence: a(0) = 4; for n>0, a(n) = a(n-1)^2 - 2.

4, 14, 194, 37634, 1416317954, 2005956546822746114, 4023861667741036022825635656102100994, 16191462721115671781777559070120513664958590125499158514329308740975788034

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn

Comments

Albert Beiler states (page 228 of Recreations in the Theory of Numbers): D. H. Lehmer modified Lucas's test to the relatively simple form: If and only if 2^n-1 divides a(n-2) then 2^n-1 is a prime, otherwise it is composite. Since 2^3 - 1 is a factor of a(1) = 14, 2^3 - 1 = 7 is a prime. - Gary W. Adamson, Jun 07 2003

a(n) - a(n-1) divides a(n+1) - a(n). - Thomas Ordowski, Dec 24 2016

References

• A. H. Beiler, Recreations in the Theory of Numbers, Dover, NY, 1964, p. 228.
• L. E. Dickson, History of the Theory of Numbers. Carnegie Institute Public. 256, Washington, DC, Vol. 1, 1919; Vol. 2, 1920; Vol. 3, 1923, see vol. 1, p. 399.
• R. K. Guy, Unsolved Problems in Number Theory, Section A3.
• Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See p. 78.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
• David Wells, The Penguin Dictionary of Curious and Interesting Numbers. Penguin Books, NY, 1986, Revised edition 1987. See p. 205.

Links

• N. J. A. Sloane, Table of n, a(n) for n = 0..10
• A. V. Aho and N. J. A. Sloane, Some doubly exponential sequences, Fibonacci Quarterly, Vol. 11, No. 4 (1973), pp. 429-437.
• A. V. Aho and N. J. A. Sloane, Some doubly exponential sequences, Fibonacci Quarterly, Vol. 11, No. 4 (1973), pp. 429-437 (original plus references that F.Q. forgot to include - see last page!)
• Larry Ericksen, Primality Testing and Prime Constellations, Šiauliai Mathematical Seminar, Vol. 3 (11), 2008.
• James S. Hall, A remark on the primeness of Mersenne numbers, J. London Math. Soc. 28, (1953). 285-287.
• D. H. Lehmer, On Lucas's test for the primality of Mersenne's numbers, Journal of the London Mathematical Society 1.3 (1935): 162-165. See page 162.
• D. H. Lehmer. Mathematical Reviews. Review of: Hall, James S. A remark on the primeness of Mersenne numbers. (1953) [Annotated scanned copy]
• Pierre Liardet and Pierre Stambul, Séries d'Engel et fractions continuées, Journal de Théorie des Nombres de Bordeaux 12 (2000), 37-68.
• Mario Raso, Integer Sequences in Cryptography: A New Generalized Family and its Application, Ph. D. Thesis, Sapienza University of Rome (Italy 2025). See p. 25.
• E. L. Roettger and H. C. Williams, Some Remarks Concerning the Lucas-Lehmer Primality Test, Journal of Integer Sequences, Vol. 28 (2025), Article 25.2.5. See p. 3.
• Jeffrey Shallit, An interesting continued fraction, Math. Mag., 48 (1975), 207-211. [Annotated scanned copy]
• Pierluigi Vellucci and Alberto Maria Bersani, The class of Lucas-Lehmer polynomials, arXiv preprint arXiv:1603.01989 [math.CA], 2016.
• Pierluigi Vellucci and Alberto Maria Bersani, New formulas for pi involving infinite nested square roots and Gray code, arXiv preprint arXiv:1606.09597 [math.NT], 2016 (The OEIS is cited in version 1, but has been dropped from version 4.)
• Eric Weisstein's World of Mathematics, Lucas-Lehmer Test.
• Wikipedia, Engel Expansion
• Index entries for sequences of form a(n+1)=a(n)^2 + ...

Crossrefs

Cf. A001566 (starting with 3), A003423 (starting with 6), A003487 (starting with 5).

Cf. A002812, A145503.

Programs

Magma

[n le 1 select 4 else Self(n-1)^2-2: n in [1..10]]; // Vincenzo Librandi, Aug 24 2015

Maple

a := n-> if n>0 then a(n-1)^2-2 else 4 fi: 'a(i)' $ i=0..9; # M. F. Hasler, Mar 09 2007
a := n-> simplify(2*ChebyshevT(2^n, 2), 'ChebyshevT'): seq(a(n), n=0..7);

Mathematica

seqLucasLehmer[0] = 4; seqLucasLehmer[n_] := seqLucasLehmer[n - 1]^2 - 2; Array[seqLucasLehmer, 8, 0] (* Robert G. Wilson v, Jun 28 2012 *)

PARI

a(n)=if(n,a(n-1)^2-2,4)
vector(10,i,a(i-1)) \\ M. F. Hasler, Mar 09 2007

Python

from itertools import accumulate
def f(anm1, _): return anm1**2 - 2
print(list(accumulate([4]*8, f))) # Michael S. Branicky, Apr 14 2021

Formula

a(n) = ceiling((2 + sqrt(3))^(2^n)). - Benoit Cloitre, Nov 30 2002

More generally, if u(0) = z, integer > 2 and u(n) = a(n-1)^2 - 2 then u(n) = ceiling(c^(2^n)) where c = (1/2)*(z+sqrt(z^2-4)) is the largest root of x^2 - zx + 1 = 0. - Benoit Cloitre, Dec 03 2002

a(n) = (2+sqrt(3))^(2^n) + (2-sqrt(3))^(2^n). - John Sillcox (johnsillcox(AT)hotmail.com), Sep 20 2003

a(n) = ceiling(tan(5*Pi/12)^(2^n)). Note: 5*Pi/12 radians is 75 degrees. - Jason M. Follas (jasonfollas(AT)hotmail.com), Jan 16 2004

Sum_{n >= 0} 1/( Product_{k = 0..n} a(k) ) = 2 - sqrt(3). - Paul D. Hanna, Aug 11 2004

From Ulrich Sondermann, Sep 04 2006: (Start)

To generate the n-th number in the sequence: let x = 2^(n-1), a = 2, b = sqrt(3). Take every other term of the binomial expansion (a+b)^x times 2.

E.g., for the 4th term: x = 2^(4-1) = 8, the binomial expansion is: a^8 + 7a^7 b + 28a^6 b^2 + 56a^5 b^3 + 70a^4 b^4 + 56a^3 b^5 + 28a^2 b^6 + 7a b^7 + b^8, every other term times 2: 2(a^8 + 28a^6 b^2 + 70a^4 b^4 + 28a^2 b^6 + b^8) = 2(256 + (28)(64)(3) + (70)(16)(9) + (28)(4)(27) + 81) = 2(18817) = 37634. (End)

a(n) = 2*cosh( 2^(n-1)*log(sqrt(3)+2) ) For n > 0, a(n) = 2 + 3 * 4^n * (Product_{k=0..n-2} (a(k)/2))^2, where a(k)/2 = A002812(k) is a coprime sequence. - M. F. Hasler, Mar 09 2007

a(n) = A003500(2^n). - John Blythe Dobson, Oct 28 2007

a(n) = 2*T(2^n,2) where T(n,x) is the Chebyshev polynomial of the first kind. - Leonid Bedratyuk, Mar 17 2011

Engel expansion of 2 - sqrt(3). Thus 2 - sqrt(3) = 1/4 + 1/(4*14) + 1/(4*14*194) + ... as noted by Hanna above. See Liardet and Stambul. Cf. A001566, A003423 and A003487. - Peter Bala, Oct 31 2012

From Peter Bala, Nov 11 2012: (Start)

2*sqrt(3)/5 = Product_{n = 0..oo} (1 - 1/a(n)).

sqrt(3) = Product_{n = 0..oo} (1 + 2/a(n)).

a(n) - 1 = A145503(n+1).

a(n) = 2*A002812(n). (End)

a(n+1) - a(n) = a(n)^2 - a(n-1)^2. - Thomas Ordowski, Dec 24 2016

a(n) = 2*cos(2^n * arccos(2)). - Ryan Brooks, Oct 27 2020

From Peter Bala, Dec 06 2022: (Start)

a(n) = 2 + 2*Product_{k = 0..n-1} (a(k) + 2) for n >= 1.

Let b(n) = a(n) - 4. The sequence {b(n)} appears to be a strong divisibility sequence, that is, gcd(b(n),b(m)) = b(gcd(n,m)) for n, m >= 1. (End)

Extensions

One more term from Thomas A. Rockwell (LlewkcoRAT(AT)aol.com), Jan 18 2005