mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Riesel Prime Search

Reply
 
Thread Tools
Old 2013-08-01, 08:21   #1
Thomas11
 
Thomas11's Avatar
 
Feb 2003

24·7·17 Posts
Default Generating low weight multipliers

Quote:
Originally Posted by Citrix View Post
Thomas11 could you post the other extremely low wt numbers you generated. Thanks!
Citrix, right now I'm on the leave for a one week vacation.
I will post them once I'm back.

In the meantime you may have a look here.

Last fiddled with by Thomas11 on 2013-08-01 at 08:24
Thomas11 is offline   Reply With Quote
Old 2013-08-02, 07:31   #2
Citrix
 
Citrix's Avatar
 
Jun 2003

1,553 Posts
Default

Quote:
Originally Posted by Thomas11 View Post
Citrix, right now I'm on the leave for a one week vacation.
I will post them once I'm back.

In the meantime you may have a look here.
Thanks Thomas11.

I tried to write some code to generate these numbers on my own.
I extended the k's beyond 64 bits.

Using covering sets I have generated some of the lowest weight k's ever know (ultra-extreme-tiny low weight).
After sieving less than 1 candidate in 1 million remains. (close to 1.5 in 2 Million)

Here is one example. (I can share more if any one needs them)
k=6642510166838280632766408995039562371
Covering set=61130828015333178565632041818522446870
n=103680

You can generate more k's by
k=k+covering set *y

I am currently working on y 1-10000.
I am using PFGW to sieve and factor

After sieving for the covering set only n=35346 (mod 103680) remain.

Feel free to reserve a range after the first 10000 if you like.
I have millions more of such k's if any one is interested.

It would be interesting if a prime can be found for such a low weight k.

Last fiddled with by Citrix on 2013-08-02 at 07:32
Citrix is offline   Reply With Quote
Old 2013-08-12, 14:24   #3
Thomas11
 
Thomas11's Avatar
 
Feb 2003

77016 Posts
Default

Hi Citrix,

I'm glad to see that you generated a new bunch of ultra low weight Ks.

Quote:
Originally Posted by Citrix View Post
Here is one example. (I can share more if any one needs them)
k=6642510166838280632766408995039562371
Covering set=61130828015333178565632041818522446870
n=103680

You can generate more k's by
k=k+covering set *y
Given the large covering set (3, 5, 7, 11, 13, 17, 19, 31, 37, 41, 61, 97, 163, 193, 271, 541, 641, 769, 1297, 7681), which leaves only 1/103680th of the candidates, it is actually not surprising that you're left with only one candidate per million after sieving.

Note that there are many more cycles sharing the same covering set. Thus, your starting k (k0) is only one out of many.
Here are a few more:
13349413408324173624146033148581
53562291021239919328906722016303
156820614115299139492807442264081
Thomas11 is offline   Reply With Quote
Old 2013-08-12, 15:12   #4
Thomas11
 
Thomas11's Avatar
 
Feb 2003

24·7·17 Posts
Default

Quote:
Originally Posted by Citrix View Post
Here is one example. (I can share more if any one needs them)
k=6642510166838280632766408995039562371
Covering set=61130828015333178565632041818522446870
n=103680

You can generate more k's by
k=k+covering set *y
Note that your formula (k = k + covering set * y) yields only 1/103680th of the k's of the cycle (one per cycle of length "covering set", but each cycle by itself consists of "n" k's). There is another recursion to get the other ones:

k = (2*k + (covering set)/2) (mod covering set)

This also means that your k is actually not the smallest k of the cycle.
In your case k0=27877812802424205899986999806089.

Last fiddled with by Thomas11 on 2013-08-12 at 15:22
Thomas11 is offline   Reply With Quote
Old 2013-08-12, 20:00   #5
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT)

163116 Posts
Default

Do you have a method of sieving these?
The only siever I have found that does such large ks is http://fatphil.org/maths/ksieve/
It only works if the k is made up of factors <10^15 though which rules most of these out.
henryzz is offline   Reply With Quote
Old 2013-08-12, 20:25   #6
Thomas11
 
Thomas11's Avatar
 
Feb 2003

24×7×17 Posts
Default

Quote:
Originally Posted by henryzz View Post
Do you have a method of sieving these?
No, I don't have a sieve for them.
That's one of the reasons why I never extended the search beyond k=2^64...
Thomas11 is offline   Reply With Quote
Old 2013-08-12, 22:03   #7
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT)

