mersenneforum.org  

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

Reply
 
Thread Tools
Old 2009-09-18, 08:23   #12
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

19×181 Posts
Default

Quote:
Originally Posted by storm5510 View Post
2P - 1, where P is any even number
p stands for prime, so its not even except for p=2. Think of it as:

2prime-1


Here is the proof that exponent has to be prime for 2p-1 can be prime:
http://primes.utm.edu/notes/proofs/Theorem2.html
ATH is offline   Reply With Quote
Old 2009-09-18, 09:05   #13
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2×7×461 Posts
Default

Quote:
Originally Posted by storm5510 View Post
Be it stupid, or not, here's what I am looking for:

I have an application which I can punch a number into. The purpose is to see if it is a prime number. It doesn't matter what type.

The conventional way is to iterate all the way up to the square root of said number in steps of two, starting at three, while skipping multiples of five.

This can be time consuming if a very large number is entered. Is there a more time-efficient method?
Yes, there are many; some which prove that the number is prime and some which have an incredibly tiny probability of calling some composite numbers prime. All of them define a group whose order is known if the number is prime and then try to demonstrate that the group has the claimed order.

http://www.mersennewiki.org/index.php/Primality_test is probably a good place to start.

Implementing the easy algorithms is straightforward, but the hard ones can get really quite fiddly; fortunately a group at the University of Bordeaux produced pari-gp, where you can type

Code:
? isprime(83^57+318)
%4 = 1
? nextprime(10^1000)-10^1000
time = 2,785 ms.
%5 = 453

Last fiddled with by fivemack on 2009-09-18 at 09:08
fivemack is offline   Reply With Quote
Old 2009-09-18, 11:20   #14
TimSorbet
Account Deleted
 
TimSorbet's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

11·389 Posts
Default

Also, Wikipedia in general and this template in particular is a great source of info regarding primality tests, etc.
http://en.wikipedia.org/wiki/Templat...tic_algorithms
TimSorbet is offline   Reply With Quote
Old 2009-09-18, 12:35   #15
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

22·1,877 Posts
Default

Quote:
Originally Posted by storm5510 View Post
Be it stupid, or not, here's what I am looking for:

I have an application which I can punch a number into. The purpose is to see if it is a prime number. It doesn't matter what type.

The conventional way is to iterate all the way up to the square root of said number in steps of two, starting at three, while skipping multiples of five.
This is NOT the conventional way.

Is doing a google search too much work? There is a LOT of
information available.
R.D. Silverman is offline   Reply With Quote
Old 2009-09-18, 12:40   #16
TimSorbet
Account Deleted
 
TimSorbet's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

11·389 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
This is NOT the conventional way.
Replace "conventional" with "naive" or "obvious" or "simple" or ...
TimSorbet is offline   Reply With Quote
Old 2009-09-18, 12:51   #17
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

11101010101002 Posts
Default

Quote:
Originally Posted by storm5510 View Post
2P - 1, where P is any even number. Subtract 1 and it becomes odd, then an exponent of 2.

3, 7, 15, 31, 63, 127, 255 .... 2097151, 4194303, so forth, and so on, what not, and what have you.

...
Still clueless, I see. Even after you have been TOLD what a
Mersenne number is, you still haven't gotten it right.

Firstly, you state that P is an even number! then your example:
"3, 7, 15, 31, 63, 127, 255 .... 2097151, 4194303, so forth"

gives instances where P is odd!!! Don't you even know the difference
between odd and even??? One has to be a total moron to state that
a Mersenne number is 2^P-1, where P is EVEN, then to
immediately give a numerical example where P is ODD.


And the expression "Subract 1 and it becomes odd, then an exponent of 2"
is GIBBERISH. The phrase "then an exponent of 2" is NONSENSE.

A Mersenne number is a number of the form 2^p-1, where p is PRIME
(i.e. not even, except for p=2).

And, of course, it is clear that you never learned basic first year
junior high school algebra. 2^(2k) - 1 can NEVER be prime, except for
k = 1. It is the difference of two squares. Where you got the idea
that it might ever be prime, I have no idea.

