mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Riesel Prime Search (https://www.mersenneforum.org/forumdisplay.php?f=59)
-   -   Generating low weight multipliers (https://www.mersenneforum.org/showthread.php?t=18471)

Thomas11 2013-08-01 08:21

Generating low weight multipliers
 
[QUOTE=Citrix;347947]Thomas11 could you post the other extremely low wt numbers you generated.:bow: Thanks![/QUOTE]

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 [URL="http://www.mersenneforum.org/showthread.php?t=16700"]here[/URL].

Citrix 2013-08-02 07:31

[QUOTE=Thomas11;347948]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 [URL="http://www.mersenneforum.org/showthread.php?t=16700"]here[/URL].[/QUOTE]

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.:smile: (close to 1.5 in 2 Million):censored:

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.:smile:

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

Thomas11 2013-08-12 14:24

Hi Citrix,

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

[QUOTE=Citrix;348012]
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
[/QUOTE]

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 2013-08-12 15:12

[QUOTE=Citrix;348012]
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
[/QUOTE]

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.

henryzz 2013-08-12 20:00

Do you have a method of sieving these?
The only siever I have found that does such large ks is [url]http://fatphil.org/maths/ksieve/[/url]
It only works if the k is made up of factors <10^15 though which rules most of these out.

Thomas11 2013-08-12 20:25

[QUOTE=henryzz;349287]Do you have a method of sieving these?[/QUOTE]

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...

henryzz 2013-08-12 22:03

I suppose once you take into account the covering set there aren't many ns anyway.

Citrix 2013-08-13 20:22

[QUOTE=Thomas11;349256]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.[/QUOTE]

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? :smile:

Thomas11 2013-08-14 17:22

[QUOTE=Citrix;349435]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.[/QUOTE]

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. :confused:

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 [B]huge[/B] covering set, leading to k much larger than 64 bits or even 128 or 256 bits.
Or did you mean a covering set of [I]length[/I] 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. :unsure:

Perhaps, if you would post a few of the Ks generated by your procedure, I could find out what I'm missing...

Citrix 2013-08-14 22:12

1 Attachment(s)
[QUOTE=Thomas11;349544]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. :confused:

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 [B]huge[/B] covering set, leading to k much larger than 64 bits or even 128 or 256 bits.
Or did you mean a covering set of [I]length[/I] 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. :unsure:

Perhaps, if you would post a few of the Ks generated by your procedure, I could find out what I'm missing...[/QUOTE]

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.:smile:

Thomas11 2013-08-15 07:50

Thanks for the further explanation, Citrix!

So, you are splitting the sequence [B]k*2^n-1[/B] into multiple sub-sequences: [B](k*2^i)*(2^5760)^m-1[/B], where [B]n=5760*m+i[/B]. 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. [B]3*2^n-1[/B]. 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: [B]3*2^(2m)-1[/B] and [B]3*2^(2m+1)-1[/B] (= [B]3*4^m-1[/B] and [B]6*4^m-1[/B]).

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.


All times are UTC. The time now is 13:50.

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