13×19×23 Posts
Default

I suppose once you take into account the covering set there aren't many ns anyway.
henryzz is offline   Reply With Quote
Old 2013-08-13, 20:22   #8
Citrix
 
Citrix's Avatar
 
Jun 2003

1,553 Posts
Default

Quote:
Originally Posted by Thomas11 View Post
Note that your formula (k = k + covering set * y) yields only 1/103680th of the k's of the cycle (one per cycle of length "covering set", but each cycle by itself consists of "n" k's). There is another recursion to get the other ones:

k = (2*k + (covering set)/2) (mod covering set)

This also means that your k is actually not the smallest k of the cycle.
In your case k0=27877812802424205899986999806089.
I know. This was just the first example. I stopped after I generated the first few. There are other ways of generating these numbers... you can generate a few TB of these numbers.

I don't think the size of the k will make any difference as all the k's generated will be low weight. Also k=64 bit would not be faster than these larger k's.

Since these numbers take too long to LLR- I turned the problem around... and took k numbers less than 2^18. Then I split the k into base 2^5760 sequences.

k1=k*2^1
k2=k*2^2
... and so on.

I tested their weight using the above covering set (for 2^5760-1) & sieving to 1200

Only a few k remained with less than 20 candidates up to 1 million (corresponding to nash weight of 1/4). I have tested some of these to 2 Million with no prime.

There are more left if any one is interested. These can be sieved using srsieve. Any thoughts of a group project?

Last fiddled with by Citrix on 2013-08-13 at 20:38
Citrix is offline   Reply With Quote
Old 2013-08-14, 17:22   #9
Thomas11
 
Thomas11's Avatar
 
Feb 2003

77016 Posts
Default

Quote:
Originally Posted by Citrix View Post
Since these numbers take too long to LLR- I turned the problem around... and took k numbers less than 2^18. Then I split the k into base 2^5760 sequences.

k1=k*2^1
k2=k*2^2
... and so on.

I tested their weight using the above covering set (for 2^5760-1) & sieving to 1200

Only a few k remained with less than 20 candidates up to 1 million (corresponding to nash weight of 1/4). I have tested some of these to 2 Million with no prime.
I agree with you that while looking for small weights one should try to keep the k as small as possible to benefit from faster LLR testing.

However, I must admit that I don't understand the explanation of your approach.

You say you're taking k<2^18, which is just k<262144 - pretty small. But there are no really low weight Ks in the interval, only a few have Nash weights < 100, the lowest weight being 29 for k=138847 - about 100 times larger than the 1/4 you mentioned.

Then you write:
k1=k*2^1
k2=k*2^2
...
which leaves k essentially unchanged. It's just a cycling through the n. k1, k2, ... all have the same weight (in practise: more or less, since the n range is shifted to higher n due to the multiplier 2^i).

Then you mention the covering set for 2^5760-1.
Given the divisors of 5760 (= 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 30, 32, 36, 40, 45, 48, 60, 64, 72, 80, 90, 96, 120, 128, 144, 160, 180, 192, 240, 288, 320, 360, 384, 480, 576, 640, 720, 960, 1152, 1440, 1920, 2880, 5760), this means a huge covering set, leading to k much larger than 64 bits or even 128 or 256 bits.
Or did you mean a covering set of length 5760 (=2^7 * 3^2 * 5)? This, on the other hand, would be too small.

Most likely I missed some essential part of your idea.

Perhaps, if you would post a few of the Ks generated by your procedure, I could find out what I'm missing...
Thomas11 is offline   Reply With Quote
Old 2013-08-14, 22:12   #10
Citrix
 
Citrix's Avatar
 
Jun 2003

1,553 Posts
Default

Quote:
Originally Posted by Thomas11 View Post
I agree with you that while looking for small weights one should try to keep the k as small as possible to benefit from faster LLR testing.

However, I must admit that I don't understand the explanation of your approach.

You say you're taking k<2^18, which is just k<262144 - pretty small. But there are no really low weight Ks in the interval, only a few have Nash weights < 100, the lowest weight being 29 for k=138847 - about 100 times larger than the 1/4 you mentioned.

Then you write:
k1=k*2^1
k2=k*2^2
...
which leaves k essentially unchanged. It's just a cycling through the n. k1, k2, ... all have the same weight (in practise: more or less, since the n range is shifted to higher n due to the multiplier 2^i).