Give it up. You lack even the basic math background to dabble in this
subject and you appear to be too lazy to do even a simple web search
on "prime algorithms". Go back to grammar school. Come back here
when you are ready to exhibit some scholarly discipline.
R.D. Silverman is offline   Reply With Quote
Old 2009-09-18, 12:59   #18
Dougal
 
Dougal's Avatar
 
Jan 2009
Ireland

2·3·31 Posts
Default

if i make a statement,which is wrong.then give several examples of it which are right,i think you would have to be a moron to think that i gave correct examples without knowing what i was talking about.my statement could of been worded wrong quite easily,and i think his example shows quite clearly what a mersenne number is,even if the statement was worded incorrect,possibly by accident.

Last fiddled with by Dougal on 2009-09-18 at 13:08
Dougal is offline   Reply With Quote
Old 2009-09-18, 13:03   #19
Dougal
 
Dougal's Avatar
 
Jan 2009
Ireland

BA16 Posts
Default

also,one of the definitions of a mersenne number is that p is prime.another is that p is a positive integer.i could easily accuse you of not knowing your definitions.
Dougal is offline   Reply With Quote
Old 2009-09-18, 13:12   #20
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

22×1,877 Posts
Default

Quote:
Originally Posted by Dougal View Post
if i make a statement,which is wrong.then give several examples of it which are right,
Also mixed in are clear examples that are wrong. Which basically
shows that what is being written is just random nonsense.

Quote:

i think you would have to be a moron to think that i gave correct examplse without knowing what i was talking about.my statement could of been worded wrong quite easily,and i think his example shows quite clearly what a mersenne number is,even if the statement was worded incorrect,possibly by accident.
Another imbecile. And you apparently do not know:

(1) Sentences are capitalized.
(2) The word "I" is capitalized.
(3) How to spell.
(4) Basic grammar: "could of been" --> "could have been"
(Although I will give the benefit of the doubt here. English may
not be your first language; If it is your first language, then you
are even dumber than I thought)
(5) Proper names (i.e. Mersenne) are capitalized.


Go away. Come back when you can write cogent sentences above
2nd grade level. Come back when you learn to read. Go back to school.
Study very hard. When your IQ reaches 75, SELL. You will make a profit.
R.D. Silverman is offline   Reply With Quote
Old 2009-09-18, 13:17   #21
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

5,987 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
(5) Proper names (i.e. Mersenne) are capitalized.
((Insert joke about Abel here))
CRGreathouse is offline   Reply With Quote
Old 2009-09-24, 21:29   #22
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

93310 Posts
Default LLT for Fermat numbers

Quote:
Originally Posted by fivemack View Post
257 is not a number of the form 2^p-1, and the Lucas-Lehmer test is only defined for numbers of that form.
The LLT for Mersenne numbers, you mean to say. But if you use the LLT for Fermat numbers, that works !

Use s=5 as the seed, and do 2^n-2 steps. Since 257=2^8+1=2^(2^3)+1, you need 6 steps :

5 -> 23 -> -> 13 -> 167 -> 131 -> 197 -> 0 BINGO ! it's a prime ! (I knew that... :)

Look at the proof from this page.

Tony

Last fiddled with by T.Rex on 2009-09-24 at 21:30
T.Rex is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Modifying the Lucas Lehmer Primality Test into a fast test of nothing Trilo Miscellaneous Math 25 2018-03-11 23:20
A second proof for the Lucas-Lehmer Test carpetpool Miscellaneous Math 2 2017-07-30 09:21
Lucas-Lehmer test Mathsgirl Information & Answers 23 2014-12-10 16:25
Lucas Lehmer test question? BMgf Programming 23 2003-12-09 08:52
about Lucas-Lehmer test and Prime 95 Annunaki Math 22 2003-08-05 21:52

All times are UTC. The time now is 08:36.


Tue Feb 7 08:36:16 UTC 2023 up 173 days, 6:04, 1 user, load averages: 1.25, 1.13, 1.01

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, 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.

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