New LLT formula

[hoca]

i use this formula to check primality of Mersenne numbers.
S(0)=2
S(n)=2*S(n-1) - 1

and generalized form is :

S(0)=2^(2-r)
S(n)=(2^r)*S(n-1) - 2^(1-r)

[maxal]

Originally Posted by hoca

i use this formula to check primality of Mersenne numbers.
S(0)=2
S(n)=2*S(n-1) - 1

It can be easily shown by induction that S(n) = 2^n + 1.
How do you test primality of M_p using these numbers S(n)?

[hoca]

opps sorry i forgot square of S(n-1)
S(0)=2
S(n)=2*S(n-1)^2 - 1;

and generalized form is :
S(0)=2^(2-r)
S(n)=(2^r)*S(n-1)^2 - 2^(1-r)

forexample:
S(0)=2
S(1)=2*2^2-1=7 =0 Mod(2^3-1)
s(2)=2*7^2-1=97
s(3)=2*97^2-1=18817 =0 mod(2^5-1) and so on...

OR
s(n)=4*s(n-1)^2-1/2

s(0)=1
s(1)=4*1^2-1/2=7/2 =0 mod(7)
s(2)=4*(7/2)^2-1/2=97/2
s(3)=4*(97/2)^2-1/2=18817/2=0 mod(31)
....

pls any comment to proof or explain

[R.D. Silverman]

Originally Posted by hoca

opps sorry i forgot square of S(n-1)
S(0)=2
S(n)=2*S(n-1)^2 - 1;

Working mod M_p throughout:

This is just LL slightly disguised. Multiply by 2 giving:

2S(n) = 4S(n-1)^2 - 2 = [2 S(n-1)]^2 - 2

Compare the arithmetic for (say) M_5. In Your sequence we
get: 2,7,4,1,0, while the ordinary LL gives 4,14,8,2,0.

All you have done is divided the original sequence by 2. (or multiplied
by 2^-1 mod M_p)

Working (say) mod 127, LL gives 4,14,67,42,111,0 while
you sequence gives 2,7,97, ... etc.

Note that 97 = 67/2 mod 127 etc.

[Fusion_power]

Translated into common terms, it means your method is not an improvement of the existing method. Its just a variant.

Fusion

[R.D. Silverman]

Originally Posted by Fusion_power

Translated into common terms, it means your method is not an improvement of the existing method. Its just a variant.

Fusion

It isn't really a variant. It is simply multiplying the sequence by a
constant. (2^-1 mod N) It is also SLOWER.

[m_f_h]

(*stumble in, some months late*)
This sequence is also called A2812 on OEIS.
It gives S(k) not only through the already mentioned relations,
but also through the following great formula : ((c) by M_F_H !)
For k>3,
S(k) = 2 + 2^(2k) x 3 x product( A2812(i), i = 1..k-3 )^2

Unfortunately, this did not help me for my ultimate goal :
calculate S(p-1) mod 2^p-1
as an explicit function of p and S(p-2) mod 2^(p-1)-1 ...

[ewmayer]

Originally Posted by Fusion_power

Translated into common terms, it means your method is not an improvement of the existing method. Its just a variant.

Which is about as good as can be expected from such an "ad hoca" approach...