TIL...... [modified]
-
OK...
p^2 - 24*p + 143 = 0So..?a quadratic equation like that has at most two solutions, so it is hardly a way to discover lots of primes. :)
Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, and improve readability.
modified on Thursday, November 4, 2010 12:05 PM
-
...an extraordinary fact - probably known to half of you, but nevertheless I thought I'd share it. It's not an alogorithm, but never mind! The square of any prime number >= 5 can be expressed as 1 + a multiple of 24 or
If p is prime, then p ^ 2 = 1 + 24 * n, for some nDon't know about you, but I think that's quite amazing. Why is it true at all, and given that it is, where does 24 come from?! (Pity it's not 42 really!) [edit] When I ask "where does 24 come from?" I am not asking for a mathermatical proof - I can look that up myself. It's more just a metaphysical musing...)modified on Thursday, November 4, 2010 6:37 AM
that is correct, even when n needs to be 1/8 for p=2. :-D
Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, and improve readability.
-
a quadratic equation like that has at most two solutions, so it is hardly a way to discover lots of primes. :)
Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, and improve readability.
modified on Thursday, November 4, 2010 12:05 PM
We have a saying round here: "Don't tell I, tell 'e"... especially as that particular one doesn't even have any (real) solutions at all!
-
that is correct, even when n needs to be 1/8 for p=2. :-D
Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, and improve readability.
Actually, that's QI.. it also "works" for p=3 (n=1/3) - so in fact, the *only* value of p for which n is neither an integer nor a proper fraction is 4.[edit] OOPS what an idiot! since when was 4 a prime! :-O
-
Me :confused: too - ome of us is being a bit dumb here (most likely me...) I just re-wrote the equation you posted... what does it prove? Is there a typo in it (yours)?
-
We have a saying round here: "Don't tell I, tell 'e"... especially as that particular one doesn't even have any (real) solutions at all!
you'll have more luck with
x2 + x + 41
for natural values of x. :)
Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, and improve readability.
-
No typo as far as I am aware. I just thought you wanted to know what was the value of 'n' in your original question.
Just say 'NO' to evaluated arguments for diadic functions! Ash
Ah, got you - except that it doesn't work for all values of p p=5, n=1 != p-6 p=7, n=2 != p-6 p=11, n=5 ok p=13, n=7 ok p=17, n=12 != p-6 ...
-
you'll have more luck with
x2 + x + 41
for natural values of x. :)
Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, and improve readability.
Now you're just confusing me....
-
...an extraordinary fact - probably known to half of you, but nevertheless I thought I'd share it. It's not an alogorithm, but never mind! The square of any prime number >= 5 can be expressed as 1 + a multiple of 24 or
If p is prime, then p ^ 2 = 1 + 24 * n, for some nDon't know about you, but I think that's quite amazing. Why is it true at all, and given that it is, where does 24 come from?! (Pity it's not 42 really!) [edit] When I ask "where does 24 come from?" I am not asking for a mathermatical proof - I can look that up myself. It's more just a metaphysical musing...)modified on Thursday, November 4, 2010 6:37 AM
Well, I know you are not asking for a mathematical proof, but like I am much better at maths than metaphisics... Where does 24 come from? Since p is prime and greater than 5, p cannot be an even number. So: p2-1=(p-1)*(p+1). Like p is odd, both (p-1) and (p+1) are even, so we can say: p2-1=2a*2b=4ab. Like (p-1) and (p+1) are two consecutive even numbers, one of them must be multiple of 4, so 2a is multiple of 4 or 2b is multiple of 4, so we can express this like: p2-1=4a*2c=8ac or p2-1=4b*2d=8bd I will examine just one of these two cases becouse they are symmetrical. Now, like (p-1) and (p+1) are two consecutive even numbers, one of them must be multiple of 3, so: p2-1=8a*3d=24ad or p2-1=8c*3e=24ce And there it is.
-
Well, I know you are not asking for a mathematical proof, but like I am much better at maths than metaphisics... Where does 24 come from? Since p is prime and greater than 5, p cannot be an even number. So: p2-1=(p-1)*(p+1). Like p is odd, both (p-1) and (p+1) are even, so we can say: p2-1=2a*2b=4ab. Like (p-1) and (p+1) are two consecutive even numbers, one of them must be multiple of 4, so 2a is multiple of 4 or 2b is multiple of 4, so we can express this like: p2-1=4a*2c=8ac or p2-1=4b*2d=8bd I will examine just one of these two cases becouse they are symmetrical. Now, like (p-1) and (p+1) are two consecutive even numbers, one of them must be multiple of 3, so: p2-1=8a*3d=24ad or p2-1=8c*3e=24ce And there it is.
You haven't explained the last step correctly, and the statement
_Erik_ wrote:
Now, like (p-1) and (p+1) are two consecutive even numbers, one of them must be multiple of 3
is wrong.
-
You haven't explained the last step correctly, and the statement
_Erik_ wrote:
Now, like (p-1) and (p+1) are two consecutive even numbers, one of them must be multiple of 3
is wrong.
It is not wrong, becouse p is a prime number, what means: if p mod 3 = 1 then (p-1) mod 3=0, so (p-1) is multiple of 3. if p mod 3 = 2 then (p+1) mod 3=0, so (p+1) is multiple of 3. if p mod 3 = 0 then p would not be prime and we would not be following our premise
-
It is not wrong, becouse p is a prime number, what means: if p mod 3 = 1 then (p-1) mod 3=0, so (p-1) is multiple of 3. if p mod 3 = 2 then (p+1) mod 3=0, so (p+1) is multiple of 3. if p mod 3 = 0 then p would not be prime and we would not be following our premise
Yes, sorry - I was forgetting that p is prime! Time to knock off for the day I think...
-
Well, I know you are not asking for a mathematical proof, but like I am much better at maths than metaphisics... Where does 24 come from? Since p is prime and greater than 5, p cannot be an even number. So: p2-1=(p-1)*(p+1). Like p is odd, both (p-1) and (p+1) are even, so we can say: p2-1=2a*2b=4ab. Like (p-1) and (p+1) are two consecutive even numbers, one of them must be multiple of 4, so 2a is multiple of 4 or 2b is multiple of 4, so we can express this like: p2-1=4a*2c=8ac or p2-1=4b*2d=8bd I will examine just one of these two cases becouse they are symmetrical. Now, like (p-1) and (p+1) are two consecutive even numbers, one of them must be multiple of 3, so: p2-1=8a*3d=24ad or p2-1=8c*3e=24ce And there it is.
-
Try
p ^ 2 = 1 + 24 * (p - 6)
Just say 'NO' to evaluated arguments for diadic functions! Ash
-
...an extraordinary fact - probably known to half of you, but nevertheless I thought I'd share it. It's not an alogorithm, but never mind! The square of any prime number >= 5 can be expressed as 1 + a multiple of 24 or
If p is prime, then p ^ 2 = 1 + 24 * n, for some nDon't know about you, but I think that's quite amazing. Why is it true at all, and given that it is, where does 24 come from?! (Pity it's not 42 really!) [edit] When I ask "where does 24 come from?" I am not asking for a mathermatical proof - I can look that up myself. It's more just a metaphysical musing...)modified on Thursday, November 4, 2010 6:37 AM
-
...an extraordinary fact - probably known to half of you, but nevertheless I thought I'd share it. It's not an alogorithm, but never mind! The square of any prime number >= 5 can be expressed as 1 + a multiple of 24 or
If p is prime, then p ^ 2 = 1 + 24 * n, for some nDon't know about you, but I think that's quite amazing. Why is it true at all, and given that it is, where does 24 come from?! (Pity it's not 42 really!) [edit] When I ask "where does 24 come from?" I am not asking for a mathermatical proof - I can look that up myself. It's more just a metaphysical musing...)modified on Thursday, November 4, 2010 6:37 AM
For p = 5, p^2 = 24 * 1 + 1 All primes > 5 have the form p = 30*k + l, where l is 1, 7, 11, 13, 17, 19, 23 or 29. All other values of l have a common factor > 1 with 30, and therefore cannot produce primes. p^2 = 900*k^2 + 60*k*l + l^2 Rewrite the first 2 terms as 60*( 15*k^2 + k*l ). The sum in the parentheses is always even, so the entire expression is divisible by 24. We are left with l^2. By inspection: 1^2 = 24 * 0 + 1 7^2 = 24 * 2 + 1 11^2 = 24 * 5 + 1 13^2 = 24 * 7 + 1 17^2 = 24 * 12 + 1 19^2 = 24 * 15 + 1 23^2 = 24 * 22 + 1 29^2 = 24 * 35 + 1 QED
-
...an extraordinary fact - probably known to half of you, but nevertheless I thought I'd share it. It's not an alogorithm, but never mind! The square of any prime number >= 5 can be expressed as 1 + a multiple of 24 or
If p is prime, then p ^ 2 = 1 + 24 * n, for some nDon't know about you, but I think that's quite amazing. Why is it true at all, and given that it is, where does 24 come from?! (Pity it's not 42 really!) [edit] When I ask "where does 24 come from?" I am not asking for a mathermatical proof - I can look that up myself. It's more just a metaphysical musing...)modified on Thursday, November 4, 2010 6:37 AM
So to put it another way, to test the primality of any number, first square it, then mod it by 24. If the answer is 1, it's possibly prime. Nifty. Perhaps impractical for cryptological purposes, but nifty nonetheless. Reminds me of p = 6*n + 1 OR p = 6*n - 1 for all p given some n.
-
For p = 5, p^2 = 24 * 1 + 1 All primes > 5 have the form p = 30*k + l, where l is 1, 7, 11, 13, 17, 19, 23 or 29. All other values of l have a common factor > 1 with 30, and therefore cannot produce primes. p^2 = 900*k^2 + 60*k*l + l^2 Rewrite the first 2 terms as 60*( 15*k^2 + k*l ). The sum in the parentheses is always even, so the entire expression is divisible by 24. We are left with l^2. By inspection: 1^2 = 24 * 0 + 1 7^2 = 24 * 2 + 1 11^2 = 24 * 5 + 1 13^2 = 24 * 7 + 1 17^2 = 24 * 12 + 1 19^2 = 24 * 15 + 1 23^2 = 24 * 22 + 1 29^2 = 24 * 35 + 1 QED
Daniel Pfeffer wrote:
All primes > 5 have the form p = 30*k + l, where l is 1, 7, 11, 13, 17, 19, 23 or 29. All other values of l have a common factor > 1 with 30, and therefore cannot produce primes.
That's quite an assertion... not saying it's wrong, but it can't be s starting point for a proof of anything; it has to be proved first. Surely.
-
...an extraordinary fact - probably known to half of you, but nevertheless I thought I'd share it. It's not an alogorithm, but never mind! The square of any prime number >= 5 can be expressed as 1 + a multiple of 24 or
If p is prime, then p ^ 2 = 1 + 24 * n, for some nDon't know about you, but I think that's quite amazing. Why is it true at all, and given that it is, where does 24 come from?! (Pity it's not 42 really!) [edit] When I ask "where does 24 come from?" I am not asking for a mathermatical proof - I can look that up myself. It's more just a metaphysical musing...)modified on Thursday, November 4, 2010 6:37 AM
NeverHeardOfMe wrote:
If p is prime, then p ^ 2 = 1 + 24 * n, for some n Don't know about you, but I think that's quite amazing. Why is it true at all, and given that it is, where does 24 come from?! (Pity it's not 42 really!)
It only needs a small modification to use 42: If p is prime and p > 7 then
p^6 = 1 + 42n for some n
Peter "Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
modified on Wednesday, November 10, 2010 11:37 PM
-
...an extraordinary fact - probably known to half of you, but nevertheless I thought I'd share it. It's not an alogorithm, but never mind! The square of any prime number >= 5 can be expressed as 1 + a multiple of 24 or
If p is prime, then p ^ 2 = 1 + 24 * n, for some nDon't know about you, but I think that's quite amazing. Why is it true at all, and given that it is, where does 24 come from?! (Pity it's not 42 really!) [edit] When I ask "where does 24 come from?" I am not asking for a mathermatical proof - I can look that up myself. It's more just a metaphysical musing...)modified on Thursday, November 4, 2010 6:37 AM
Your algorithm finds the nth prime with reasonable speed. If you eliminate the (1 + (24 * N))^.5 that are not integers the calculation is almost trivial. This could be very useful in cryptographic and password gen. apps.
"Coding for fun and profit ... mostly fun"