mersenneforum.org  

Go Back   mersenneforum.org > Other Stuff > Archived Projects > 15k Search

 
 
Thread Tools
Old 2004-03-06, 01:27   #1
jocelynl
 
Sep 2002

4068 Posts
Default 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
jocelynl is offline  
Old 2004-03-06, 15:08   #2
Thomas11
 
Thomas11's Avatar
 
Feb 2003

22×32×53 Posts
Default

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

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
Thomas11 is offline  
Old 2004-03-06, 16:34   #3
jocelynl
 
Sep 2002

2·131 Posts
Default

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
jocelynl is offline  
Old 2004-03-06, 20:03   #4
masser
 
masser's Avatar
 
Jul 2003
wear a mask

2×52×31 Posts
Default

Hi Thomas,

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

Regards,
masser

Quote:
Originally Posted by 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
masser is online now  
Old 2004-03-07, 13:01   #5
Thomas11
 
Thomas11's Avatar
 
Feb 2003

22·32·53 Posts
Default

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)
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
----------------------
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
Thomas11 is offline  
Old 2004-03-08, 04:21   #6
Citrix
 
Citrix's Avatar
 
Jun 2003

1,579 Posts
Default

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
Citrix is offline  
Old 2004-03-08, 10:48   #7
Thomas11
 
Thomas11's Avatar
 
Feb 2003

22×32×53 Posts
Default

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
Thomas11 is offline  
Old 2004-03-08, 14:20   #8
Citrix
 
Citrix's Avatar
 
Jun 2003

157910 Posts
Default

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

Citrix
Citrix is offline  
Old 2004-03-08, 20:33   #9
jocelynl
 
Sep 2002

2·131 Posts
Default

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
jocelynl is offline  
Old 2004-03-09, 07:25   #10
thommy
 

2×3,319 Posts
Default

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
 
Old 2004-03-09, 10:13   #11
Thomas11
 
Thomas11's Avatar
 
Feb 2003

22×32×53 Posts
Default

Quote:
Originally Posted by 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
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
Thomas11 is offline  
 

Thread Tools


All times are UTC. The time now is 01:18.

Fri Feb 26 01:18:29 UTC 2021 up 84 days, 21:29, 0 users, load averages: 1.55, 1.71, 1.71

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.