|
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
|
|
|
|
|
Hi,
when you rotate a point [x,y] over an angle alpha its coordinates become:
xNew=x*cos(alpha)+y*sin(alpha);
yNew=-x*sin)alpha)+y*cos(alpha);
If you apply this to the four corners, then subtract to get width and height, you would get:
widNew=wid*abs(cos(alpha))+hei*abs(sin(alpha));
heiNew=wid*abs(sin(alpha))+hei*abs(cos(alpha));
[EDIT] added abs functions [/EDIT]
|
|
|
|
|
The formulas that you post for the rotation are right, but there is an error on the second couple of equations. They should be:
new_width = abs( width * cos(alpha) + height * sin(alpha))
new_height = abs(-width * sin(alpha) + height * cos(alpha))
|
|
|
|
|
and why would I add a monadic minus to a subexpression of which I only need the absolute value???
|
|
|
|
|
Read carefully the formula:
rotated_x = x * cos(alpha) + y * sin(alpha)
rotated_y = -x * sin(alpha) + y * cos(alpha)
What you need is abs(rotated_y) which is:
new_height = abs(-width * sin(alpha) + height * cos(alpha))
And this is different from the sum of abs of each component:
abs(-width * sin(alpha)) + abs(height * cos(alpha))
^
|
+- This is the minus that you are talking about, I suppose
|
|
|
|
|
If you use alpha = 45 degrees and x = width = height, you get
abs(-x * sqrt(2) / 2 + x * sqrt(2) / 2)
Rename:
abs(-x * a + x * a)
Cancel out:
abs(0)
I'm pretty sure you're not supposed to get 0 as the new height for an angle of 45 degrees
For Luc's formula you get x * sqrt(2) (which fits with the Pythagorean theorem)
|
|
|
|
|
You are right! What I got is the absolute value of the position of the corner, not the width and height!
This demonstrates that it's not good for me to post answers in the late evening! 
Sorry!
|
|
|
|
|
|
Hello Guyz,
Can someone please show me how to eveluate
y=(1-R)^2.3
|
|
|
|
|
y = (1 - R) ^ (23 / 10)
C'mon kid, crack that book.
Tadeusz Westawic
Sum quid sum.
|
|
|
|
|
What algorithm can I solve this pensions problem?
A Company's Net Income(NI) is to be distributes to members based on their monthly contributions(MC) and a common rate(R)and a variant power(P) where P is n/12 and n is the month.
The equation is
I=((((1+R/100)^P)-1)*MC) where I is interest for a particular month.
Hence NI=i1+I2+I3+.....In
How can I find the unknown which is the Rate R?
I really need your help
Thanks
|
|
|
|
|
Surely the rate (R) needs to be set in advance by the fund's trustees. Or am I totally misunderstanding the issue?
Just say 'NO' to evaluated arguments for diadic functions! Ash
|
|
|
|
|
I agree with you, this thing might be impossible.
This is the scenario, the client has Net Income that it wants to distribute to members based on an unknown Rate such that the sum of all the Interest earned on month contributions will sum up to this Net Income.
Thank You
|
|
|
|
|
It's some years since I did formulae like this so I am afraid the best I can suggest is to take a look here[^] for some possible suggestions.
Just say 'NO' to evaluated arguments for diadic functions! Ash
|
|
|
|
|
when there isn't a closed formula yielding the variable you want, all you can do is create an iterative approach. Basically come up with an initial guess R1, calculate how wrong the outcome is, say F1 = NI1 - NItarget, then use a new guess R2, calculcate F2, etc. until it is sufficiently accurate. An appropriate iteration scheme is offered by the Newton-Raphson algorithm (Google it).
|
|
|
|
|
Solve for December to get rid of P? Or sum the year? Or do I grossly misunderstand?
Tadeusz Westawic
Sum quid sum.
|
|
|
|
|
Anyone know of an efficient algorithm for calculating contours / isolines from either regular or irregular elevation data? Preferably one that results in a definition of points per contour (i.e., a polyline representing a contour line).
Cheers!
|
|
|
|
|
I've got a simple and fast one for colouring in a contour line on a bitmap, but that may not suit your needs. Essentially it goes
for x = 0 to xmax
for y = 0 to ymax
if (CI(x,y) > CI(x-1,y) || CI(x,y) > CI(x+1,y) || CI(x,y) > CI(x,y-1) || CI(x,y) > CI(x,y+1))
set_line_colour(x,y);
where
int CI(int x, int y)
{
return (int)(altitude[x,y] / contour_interval);
}
If this is any good to you, it's yours. You'll need to clean up edge effects.
Cheers,
Peter
Software rusts. Simon Stephenson, ca 1994.
|
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
