Browse Groups

• 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.