|
Yes, for
p=5, n=1
p=7, n=2
p=11, n=5
p=13, n=7
If you can work out a forumla that spits out each value of n that produces the "next" prime, you'll be able to retire early
|
|
|
|
|
Try
p ^ 2 = 1 + 24 * (p - 6)
Just say 'NO' to evaluated arguments for diadic functions! Ash
|
|
|
|
|
OK...
p^2 - 24*p + 143 = 0
So..?
|
|
|
|
|
Just say 'NO' to evaluated arguments for diadic functions! Ash
|
|
|
|
|
Me 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)?
|
|
|
|
|
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
...
|
|
|
|
|
a quadratic equation like that has at most two solutions, so it is hardly a way to discover lots of primes.
|
|
|
|
|
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
x<sup>2</sup> + x + 41
for natural values of x.
|
|
|
|
|
Now you're just confusing me....
|
|
|
|
|
actually that's not correct; when p=7 then by your formula we would have 49=1+24*1 = 25
|
|
|
|
|
that is correct, even when n needs to be 1/8 for p=2.
|
|
|
|
|
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!
|
|
|
|
|
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.
|
|
|
|
|
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...
|
|
|
|
|
3 cheers !!
All are born right-handed. Only gifted few overcome it.
There's NO excuse for not commenting your code.
|
|
|
|
|
WolramAlpha say that the equation p^2 = 24*d*e+1
is a hyperboloid of one sheet
which means that it is of the form x^2/a^2 + y^2/b^2 - z^2/c^2 = 1
|
|
|
|
|
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.
|
|
|
|
|
NeverHeardOfMe wrote: 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.
I have simply performed the first three steps of the Sieve of Erathostenes, eliminating all numbers divisible by 2, 3 or 5, as follows:
30 is the product of the first three primes (2 * 3 * 5).
All integers may be represented as n = 30*k + l where k is any integer, and l is any integer in the range { 0..29 }.
Of these integers:
Any integers of the form 30*k + {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28} are divisible by 2.
Any integers of the form 30*k + {0, 3, 6, 9, 12, 15, 18, 21, 24, 27} are divisible by 3.
Any integers of the form 30*k + {0, 5, 10, 15, 20, 25} are divisible by 5.
When all integers known to be divisible by 2, 3, or 5 are removed, we are left with 30*k + {1, 7, 11, 13, 17, 19, 23, 29} that MAY be prime.
|
|
|
|
|
Now that I think of it, there is no need to carry the Sieve of Erathostenes beyond the second step.
All numbers may be written in the form n = 6*k +l where k is any integer and l = { 0.. 5 }.
Numbers of the form 6*k + {0, 2, 4} are divisible by 2.
Numbers of the form 6*k + {0, 3} are divisible by 3
Numbers of the form 6*k + {1, 5} MAY be prime. With the exception of {2,3} {which are divisible by 2 and by 3, respectively), all primes fit this template.
p^2 = {6*k + l)^2
p^2 = 36*k^2 + 12*k*l + l^2
p^2 = 12*(3*k^2 + k*l} + l^2
The value in the parentheses is always even, and therefore the first term is divisible by 24. We are left with l^2.
By inspection:
1^2 = 1 = 24*0 + 1
5^2 = 25 = 24*1 + 1
QED
|
|
|
|
|
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.
|
|
|
|
|