- View SourceHi

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] - View SourceWhat 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]

> - View SourceYour 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