mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2006-12-19, 16:58   #1
hoca
 
hoca's Avatar
 
Dec 2006

3 Posts
Default New LLT formula

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)
hoca is offline   Reply With Quote
Old 2006-12-19, 21:12   #2
maxal
 
maxal's Avatar
 
Feb 2005

22×5×13 Posts
Default

Quote:
Originally Posted by hoca View Post
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)?

Last fiddled with by maxal on 2006-12-19 at 21:13
maxal is offline   Reply With Quote
Old 2006-12-20, 10:09   #3
hoca
 
hoca's Avatar
 
Dec 2006

3 Posts
Default

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
hoca is offline   Reply With Quote
Old 2006-12-20, 14:40   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

23×937 Posts
Default

Quote:
Originally Posted by hoca View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2006-12-20, 20:13   #5
Fusion_power
 
Fusion_power's Avatar
 
Aug 2003
Snicker, AL

17008 Posts
Default

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

Fusion
Fusion_power is offline   Reply With Quote
Old 2006-12-21, 01:10   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

23×937 Posts
Default

Quote:
Originally Posted by Fusion_power View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2007-03-05, 17:36   #7
m_f_h
 
m_f_h's Avatar
 
Feb 2007

24·33 Posts
Default

(*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 ...

Last fiddled with by m_f_h on 2007-03-05 at 17:47 Reason: removed title which consisted in ill-defined clipboard contents (copy-paste did not work directly into editing area...)
m_f_h is offline   Reply With Quote
Old 2007-03-05, 17:41   #8
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

2·32·653 Posts
Default

Quote:
Originally Posted by Fusion_power View Post
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...
ewmayer is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
How do I run this formula in PFGW? Stargate38 Software 1 2014-08-19 15:23
Interesting formulæ Uncwilly Lounge 29 2013-05-05 16:12
Fibonacci Formula MattcAnderson Math 7 2013-01-14 23:29
P-1 formula (help wanted) Prime95 Data 18 2012-02-12 18:07
Combination Formula? drake2 Math 10 2006-12-08 22:43

All times are UTC. The time now is 19:28.


Fri Dec 9 19:28:00 UTC 2022 up 113 days, 16:56, 0 users, load averages: 0.89, 1.14, 1.10

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