 mersenneforum.org Generating low weight multipliers
 Register FAQ Search Today's Posts Mark Forums Read  2013-08-01, 08:21   #1
Thomas11

Feb 2003

190810 Posts Generating low weight multipliers

Quote:
 Originally Posted by Citrix 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   2013-08-02, 07:31   #2
Citrix

Jun 2003

110001011102 Posts Quote:
 Originally Posted by Thomas11 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   2013-08-12, 14:24   #3
Thomas11

Feb 2003

22×32×53 Posts Hi Citrix,

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

Quote:
 Originally Posted by Citrix 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   2013-08-12, 15:12   #4
Thomas11

Feb 2003

22×32×53 Posts Quote:
 Originally Posted by Citrix 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.

Last fiddled with by Thomas11 on 2013-08-12 at 15:22   2013-08-12, 20:00 #5 henryzz Just call me Henry   "David" Sep 2007 Cambridge (GMT/BST) 2·3·5·197 Posts 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.   2013-08-12, 20:25   #6
Thomas11

Feb 2003

22×32×53 Posts Quote:
 Originally Posted by henryzz 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...   2013-08-12, 22:03 #7 henryzz Just call me Henry   "David" Sep 2007 Cambridge (GMT/BST) 171616 Posts I suppose once you take into account the covering set there aren't many ns anyway.   2013-08-13, 20:22   #8
Citrix

Jun 2003

30568 Posts Quote:
 Originally Posted by Thomas11 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   2013-08-14, 17:22   #9
Thomas11

Feb 2003

22·32·53 Posts Quote:
 Originally Posted by Citrix 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...   2013-08-14, 22:12   #10
Citrix

Jun 2003

62E16 Posts Quote:
 Originally Posted by Thomas11 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 Lowk_low weight.txt (12.4 KB, 168 views)   2013-08-15, 07:50 #11 Thomas11   Feb 2003 77416 Posts 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   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post pepi37 Math 10 2018-03-02 16:50 henryzz Riesel Prime Search 9 2012-04-09 21:36 davar55 Math 14 2011-02-20 16:06 Wacky Puzzles 46 2005-06-05 22:19 Orgasmic Troll Math 28 2004-12-02 16:37

All times are UTC. The time now is 12:00.

Sun Sep 26 12:00:57 UTC 2021 up 65 days, 6:29, 0 users, load averages: 1.41, 1.42, 1.41