|
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.
|
|
|
|
|
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
|
|
|
|
|
Hello cp9876,
the correct formula is actually
p^6 = 1 + 84n for some n, and p being a prime >7 With 84 = 2 * 42, your version is not wrong either, but only half of the truth.
At a first glance, it looked like a big step forward to proving the universal truth and meaning of everything (which is said to be 42), but as soon as I started to find the proof, doubts were shed on this old belief.
Let me now prove my version of the formula, following the steps outlined by _Erik_ previously in this thread.
We have to show that p^6 - 1 can be divided by 84, and I will do that by showing that it can be divided by 4, 3, and 7 (because 4*3*7=84) at the same time.
The first two factors are quite trivial:
I) (p^6 - 1) = (p^3 - 1) * (p^3 + 1), since p is prime and > 2, it is an odd number, thus
p^3 is an odd number, and consequently both (p^3 - 1) and (p^3 + 1) are even numbers, hence:
(p^6 - 1) = (p^3 - 1) * (p^3 + 1) = 2*a * 2*b = 4*a*b
II) With p being a prime and p > 3,
p^3 is an odd number which cannot be divided by 3. Consequently, either (p^3 - 1) (x)or (p^3 + 1) can be divided by 3 (for a more detailed proof of this, see a post from _Erik_ above). Hence:
(p^6 - 1) = (p^3 - 1) * (p^3 + 1) = 3*c * d
III) I did not find a smart proof for that "7", but the number of cases can be simply enumerated:
With p being prime and > 7,
p = (7*o + e) with o being an odd integer and e an even integer in {2; 4; 6; 8; 10; 12}
Now we have to prove that either (p^3 - 1) (x)or (p^3 + 1) can be divided by 7.
p^3 = (7*o + e)^3 = (7*o)^3 + 3*e*(7*o)^2 + 3*(7*o)*e^2 + e^3
It is easy to see that each of the summands (7*o)^3, 3*e*(7*o)^2, 3*(7*o)*e^2 can be divided by 7. We need to concentrate only on e^3: either e^3+1 (x)or e^3-1 must be dividable by 7. I enumerate all the 6 possible cases and then dicide for +1 or -1:
- e=2: e^3= 8 => -1
- e=4: e^3= 64 => -1
- e=6: e^3= 216 => +1
- e=8: e^3= 512 => +1
- e=10: e^3=1000 => +1
- e=12: e^3=1728 => +1 Now we can write:
(p^6 - 1) = (p^3 - 1) * (p^3 + 1) = 7*e * f
And consequently here it is:
(p^6 - 1) = (p^3 - 1) * (p^3 + 1) = 4*3*7*n
Now we must recognize the full proven truth of 84.
Previously, we were told half of the truth only.
Knowing this new proven truth, which replaces the old believe of 42 and proves it at the same time, we can look forward to an even brighter future.
|
|
|
|
|
for Bernard proveth that if p > 7 then
p^6 = 1 + 84n
and thus 84 is the full proven truth, twice the truth of 42.
However 84 is but an imposter of the full proven truth.
As Bernard showeth, for p an odd prime, p^3 is an odd number, and consequently both (p^3 - 1) and (p^3 + 1) are even, but as they are consecutive even numbers then one must be divisible by 4, hence:
(p^6 - 1) = (p^3 - 1) * (p^3 + 1) = 2*a * 4*b = 8*a*b
Thus we have the next full proven truth that
p^6 = 1 + 168n
But there is more...
As p is prime, then the residue modulo 9 shall be one of {+/- 1, +/- 2, +/- 4} which using the fact that 2^3 = 8 = -1(mod 9), and 4 = 2^2 so 4^3 = 2^6 = 1(mod 9), then p^3 = +/- 1 (mod 9), then p^6 = 1 (mod 9) and hence:
(p^6 - 1) = 9*c
And so we have the next proven truth that if p is prime and p is not 2,3 or 7 then:
p^6 = 1 + 504n
and the full truth is that there is no number higher than 504 to satisfy this.
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."
|
|
|
|
|
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"
|
|
|
|
|
hi
i look for a formula to calc new width and height of an image after rotation with given angle.
look at this image (the square rotate 45 degrees):
thanks
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
