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

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

Author

Max Alekseyev, Oct 10 2006, Sep 29 2007

Keywords

• more
• sign

Comments

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

Examples

			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)
		

Links

• 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

Crossrefs

Cf. A000043, A000668, A003010.

Programs

PARI

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

Formula

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

Extensions

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