| Topic: |
Science > Physics |
| User: |
"dedanoe" |
| Date: |
06 Apr 2006 03:50:35 AM |
| Object: |
dedanoe's rootless primality criterion |
Taken from http://dedanoe.tripod.com/primality/index.pdf
We want to check if N is prime or composite. Here is how we do it: We
write N
as A^2 - (B[1]^2 + B[2]^2 + B[3]^2 + ... + B[m]^2). It is so easy to do
with Delphi.
First we find A = Trunc(Sqrt(N)) + 1 then we implement this recursion:
function SquareExtractor(x, i: Integer): Integer;
if x > 1 then begin
B[i] := Trunc(Sqrt(x));
SquareExtractor(x - B[i]^2, i + 1);
Result := B[i]^2 + Result;
end else Result := 1;
end;
We call that function with SquareExtractor(A^2 - N; 1); In the end we
write N as product of sum and difference of two numbers (one real and
one whole) using:
x2 - y2 = (x - y)(x + y)
For instance if N = A^2 - B^2 then N is certainly composite. If N =
A^2-B^2-C^2 then N = (Sqrt(A^2 - B^2) - C)(Sqrt(A^2 - B^2) + C) so if
Sqrt(A^2 - B^2) is whole then N is composite or N = (Sqrt(A^2 - C^2) -
B)(Sqrt(A^2 - C^2) + B) so if Sqrt(A^2 - C^2) is whole then N is
composite or if neither then N is prime. Maybe my criterion is not so
fast after all but in any case it is faster than the well known ancient
Greek method.
That's all folks!!!
http://dedanoe.tripod.com
*****-SHIQUE SCIENCE
.
|
|
| User: "Dik T. Winter" |
|
| Title: Re: dedanoe's rootless primality criterion |
06 Apr 2006 09:08:03 AM |
|
|
In article <1144313435.464580.21150@i40g2000cwc.googlegroups.com> "dedanoe" <dedanoe@yahoo.com> writes:
For instance if N = A^2 - B^2 then N is certainly composite. If N =
A^2-B^2-C^2 then N = (Sqrt(A^2 - B^2) - C)(Sqrt(A^2 - B^2) + C) so if
Sqrt(A^2 - B^2) is whole then N is composite or N = (Sqrt(A^2 - C^2) -
B)(Sqrt(A^2 - C^2) + B) so if Sqrt(A^2 - C^2) is whole then N is
composite or if neither then N is prime.
Suppose N = 119. We find A = 11, B = 1 and C = 1. But neither
sqrt(A^2 - B^2), nor sqrt(A^2 - C^2) is integer. According to your
conclusion N is prime, but it is not.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
.
|
|
|
| User: "dedanoe" |
|
| Title: Re: dedanoe's rootless primality criterion |
06 Apr 2006 02:09:58 PM |
|
|
interesting remark!
.
|
|
|
|
| User: "dedanoe" |
|
| Title: Re: dedanoe's rootless primality criterion |
06 Apr 2006 03:23:11 PM |
|
|
the flow arrises because in N written as AA-BB-CC we have B=C=1. 1 is
the greatest trouble maker of all the integer numbers out there.
but there is a way of avoiding this trouble. instead of making
A=Trunc(Sqrt(N))+1 make A=Trunc(Sqrt(N))+2. This way N=119 can be
written as 144-25=(12-5)(12+5)=7*17.
You see once you write N as (x-y)(x+y) you look for
c=Biggest_Common_Divider(x, y) to pull it twice infront of the product
or write N=(x-y)(x+y) as N=c(x'-y')c(x'+y').
function BCD(x, y: Integer): Integer;
begin
if y > 0 then result:= BCD(y, x mod y) else result:= x;
end;
dedanoe's difence rests!
.
|
|
|
| User: "Dik T. Winter" |
|
| Title: Re: dedanoe's rootless primality criterion |
07 Apr 2006 06:51:39 AM |
|
|
In article <1144354991.306912.307260@v46g2000cwv.googlegroups.com> "dedanoe" <dedanoe@yahoo.com> writes:
(pray provide some context about what you are replying to)
the flow arrises because in N written as AA-BB-CC we have B=C=1. 1 is
the greatest trouble maker of all the integer numbers out there.
No. The problem is your assertion that if
N = A^2 - B^2 - C^2
and neither A^2 - B^2, nor A^2 - C^2 are squares that N is prime.
This is false. See for instance:
51 = 8^2 - 3^2 - 2^2.
but there is a way of avoiding this trouble. instead of making
A=Trunc(Sqrt(N))+1 make A=Trunc(Sqrt(N))+2. This way N=119 can be
written as 144-25=(12-5)(12+5)=7*17.
Yes, when you increment the 1 to 2 and next to 3 etc. whenever you do
not find a difference of two squares, you will factor the number indeed,
if it is not prime. But that is essentially Fermat's method to factor
numbers.
But also with A = sqrt(N) + 2 you will get problems:
115 = 12^2 - 5^2 - 2^2
neither 12^2 - 5^2, nor 12^2 - 2^2 are squares of integers.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
.
|
|
|
| User: "dedanoe" |
|
| Title: Re: dedanoe's rootless primality criterion |
07 Apr 2006 02:16:45 PM |
|
|
you are a hell of a valuable contributor, you know that?
the articulation of my criterion is an ongoing process so you'll need
to follow the changes. the assertion has just been altered.
when you write N as (x-y)(x+y) you look for the biggest comon divider
for x and y to pull it twice in front of the product.
for instance:
115=12^2-5^2-2^2
1) 115=(Sqrt(119)-2)(Sqrt(119)+2) accordingly N is potential prime.
2)
115=(Sqrt(140)-5)(Sqrt(140)+5)=Sqrt(5)(Sqrt(28)-Sqrt(5))Sqrt(5)(Sqrt(28)+Sqrt(5))=5*(28-5)=5*23
accordingly N is composite end.
http://dedanoe.tripod.com
.
|
|
|
| User: "Dik T. Winter" |
|
| Title: Re: dedanoe's rootless primality criterion |
09 Apr 2006 09:04:44 PM |
|
|
In article <1144437405.116049.211550@t31g2000cwb.googlegroups.com> "dedanoe" <dedanoe@yahoo.com> writes:
you are a hell of a valuable contributor, you know that?
Who? O, me. As I stated before, include information about the parent
article when you post a reply. Not everybody is reading news with google.
when you write N as (x-y)(x+y) you look for the biggest comon divider
for x and y to pull it twice in front of the product.
for instance:
115=12^2-5^2-2^2
1) 115=(Sqrt(119)-2)(Sqrt(119)+2) accordingly N is potential prime.
2)
115=(Sqrt(140)-5)(Sqrt(140)+5)=Sqrt(5)(Sqrt(28)-Sqrt(5))Sqrt(5)(Sqrt(28)+Sqrt(5))=5*(28-5)=5*23
accordingly N is composite end.
Yes, so you can find composites, but you do not show that numbers are prime.
Consider: 889 = 31^2 - 6^2 - 6^2.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
.
|
|
|
| User: "dedanoe" |
|
| Title: Re: dedanoe's rootless primality criterion |
12 Apr 2006 05:35:39 AM |
|
|
Yes I don't show the numbers are prime but as long as they are not
composite I say they are potentially prime.
889=30^2-3^2-1-1 potentially prime
889=31^2-8^2-2^2-2^2 potentially prime
889=32^2-11^2-3^2-2^2-1 potentially prime
889=33^2-14^2-2^2=7(155-28)=7*127 definitly composite.
Biggest_Common_Divider(33^2-2^2, 14^2)=7
I say potentially prime because I don't know what is the top M in
A=Trunc(Sqrt(N))+M that concludes my criterion.
http://dedanoe.tripod.com
.
|
|
|
| User: "Dik T. Winter" |
|
| Title: Re: dedanoe's rootless primality criterion |
12 Apr 2006 05:52:22 AM |
|
|
In article <1144838139.062706.271960@t31g2000cwb.googlegroups.com> "dedanoe" <dedanoe@yahoo.com> writes:
Yes I don't show the numbers are prime but as long as they are not
composite I say they are potentially prime.
889=30^2-3^2-1-1 potentially prime
889=31^2-8^2-2^2-2^2 potentially prime
889=32^2-11^2-3^2-2^2-1 potentially prime
889=33^2-14^2-2^2=7(155-28)=7*127 definitly composite.
Biggest_Common_Divider(33^2-2^2, 14^2)=7
I say potentially prime because I don't know what is the top M in
A=Trunc(Sqrt(N))+M that concludes my criterion.
There is one, but it is so large that it makes no sense to use it.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
.
|
|
|
|
| User: "dedanoe" |
|
| Title: Re: dedanoe's rootless primality criterion |
13 Apr 2006 09:40:54 AM |
|
|
also because we don't have an exact formulation for primes i cannot say
this number is definitly prime. for composites i can cause we know that
if N=xy where N,x,y<>1 are whole then N is composite.
http://dedanoe.tripod.com
.
|
|
|
|
| User: "Pubkeybreaker" |
|
| Title: Re: dedanoe's rootless primality criterion |
13 Apr 2006 10:31:11 AM |
|
|
dedanoe wrote:
Yes I don't show the numbers are prime but as long as they are not
composite I say they are potentially prime.
"potentially prime" is useless.
Any number, for which YOU don't know a factor is 'potentially prime".
The concept is vacuous.
Your methods do not work.
.
|
|
|
| User: "dedanoe" |
|
| Title: Re: dedanoe's rootless primality criterion |
13 Apr 2006 03:16:12 PM |
|
|
pull my finger!
.
|
|
|
|
|
|
|
|
|
|
|
| User: "dedanoe" |
|
| Title: Re: dedanoe's rootless primality criterion |
06 Apr 2006 04:04:34 AM |
|
|
the identity was x^2 - y^2 = (x - y)(x + y)
.
|
|
|
| User: "dedanoe" |
|
| Title: Re: dedanoe's rootless primality criterion |
06 Apr 2006 08:29:13 AM |
|
|
actually the criterion is Sqrt(x)/Sqrt(y) to be whole number if N tends
to be composite.
.
|
|
|
|
|
|
Related Articles |
|
|
