The other 39261 candidates

[Greenbank]

I've been implementing my own sievers, proth_tests and composite tests to help me understand this problem in more detail.

I've been using the GMP library on non x86 hardware (otherwise I'd be using those machines for SoB!).

There are 39278 odd k values between 1 and 78555 (inclusive) and in the last 7 days I've managed to find n's for all but 60 of these candidate k values (excluding the 17 being tested by SoB) that pass a proth-test and prove primality.

My goal is to produce a list of all odd k values < 78557 (excluding the SoB 17) along with the corresponding n value that produces the prime (with the appropriate a value for the proth test).

I've tested up to n=25000 (it's currently testing the 25000 to 26000 range where it has found k=7651,n=25368 and k=38569,n=25562 as prime). Still another 230 tests to go for this range.

Anyone know how high (n) you have to check to get rid of all k-values apart from the original 17? Not looking for actual numbers (don't want to spoil my work) but just a general idea.

I'm doing the following:-

1. A naive sieve to remove all k,n pairs which have a factor between 3 and 10M. This reduces the 1000 n-values down to roughly 11 per k-value.

2. Followed by prime testing with gmp's mpz_probab_prime_p() function.

The mpz_probab_prime_p() function returns one of 3 values. Definitely composite = remove k,n pair from list. Definitely prime (it never returns this). Probably prime. This is better than some of the other prime testing functions as there is no possibility (however slim) of a prime being returned as 'Definitely composite'.

If I get a Probably Prime then I perform a proth-test on it (with a=3). So far the proth_test with a=3 has never failed to prove primality for a number that mpz_probab_prime_p() says is probably prime. If it does fail I will retest with other values of a (5,7,11, etc) but I doubt this will ever happen.

The proth test code is very naive again. It's simply compute N=k*2^n+1, then a^((N-1)/2) mod N using the mpz_powm() function.

I have a much faster siever (based on iterating 2r-1 on the remainder rather than trial division) but I haven't tested it enough to be 100% confident in it.

Once I do some final testing on my new siever I'll be able to sieve to a higher n in the same time period and therefore remove more candidate k,n pairs.

I'm also approaching the point where mpz_probab_prime_p() takes almost as long as doing the proth test directly. Not sure what I'll do when it becomes too much of a burden.

[Greenbank]

Ah. Found some of the info on this page (which I'd seen before but failed to bookmark).

http://www.prothsearch.net/sierp.html

[olaright]

Greenbank,

Making such a list is a great idea and I hope you can finish the job! If the primes you find are the lowest, i figure the list would enable for accurate prediction of the location of the sob primes.

When finished, can you make your list available? Maybe sob can host it.


regards,

Ola

[Greenbank]

They may not be the lowest n as there are multiple a values that can be used by the Proth test. Sometimes using the lowest prime non-factor of k is not the 'best'.

Here's a good example:-

k=13635 = 3*3*3*5*101

FACTOR: k=13635 a=3
FACTOR: k=13635 a=5

There's no point performing a proth-test with a being a factor of k. It will never be sucessful (i.e. it will never return the right result that proves primality).

Now look at the n values for sucessive primes:-

PRIME: k=13635 n=310 a=7
PRIME: k=13635 n=65 a=11
PRIME: k=13635 n=62 a=13
PRIME: k=13635 n=62 a=17
PRIME: k=13635 n=62 a=19
PRIME: k=13635 n=65 a=23
PRIME: k=13635 n=62 a=29

Now do we list k=13635 as n=310 (a=7) or n=65 (a=11) or even n=62 (a=13)?

Trying to find the lowest n will involve a whole lot more computation as you have to perform the proth test with many different a-values.

[EDIT] I wasn't thinking properly when I wrote this. I had performed my calculations based on the time it takes for a probable-prime test at n~20k instead of n~8k. I've rechecked all k for n < 8000 and found the lowest n values possible (with larger a's). All probable-primes for n>=8000 have been proth-tested with multiple a-values until I found one that proved primality, so I know I have the lowest n for them.

When I've finished I'll put it up on a website. (I'll need to spend a bit of time attributing the k,n pairs that I haven't found myself to the appropriate people).

If anyone wants to steal a copy of the page then they are free to, although they must keep the attributions for the other k values (I don't care about the ones I found, it's just the other people concerned).

[Greenbank]

Hmm...I'm having trouble getting values for all of them as I had a fit of stupidity and deleted the data file (although I've got almost everything on paper and other log files).

This page: http://www.prothsearch.net/sierp.html claims that all but 69 k's are prime with n <= 8000.

48 are given in the table, 17 are the SoB 17, and 4 (much larger n) are provided at the bottom.

Strangely though not all of the ones *NOT* listed have primes with n <= 8000.

k=6529 for example is only prime at n=18618.

Hmm. May take a couple of days to get all of the values.

[Greenbank]

OK. 29 left. Seems that page defintely lied about all but 60 with n <= 8000. Hmm.

12743, 22249, 23873, 23971, 27589, 28831, 32807, 35461, 39527, 41573,
44243, 45323, 46457, 47269, 50777, 50839, 50873, 54953, 56387, 57377,
63691, 66683, 68221, 68633, 71657, 75991, 76277, 76877, 77297.

Thursday 30-JUN-2005 4pm: 88 k,n pairs with n < 26000 left to test.
Friday 01-JUL-2005 11am. k=32807,n=26827,a=3. 28 to go.
Friday 01-JUL-2005 11am. 180 k,n pairs with n < 29000 left to test.

[Greenbank]

05-JUL-2005 25 left
k=47269,n=32182,a=3
k=76277,n=32539,a=3
k=27589,n=35562,a=3

Lower bound of n now 37001.

Just finishing off the sieving up to about 13G and then I'll be prp'ing the remaining k,n pairs. Should be about 5000 k,n pairs with 37000 < n < 60000 left after the sieving.

Hopefully all 25 should be found pretty soon as this is starting to get annoying ;-)

[Greenbank]

Doh. How stupid can I be.

(12743*2^9)+1 = 6524417 which is prime.

I wasn't checking n where 2^n <= k as the proth test isn't valid for these n's.

Now going through and checking for n where 2^n <= k. Surprisingly I'm finding lots of lower n values for lots of k's.

Should have the page of all k's and n's (except the 9 with no factor) by the end of the day.

I guess the page quoted above doesn't lie. Mea cupla.

[olaright]

> Should have the page of all k's and n's (except the 9 with no factor) by the end of the day


Hi Greenbank,

Any update on this? I would be very interested if you could make this list available.

Regards,

Ola

[Greenbank]

Ah yes, thank you for reminding me. Will this do:-

http://www.greenbank.org/sob/other.html

Note that it's quite large (1.4Mb)...

Comments/mistakes/corrections please let me know.