Then you mention the covering set for 2^5760-1.
Given the divisors of 5760 (= 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 30, 32, 36, 40, 45, 48, 60, 64, 72, 80, 90, 96, 120, 128, 144, 160, 180, 192, 240, 288, 320, 360, 384, 480, 576, 640, 720, 960, 1152, 1440, 1920, 2880, 5760), this means a huge covering set, leading to k much larger than 64 bits or even 128 or 256 bits.
Or did you mean a covering set of length 5760 (=2^7 * 3^2 * 5)? This, on the other hand, would be too small.

Most likely I missed some essential part of your idea.

Perhaps, if you would post a few of the Ks generated by your procedure, I could find out what I'm missing...
1) Take k <262144 (This is the cut off LLR starts taking more time on my computer)

2) The more k's you test, the more likely you are to find a small weight k

3) using the covering set of just 3 there are 2 kinds of k--> 1/2 the candidates are divisible by 3 or no candidate is divisible by 3 (where k is a multiple of 3). If you tested up to n=10000 then you get weights of 5000, 10000

4) Now using a covering set of 3, instead of using base 2.. you go to base 4, but test only to n=5000.
you have 262144*2 k's. (as all k's less than 262144 and these k*2; ie k1=k & k2=k*2)

5) If a k is not a multiple of 3, then for k1 and k2 you will either get 0 or the weight that would be the same for base 2.
For numbers that are multiples of 3.. you generated 2 new k weights. for k1 and k2


Repeating the above process for the covering set of 2^5760-1
{3, 5, 7, 11, 13, 17, 19, 31, 37, 41, 61, 97, 163, 193, 271, 541, 641, 769}

you can generate k that have low weight but are to be tested for base=2^5760.

Then you can sieve up to 1200 to get an approximate nash weight. But given the extremely small weight of these k, you increase the n=1000000

Here are the numbers I generated with number of candidate remaining. The first 40 have been tested to 2M. The others to 250K.


I hope this makes sense.
Attached Files
File Type: txt Lowk_low weight.txt (12.4 KB, 70 views)
Citrix is offline   Reply With Quote
Old 2013-08-15, 07:50   #11
Thomas11
 
Thomas11's Avatar
 
Feb 2003

24×7×17 Posts
Default

Thanks for the further explanation, Citrix!

So, you are splitting the sequence k*2^n-1 into multiple sub-sequences: (k*2^i)*(2^5760)^m-1, where n=5760*m+i. And some of those sub-sequences (or quite many - depending on k) are eliminated by the covering set. This is essentially the idea behind Geoffrey Reynolds' sr1sieve and sr2sieve.

In other words you are just picking some "slices" of n (mod 5760) from the whole sequence. Summing up the weights of all sub-sequences should yield the weight of the original sequence.

If you concentrate on just one (or a few) of those sub-sequences, then it's obviously faster than testing the whole sequence. But typically one has to pick quite a few low weight k's to find at least one prime. Thus, on average it shouldn't make a difference whether to pick a few of the "whole" sequences, or a few hundreds of the ultra-low-weight sub-sequences (out of the same set of k).

To give just a simpler example for illustration:

Let's take k=3, e.g. 3*2^n-1. After some appropriate sieving, there will be even and odd exponents surviving (since k is divisible by 3). We could therefore split the original sequence into even and odd exponents: 3*2^(2m)-1 and 3*2^(2m+1)-1 (= 3*4^m-1 and 6*4^m-1).

Then k=3 in base=4 is just a subset of k=3 in base=2. But if the goal is to test the whole set of k=3 in base=2 up to a given n, then there is no benefit from testing both k=3 and k=6 in base=4 up to m=n/2.

Last fiddled with by Thomas11 on 2013-08-15 at 07:53
Thomas11 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Generating from 16 to 35 digit number in row (+1) pepi37 Math 10 2018-03-02 16:50
Generating Low-Weight Ks henryzz Riesel Prime Search 9 2012-04-09 21:36
Generating Random Primes davar55 Math 14 2011-02-20 16:06
Generating 2005 Wacky Puzzles 46 2005-06-05 22:19
Prime-generating polynomials Orgasmic Troll Math 28 2004-12-02 16:37

All times are UTC. The time now is 04:37.

Tue Jul 14 04:37:40 UTC 2020 up 111 days, 2:10, 0 users, load averages: 2.09, 2.23, 2.25

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.