mersenneforum.org (https://www.mersenneforum.org/index.php)
-   15k Search (https://www.mersenneforum.org/forumdisplay.php?f=16)
-   -   Non 15k to 1M anyone? (https://www.mersenneforum.org/showthread.php?t=2180)

 jocelynl 2004-03-06 01:27

Non 15k to 1M anyone?

As you all know 15k's usually have more primes in the lower n's. More primes also mean more n's to test. I have been working for past couple weeks to find k's that are easier to sieve. They have very few primes but also have very few n's to test thus faster the way to 1M. The best one that came up so far is 79*487 (38473) it has only 2049 n's left to be tested from 300k to 1M. The funny thing is, I haven't found one yet! Would any be interested in joining a team to take a non 15k to 1M? It could be after the current 15k team!

Joss L15

 Thomas11 2004-03-06 15:08

I'm currently testing a few non-15k's of extremely low Nash weight up to 1M. You may have noticed the prime 243163663*2^919087-1 I have found recently. For the k's I'm testing usually only about 400-500 n's survive the sieve and need to be tested by LLR. So this could be done on a typical machine in about one month or so. But the chances of finding a prime is at least very low. Nevertheless, if you find one it will be a big one :smile:

Until now I've computed Nash weights for all k<350.000.000 and there are a lot of interesting candidates, e.g. almost about 50.000 candidates have a Nash weight less than 100. For my tests I've picked only those with weights lower than 20. If you're interested in a list of possible candidates, e.g. the "less than 100 list", just leave a note here in the forum.

Thomas L8 L19 L10

 jocelynl 2004-03-06 16:34

Hi Thomas,

Are you taking 1423*170881 (243163663) to 10M? This would definitely be a good candidate for team work. Feel free to post any of your work so I can add it to the stats. What program do you use to find nash weight?

Joss

 masser 2004-03-06 20:03

Hi Thomas,

I would like to see that list; could a link to it be added to the 15k webpage?

Regards,
masser

[QUOTE=Thomas11]Until now I've computed Nash weights for all k<350.000.000 and there are a lot of interesting candidates, e.g. almost about 50.000 candidates have a Nash weight less than 100. For my tests I've picked only those with weights lower than 20. If you're interested in a list of possible candidates, e.g. the "less than 100 list", just leave a note here in the forum.

Thomas L8 L19 L10[/QUOTE]

 Thomas11 2004-03-07 13:01

Hi Joss and Masser,

thank's for your interest. First of all I should note that I'm currently out of town for about one week. Therefore I haven't full access to all the data I'd like to provide to you.

For the Nash weight computation I used a small C program written by myself after a "close" look into John Brennen's Java applet. I developed my program in a UNIX environment using the GMP library. I compiled and used it under Linux too, but I don't know if GMP is available for Windows and how to get it compiled there. Nevertheless, if some of you are interested, I could send you the source code and/or Linux binary.

Please don't ask for a "complete" list of Nash weights for all (odd) k's up to 350 million. Since my program stores the results into ascii files this would be 3.5 GByte of data (10.5 MByte per 1 million range of k's = 500.000 odd k's)! But any small portion of data can be easily extracted for the list, e.g. the "less than 100" list or a "larger than 6000" list or a "zero weight" list (= Riesel numbers). The "less than 100" list would be about 900 kByte (or 300 kByte ZIPed).

Originally I had planned to take one or a few k's up to 10M and I did a lot of sieving work in that direction. But after all it is too much work for one single person having only a few machines. So any of you may take part in the search for some big primes ...

The following 23 k values have been sieved for n=2..10.000.000 up to p=8.000.000.000.000 (yes, 8 trillion!) and already LLR-tested up to n=1.000.000:

[CODE]
k w w' prime for n=
-----------------------------------------
19370947 17 15 25
59910449 15 15 92
80857169 19 17 4
143316643 15 16
162405629 20 21 896, 12236
175437131 20 21
189030223 18 19
203012861 16 17 754
209826493 16 18
224371169 17 17 3548
243163663 15 18 919087
245265883 16 17
260213857 13 16
265831619 19 16
276278983 16 18 21623, 473423
290851087 23 21 57
298095191 14 15
300871183 22 23
308120317 19 19
308141737 19 19 7517
315940139 18 17 8388, 595620
326840893 17 15 31
----------------------------------------
(w is the "original" Nash weight for n=100.001-110.000,
while w' is the Nash weight obtained for n=1-10.000)
[/CODE]

I have no idea, which k should be choosen for testing n>1 million. Maybe one or a few for which no prime exists for n<1 million.

As I already mentioned, I don't have access to the presieved ranges at the moment, but I can send them to Joss around March 15th, so he could store the data on 15k.org.

It should be mentioned that a single LLR test on a n=1 million number takes about 4 hours on a 2.4 GHz P4. And around n=1.5 million the time raises to 8 hours and more.

In case you can't wait until I've sent you the presieved data and/or you want to test some untested k-values for lower n, here is a short list of low weight k's which I haven't tested so far (but someone else may have tested them):

[CODE]
k w w'
----------------------
10013593 40 46
10247561 38 38
10284899 27 30
10346561 46 48
10453199 28 26
10463923 34 28
10598947 45 45
10639619 37 38
10671431 34 36
10805593 49 45
10813783 34 40
10906603 38 38
10932097 44 41
10943321 50 61
11223059 26 27
11311003 31 28
11319193 45 43
11468609 46 47
11639819 39 38
11658187 48 44
11716993 48 41
11741347 42 44
11846279 50 48
11847299 45 45
11932211 38 37
11955659 36 36
12254533 36 36
12305981 44 44
12334093 49 53
12551291 43 41
12695159 31 36
12753311 48 42
12825793 49 53
13277471 48 50
13651423 48 49
13768087 46 49
13900807 23 18
14085941 35 36
14321533 29 23
14466883 40 41
14533213 42 44
14549347 48 52
14745343 31 32
14961487 25 23
----------------------
[/CODE]

I suggest to sieve them for n=2..250.000 up to about p=10 or 15 billion. Only 150-400 candidates will remain per k and can be LLR tested in a few hours. Candidates for n<256 should be tested by Pari (or Mathematica, Maple, etc.) rather than using LLR, since it may crash or report a prime as "non-prime".
There should be quite a few primes in the above list for n<250.000 but only
one or two Top5000 primes.

Best wishes and a few primes ...

Thomas

 Citrix 2004-03-08 04:21

Thomas,
Do you know which is the second smallest riesel number?
Could you also provide me with a list for k's with weight's under 40. We should extend you list upto 2^31 than just 350M.

Thanks,
Citrix
:cool: :cool: :cool:

 Thomas11 2004-03-08 10:48

Hi Citrix,

there are 5 Riesel numbers below k=1 million:
509203, 762701, 777149, 790841, and 992077.

I'll send you a complete list of zero weighted k's as well as the "less than 40" list by private mail. Interesting to note, that there are much more k's of zero weight than k's with weights between 0 and 40 ...

Currently I'm extending the weights list to k=500M, any co-workers are welcome, but the problem is how to store and exchange the large data blocks generated by the program (e.g. 10.5 MByte for a 1M k-range).
Well, one could cancel the w' computation and store k and w in binary form (4 + 2 Byte), but this is still 3 MByte instead of 10.5 MByte.

Thomas

 Citrix 2004-03-08 14:20

Thomas,
The algorithm used in psieve is inefficient. You can use recursion and reduce the number of run hours to less than 25.

Citrix
:cool: :cool: :cool:

 jocelynl 2004-03-08 20:33

I'm working on the zero's up to k=2^31 the list is at the end of the stats. I'm at k=13M and testing them with newpgen one by one up to n=1M.

Joss

 thommy 2004-03-09 07:25

Thomas,
are you 100% sure that a zero weight k is indeed a riesel prime? maybe the n-range for calculating the weight is just to low. I don't think so, but safty first.

Thommy

 Thomas11 2004-03-09 10:13

[QUOTE=thommy]Thomas,
are you 100% sure that a zero weight k is indeed a riesel prime? maybe the n-range for calculating the weight is just to low. I don't think so, but safty first.

Thommy[/QUOTE]

Thommy,

please do not mix up "Riesel primes" and "Riesel numbers"! A Riesel number is a k, for which k*2^n-1 is never prime.

You may verify the zero weight k's easily by hand and a pocket calculator.
Let's take k=762701, for example:

3 | 762701*2^1-1
7 | 762701*2^2-1
3 | 762701*2^3-1
5 | 762701*2^4-1
3 | 762701*2^5-1
11 | 762701*2^6-1
3 | 762701*2^7-1
5 | 762701*2^8-1
3 | 762701*2^9-1
13 | 762701*2^10-1
3 | 762701*2^11-1
5 | 762701*2^12-1
3 | 762701*2^13-1
7 | 762701*2^14-1
3 | 762701*2^15-1
5 | 762701*2^16-1
3 | 762701*2^17-1
17 | 762701*2^18-1
3 | 762701*2^19-1
5 | 762701*2^20-1
3 | 762701*2^21-1
13 | 762701*2^22-1
...

The pattern repeats itself and shows that:
3 divides every second number,
5 divides every fourth number,
7 divides every sixth number,
11 divides every tenth number,
13 divides every twelth number, and
17 divides every sixteenth number.

Or in other words:
After sieving to p=3, only half the numbers remain (the even ones in the above case). Sieving to p=5 eliminates every second of the remaining numbers. p=7 should eliminate every sixth number, but half of them are already eliminated by p=5. And so forth ...

It is special for Riesel numbers that the small primes up to 13, 17 (or some other small prime) cancel out ANY n. And therefore no primes can exist for that k.

The above test may be done by NewPGen too - it should find for any given range of n, that after p=13, 17 (or,in some rare case, a higher "small" prime)
no n remains.

Thomas

All times are UTC. The time now is 20:05.