A003010 -id:A003010 - cp's OEIS frontend

4, 14, 194, 37634, 7031978, 7033660, 1176429, 7643358, 3179743, 2694768, 763525, 4182158, 7004001, 1531454, 5888805, 1140622, 4321431, 7041324, 2756392, 1280050, 6563009, 6107895

Offset: 0

Sergio Pimentel, Apr 04 2007

Since a(21) > 0, M(23) = 8388607 is composite. Mersenne numbers are only prime if a(p-2) = 0.

			a(21) = 6563009^2 - 2 mod 8388607 = 6107895.

Eric Weisstein's World of Mathematics, Lucas Lehmer Test.
Wikipedia, Lucas Lehmer Primality Test.

Cf. A095847, A003010, A129219, A129220, A129221, A129222, A129223, A129225, A129226, A001348.

a(0) = 4, a(n) = a(n-1)^2 mod 2^p-1. Last term: a(p-2).

A129226 Residues of the Lucas - Lehmer primality test for M(31) = 2147483647.

Original entry on oeis.org

4, 14, 194, 37634, 1416317954, 669670838, 1937259419, 425413602, 842014276, 12692426, 2044502122, 1119438707, 1190075270, 1450757861, 877666528, 630853853, 940321271, 512995887, 692931217, 1883625615, 1992425718

Offset: 0

Sergio Pimentel, Apr 04 2007

Since a(29) = 0, M(31) = 2147483647 is prime. Mersenne numbers are only prime if a(p-2) = 0.

			a(29) = 65536^2 - 2 mod 2147483647 = 0.

Dennis Martin, Table of n, a(n) for n = 0..29
Eric Weisstein's World of Mathematics, Lucas Lehmer Test.
Wikipedia, Lucas Lehmer Primality Test.

Cf. A095847, A003010, A129219, A129220, A129221, A129222, A129223, A129224, A129225, A001348.

p = 31; Mp = 2**p - 1
from itertools import accumulate
def f(anm1, _): return (anm1**2 - 2) % Mp
print(list(accumulate([4]*30, f))) # Michael S. Branicky, Apr 14 2021

a(0) = 4, a(n) = a(n-1)^2 mod 2^p-1. Last term: a(p-2).

A135927 a(n) = a(n-1)^2 - 2 with a(1) = 10.

Original entry on oeis.org

10, 98, 9602, 92198402, 8500545331353602, 72259270930397519221389558374402, 5221402235392591963136699520829303150191924374488750728808857602

Offset: 1

Ant King, Dec 07 2007

This is the Lucas-Lehmer sequence with starting value u(1) = 10 and the position of the zeros when it is reduced mod(2^p - 1) also gives the position of the Mersenne primes. As we have started with n = 1, these will occupy the (p - 1)th positions in the sequence. For example, the first 12 terms mod(2^13 - 1) are 10, 98, 1411, 506, 2113, 672, 1077, 4996, 2037, 4721, 128, 0 and hence 8191 is a Mersenne prime. The radicals in the above closed forms are the solutions to x^2 - 10x + 1 = 0.

			a(4) = 2*cosh(2^3*log(5 + 2*sqrt(6))) = 92198402.

Gabriel Klambauer, Summation of Series, Amer. Math. Monthly, Vol. 87, No. 2 (Feb., 1980), pp. 128-130.
Raphael M. Robinson, Mersenne and Fermat Numbers, Proceedings of the American Mathematical Society, Vol. 5, No. 5. (October 1954), pp. 842-846.
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.
Wikipedia, Engel expansion

Cf. A000668, A000043, A003010, A095847, A001566, A135928, A246723.

