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

Cc: primenumbers@yahoogroups.com

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. - --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
>

You did very much what I did.

> 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!

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,

Not very.

> given the variability of the overall factor with a?

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

Mike