Browse Groups

• Hi Here I send you that I have obtained a MATHEMATICA algorithm to obtain the prime numbers based on ideas Ragheb and Thamer Masarweh. Two questions: Is that
Message 1 of 4 , Sep 11, 2011
View Source
Hi

Here I send you that I have obtained a MATHEMATICA algorithm to obtain the prime numbers based on ideas
Ragheb and Thamer Masarweh.

Two questions:

Is that correct?

Is polynomial?

Do[a=0;b=0;Ln=Log[n]^Log[Log[n]^2];c=1;
While[a<Ln,c=1;
While[b<Ln,nab=Abs[n/(2 a b +3(a+b+1))-1];
If[nab==0,c=n;b=Ln+1;a=Ln+1,b=b+1]];a=a+1;b=a];
If[c<n,Print[2n+3," ",PrimeQ[2n+3]]],{n,2,1500}]

Sincerely

Sebastian Martin Ruiz

[Non-text portions of this message have been removed]
• What do you mean by polynomial ? The most naive algorithm, for n from 2 to N_max for k from 2 to sqrt(n) if n mod k = 0 then next n end for k print n /*
Message 1 of 4 , Sep 11, 2011
View Source
What do you mean by "polynomial" ?
The most naive algorithm,

for n from 2 to N_max
for k from 2 to sqrt(n)
if n mod k = 0 then next n
end for k
print "n" /* it's prime */
end for n

also is polynomial, less than O(N_max)^2.

Maximilian

--- In primenumbers@yahoogroups.com, Sebastian Martin Ruiz <s_m_ruiz@...> wrote:
>
>
>
> Hi
>
>
> Here I send you that I have obtained a MATHEMATICA algorithm to obtain the prime numbers based on ideas
> Ragheb and Thamer Masarweh.
>
> Two questions:
>
> Is that correct?
>
> Is polynomial?
>
> Do[a=0;b=0;Ln=Log[n]^Log[Log[n]^2];c=1;
> ï¿½ While[a<Ln,c=1;
> ï¿½ï¿½ï¿½ While[b<Ln,nab=Abs[n/(2 a b +3(a+b+1))-1];
> ï¿½ï¿½ï¿½ï¿½ï¿½ If[nab==0,c=n;b=Ln+1;a=Ln+1,b=b+1]];a=a+1;b=a];
> ï¿½ If[c<n,Print[2n+3," ",PrimeQ[2n+3]]],{n,2,1500}]
>
> Sincerely
>
> Sebastian Martin Ruiz
>
> [Non-text portions of this message have been removed]
>
• Your algorithm can be more simply & efficiently be written as: for( n=2,1500, Ln=log(n)^log(log(n)^2) ; for(a=0,Ln, ; ; for(b=a,Ln, ; ; ; if( n==2 *a *b
Message 1 of 4 , Sep 11, 2011
View Source
Your algorithm can be more simply & efficiently be written as:

for( n=2,1500, Ln=log(n)^log(log(n)^2)
; for(a=0,Ln,
; ; for(b=a,Ln,
; ; ; if( n==2 *a *b +3*(a+b+1), next(3))
; ; )
; )
; print(2*n+3)
)}

Clearly 2*n+3 is never even, so if it is composite, it can be written as

2n+3 = (2a+3)*(2b+3) (a>=0, b>=0)

<=> 2n = 4ab + 6a + 6b + 6

<=> n = 2ab + 3a + 3b + 3

Your algorithm checks whether n can be written in that form,
for all possible a,b < Ln.
This is of course very inefficient
(since the value of b is irrelevant for given a),
it would be enough to check if 2n+3 is divisible by 2a+3.
This would correspond to the (much more efficient) algorithm:

for( n=2,1500, Ln=log(n)^log(log(n)^2)
; for(a=0, min(Ln,n-1), /* because Ln may be >> n !! */
; ; if( (2*n+3)%(2*a+3)==0, next(2))
; )
; print(2*n+3)
)

Moreover, it is sufficient to restrict yourself to
2a+3 < sqrt(2n+3), i.e. a ~ sqrt(n/2)

The bound you use is much too high for values of n < 10^30
but it is not high enough beyond n ~ 10^35
(you have Ln = sqrt(n) at n ~ 1.6 x 10^32, and then it is smaller).

From there on you would be sure to find "wrong primes",
if your program was not too inefficient as to do a check for n of this size.

Maximilian
Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.