mersenneforum.org > Math New LLT formula
 Register FAQ Search Today's Posts Mark Forums Read

 2006-12-19, 16:58 #1 hoca     Dec 2006 3 Posts 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)
2006-12-19, 21:12   #2
maxal

Feb 2005

1000001002 Posts

Quote:
 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)?

Last fiddled with by maxal on 2006-12-19 at 21:13

 2006-12-20, 10:09 #3 hoca     Dec 2006 3 Posts 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
2006-12-20, 14:40   #4
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

2·3,779 Posts

Quote:
 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.

 2006-12-20, 20:13 #5 Fusion_power     Aug 2003 Snicker, AL 26×3×5 Posts Translated into common terms, it means your method is not an improvement of the existing method. Its just a variant. Fusion
2006-12-21, 01:10   #6
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

2·3,779 Posts

Quote:
 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.

 2007-03-05, 17:36 #7 m_f_h     Feb 2007 24·33 Posts (*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...)
2007-03-05, 17:41   #8
ewmayer
2ω=0

Sep 2002
República de California

101101111011002 Posts

Quote:
 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...

 Similar Threads Thread Thread Starter Forum Replies Last Post Stargate38 Software 1 2014-08-19 15:23 Uncwilly Lounge 29 2013-05-05 16:12 MattcAnderson Math 7 2013-01-14 23:29 Prime95 Data 18 2012-02-12 18:07 drake2 Math 10 2006-12-08 22:43

All times are UTC. The time now is 11:16.

Fri Jun 9 11:16:58 UTC 2023 up 295 days, 8:45, 0 users, load averages: 1.81, 0.98, 0.82

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.

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