a[1] = 10; a[n_] := a[n] = a[n - 1]^2 - 2; a[#]&/@Range[7]

A135927 = [10]
for n in range(1, 8): A135927.append(A135927[-1]**2-2)
print(A135927) # Karl-Heinz Hofmann, Feb 01 2022

a(n) = 2*cosh(2^(n-1)*log(5 + 2*sqrt(6))) = exp(2^(n-1)*log(5 + 2*sqrt(6))) + exp(2^(n-1)*log(5 - 2*sqrt(6))) = (5 + 2*sqrt(6))^(2^(n-1)) + (5 - 2*sqrt(6))^(2^(n-1)) = ceiling(exp(2^(n-1)*log(5 + 2*sqrt(6)))) = ceiling((5 + 2*sqrt(6))^(2^(n-1))).
From Peter Bala, Feb 01 2022: (Start)
Product_{n >= 1} (1 + 2/a(n)) = (1/2)*sqrt(6); Product_{n >= 1} (1 - 1/a(n)) = (4/11)*sqrt(6).
Engel expansion of 5 - sqrt(24) = 1/a(1) + 1/(a(1)*a(2)) + 1/(a(1)*a(2)*a(3)) + .... See Klambauer, p. 130. (End)

A145503 a(n+1) = a(n)^2+2*a(n)-2 and a(1)=3.

Original entry on oeis.org

3, 13, 193, 37633, 1416317953, 2005956546822746113, 4023861667741036022825635656102100993

Offset: 1

Artur Jasinski, Oct 11 2008

General formula for a(n+1)=a(n)^2+2*a(n)-2 and a(1)=k+1 is a(n)=Floor[((k + Sqrt[k^2 + 4])/2)^(2^((n+1) - 1)).

Essentially the same as A110407. [R. J. Mathar, Mar 18 2009]

Indranil Ghosh, Table of n, a(n) for n = 1..11

Cf. A145502-A145510. A003010, A002812.

aa = {}; k = 3; Do[AppendTo[aa, k]; k = k^2 + 2 k - 2, {n, 1, 10}]; aa
(* or *)
k = 2; Table[Floor[((k + Sqrt[k^2 + 4])/2)^(2^(n - 1))], {n, 2, 7}]
NestList[#^2+2#-2&,3,10] (* Harvey P. Dale, Feb 01 2018 *)

From Peter Bala, Nov 12 2012: (Start)
a(n) = alpha^(2^(n-1)) + (1/alpha)^(2^(n-1)) - 1, where alpha := 2 + sqrt(3).
a(n) = A003010(n-1) - 1. a(n) = 2*A002812(n-1) - 1.
Recurrence: a(n) = 5*(Product {k = 1..n-1} a(k)) - 2 with a(1) = 3.
Product_{n >= 1} (1 + 1/a(n)) = 5/6*sqrt(3).
Product_{n >= 1} (1 + 2/(a(n) + 1)) = sqrt(3).
(End)

A219163 Recurrence equation a(n+1) = a(n)^4 - 4*a(n)^2 + 2 with a(0) = 4.

Original entry on oeis.org

4, 194, 1416317954, 4023861667741036022825635656102100994

Offset: 0

Peter Bala, Nov 13 2012

Bisection of A003010.

a(4) has 147 digits and a(5) has 586 digits. - Harvey P. Dale, Mar 03 2020

Cf. A001999, A003010, A003500, A219162, A219164, A219165.

NestList[#^4-4#^2+2&,4,5] (* Harvey P. Dale, Mar 03 2020 *)

a(n)={if(n==0,4,a(n-1)^4-4*a(n-1)^2+2)} \\ Edward Jiang, Sep 11 2014

Let alpha = 2 + sqrt(3). Then a(n) = (alpha)^(4^n) + (1/alpha)^(4^n).
a(n) = A003010(2*n) = A003500(4^n).
Product_{n >= 0} ((1 + 2/a(n))/(1 - 2/a(n)^2)) = sqrt(3).
From Peter Bala, Dec 06 2022: (Start)
a(n) = 2*T(4^n,2), where T(n,x) denotes the n-th Chebyshev polynomial of the first kind.
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)

A110407 Integers with mutual residues -2.

Original entry on oeis.org

3, 5, 13, 193, 37633, 1416317953, 2005956546822746113, 4023861667741036022825635656102100993, 16191462721115671781777559070120513664958590125499158514329308740975788033

Offset: 1

Seppo Mustonen, Sep 11 2005

nonn

This is the special case k=2 of sequences with mutual residues -k. In general, a(1)=k+1 and a(n)=min{m | m>a(n-1), mod(m,a(i))=-k, i=1,...,n-1}.

An infinite coprime sequence

S. Mustonen, On integer sequences with mutual k-residues

a:=proc(k,n::nonnegint) option remember; if n<3 then RETURN(n*k+1); fi; if n=3 then RETURN(a(k,1)*a(k,2)-k); fi; a(k,n-1)*(a(k,n-1)+k)-k; end; seq(a(2,n),n=1..9);

Join[{3,5},NestList[#^2+2#-2&,13,6]] (* Harvey P. Dale, Mar 05 2019 *)

a(1)=3, a(2)=5, a(n)=-2+a(1)*a(2)*...*a(n-1) [typo corrected by Vincenzo Librandi, Feb 08 2010]
a(n)=a(n-1)^2+2*a(n-1)-2, for n>3.
Apparently a(n)=A003010(n-2)-1 for n>=3. - R. J. Mathar, Apr 22 2007

A123271 Sign of the penultimate term of the Lucas-Lehmer sequence modulo the n-th Mersenne prime.

Original entry on oeis.org

1, 1, -1, 1, -1, -1, 1, 1, -1, -1, 1, -1, -1, -1, 1, -1, -1, 1, -1, -1, 1, -1, 1, -1, 1, -1, 1, 1, 1, -1, 1, -1, -1, 1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, -1, 1, -1

Offset: 2

Max Alekseyev, Oct 10 2006, Sep 29 2007

Also known as the Lehmer symbol ϵ(4, p) for Mersenne prime exponent p.
For the n-th Mersenne prime 2^p - 1 = A000668(n) (with p=A000043(n)), we have A003010(p-2) == 0 (mod 2^p - 1). Therefore A003010(p-3) == a(n) * 2^((p+1)/2) (mod 2^p - 1) where a(n) = 1 or -1.
From currently known Mersenne primes we have these exponents and sequence values: (74207281: -1, 77232917: 1, 82589933: -1, 136279841: 1), but there is a possibility of new Mersenne primes to be found out of order. - Serge Batalov, Feb 04 2013; updated by Max Alekseyev, Feb 25 2018, updated by Gord Palameta, Oct 21 2024

			From _Serge Batalov_, Feb 04 2013: (Start)
For n=3, p=5, M_p=31, and the Lucas-Lehmer sequence is (4, 14, 8, 0). The penultimate element is 1*2^3 == 8 (mod 31), so a(3)=1.
For n=4, p=7, M_p=127, and the Lucas-Lehmer sequence is (4, 14, 67, 42, 111, 0). The penultimate element is -1*2^4 == 111 (mod 127), so a(4)=-1.
(End)

Bastiaan Jansen, Mersenne primes and class field theory. Doctoral thesis, Leiden University, 2012.
Mersenne Forum, Penultimate Lucas-Lehmer step
Eric Weisstein's World of Mathematics, Lucas-Lehmer test

Cf. A000043, A000668, A003010.

test(p)=s=Mod(4, 2^p-1); for(i=1, p-3, s=s^2-2); r=2^((p+1)/2); if(s==+r,+1,s==-r,-1,"error") \\ Then a(n) = test(A000043(n)). From Jeppe Stig Nielsen, Jan 25 2016

a(n) = 1 or -1 such that A003010(A000043(n)-3) == a(n) * 2^((A000043(n)+1)/2) (mod A000668(n)).

More terms from Andreas Höglund, Sep 29 2007
a(40) added by Max Alekseyev, Feb 07 2011
a(41)-a(46) and prospective a(47)-a(48) from Andreas Höglund via Serge Batalov, Feb 04 2013; Max Alekseyev, Feb 25 2018
a(47) added by Gord Palameta, Dec 21 2018
a(48) added by Gord Palameta, Oct 21 2024

A128976 Number of cycles for the map LL:x->x^2-2 acting on Z/(2^n-1).

Original entry on oeis.org

2, 1, 1, 2, 2, 4, 6, 8, 6, 8, 14, 25, 36, 180, 76, 80, 66, 2068, 354, 7316, 740, 1776, 2198, 264, 792, 3278, 122396, 848, 17312, 27743, 36696, 17896832

Offset: 0

M. F. Hasler, Apr 29 2007, corrected May 19 2007

A cycle is the orbit of an element x of Z/(2^n-1), i.e., { x, LL(x), ..., LL^c(x)=x } for some positive integer c.

			a(0)=2 since fixed points 2 and -1 are the only cycles for LL on Z/(0) = Z;
a(1)=1 since Z/(1) = {0};
a(2)=1 since 2=-1 is a cycle of length 1 (fixed point) for LL on Z/(3) and LL(0)=-2=1, LL(1)=-1;
a(3)=2 since 3,4(=-3) -> 0 -> 5(=-2) -> {2} and 1 -> {6(=-1)} for LL acting on Z/(7);
a(5)=4 since {2}, {30}, {12,18} and {3,7,16,6} are the cycles for LL acting on Z/(31).

Troy Vasiga and Jeffrey Shallit, On the iteration of certain quadratic maps over GF(p), Discrete Math. 277 (2004) 219-240 (see also doi).

Cf. A003010.

numcycles(q) = { my(Mq=2^q-1, v=vector(Mq+1), c=1, i, start, cyc=0); if(q<2,return(1+!q)); for( j=1, #v, if(v[j],next); i=j; start=c; until(v[i=1+((i-1)^2-2)%Mq],v[i]=c++); if(v[i]>start, cyc++)); cyc; }
A128976=vector(20,i,numcycles(i-1))

If p=2^n-1 is prime, then a(n) = 1/2 + Sum_{d|2^(n-1)-1} eulerphi(d)/ordp(2,d)/2, where ordp(2,d) = min { e in N* | 2^e == 1 (mod d) or 2^e == -1 (mod d) }

a(20)-a(31) from Max Alekseyev, Aug 25 2023

cp's OEIS Frontend

A129222 Residues of the Lucas - Lehmer primality test for M(17) = 131071.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A129223 Residues of the Lucas - Lehmer primality test for M(19) = 524287.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A129224 Residues of the Lucas - Lehmer primality test for M(23) = 8388607.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A129226 Residues of the Lucas - Lehmer primality test for M(31) = 2147483647.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula

A135927 a(n) = a(n-1)^2 - 2 with a(1) = 10.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

A145503 a(n+1) = a(n)^2+2*a(n)-2 and a(1)=3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A219163 Recurrence equation a(n+1) = a(n)^4 - 4*a(n)^2 + 2 with a(0) = 4.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

Formula

A110407 Integers with mutual residues -2.

Views

Author

Keywords

Comments

Links

Programs

Maple

Mathematica