Re: {Spam?} [PrimeNumbers] faster than the APR algorithm

Expand Messages
• Paul I d like to know who made you the spam-master! I believe that if I use the word prime, primality, or even list a few primes that it cannot be consider- ed
Message 1 of 33 , May 22, 2010
• 0 Attachment
Paul

I'd like to know who made you the spam-master!
I believe that if I use the word prime, primality, or
even list a few primes that it cannot be consider-
ed spam... lol

Here's how it works... and yes it's a QBasic alg.
I am computing two T-sequences... a T-3 and T-4
at the same time.

First, it computes the necessary term numbers
for each sequence, simultaneously, and then it
computes the value of each term.  For example...

N= 15; the terms are T15, T8, T7, T4, T3, T2, T1 & T0
for both sequences, the same, and then it computes...

the T-3 terms values...
T0= 2, T1= 3, T2= 3^2 -2 = 7 mod 15, T3= 3*7 -3 = 3 mod 15,
T4= T2^2 -2 = 2 = 15, T5= T2*T3 -3 = 3, etc.

the T-4 term values are computed the same, except...
T0= 2, T1= 4, etc.; I didn't invent it, but it's faster than
using the "extremely" bulky APR algorithm.

There's nothing wrong with a '70's program, it's simple
to read, and very, very easily translated into another
language... any language... I don't care who reads it;
my 50-line program is a ton easier to implement than
the several 100 lines of the APR algorithm and is far
less contrived and/or convoluted.  The bottom line is
that if T15 for both the T-3 and T-4 sequences equal 3 & 4,
respectively, then the number is prime; 231 is the only
composite that gives a mis-read; the two curves cross
there.

If you've ever looked at the APR algorithm, you'd know
that it is certainly twisted and absolutely ridiculous to
calculate; most mathematicians would insist that an
algorithm be elegant is some fashion as well as be the
fastest; the APR algorithm isn't elegant.  I spoke to
Carl Pomerance, once, and he wasn't very happy with
his own algorithm... "it doesn't tell me the factors"...
his words exactly!

Bill

----- Original Message ----
From: Paul Leyland <paul@...>
To: leavemsg1 <leavemsg1@...>
Sent: Fri, May 21, 2010 10:34:52 AM
Subject: Re: {Spam?} [PrimeNumbers] faster than the APR algorithm

On Fri, 2010-05-21 at 15:28 +0000, leavemsg1 wrote:

> I believe that this algorithm proves primality faster than the
> APR algorithm, not compositeness, but primality; if both this
> T-sequence algorithm and the APR algorithm were written in the
> same language and had the same FFT's and CPU available, then I
> believe the T-sequence would beat it; assuming that variables
> were computed on the fly... i.e. no stored values allowed.

Bunch of code omitted.

> Bill, hoping that someone would comment on it other than DjBrst

Wish granted.

Paul, hoping that you would comment on how it works instead of expecting
us to decipher some turgid code which looks as if it was written in the
early 1970s.  Some kind of BASIC if my age-addled memory doesn't
deceive me.
• ... You did very much what I did. I nearly fell off the chair when I averaged everything out and saw 0.57... :-) ... Not very. Would you buy an appeal to
Message 33 of 33 , May 27, 2010
• 0 Attachment
>
> I tried 1/n^c:
>
> v=[1237.1, 328.7, 105.4, 28.01, 6.22 , 1.510, 0.439, 0.0939];
> print(vector(8,k,-log(v[k]/10^6)/(k+4)/log(10)));
>
> [0.5815, 0.5805, 0.5682, 0.5691, 0.5785, 0.5821, 0.5780, 0.5856]
>
> and then A/n^c, using the first datum to remove A:
>
> print(vector(7,k,-log(v[k+1]/v[1])/k/log(10)));
>
> [0.5756, 0.5348, 0.5484, 0.5747, 0.5827, 0.5750, 0.5885]
>
> In both cases c =~ Euler looks rather convincing,
> given the statistics. Well spotted, Sir!

You did very much what I did.
I nearly fell off the chair when I averaged everything out and saw 0.57... :-)

> How strongly are you committed to A = 1, for the average,
> given the variability of the overall factor with a?

Not very.
Would you buy an appeal to Occam's razor, mon vieux?

Mike
Your message has been successfully submitted and would be delivered to recipients shortly.