mersenneforum.org  

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

Reply
 
Thread Tools
Old 2013-11-05, 18:33   #1
pepi37
 
pepi37's Avatar
 
Dec 2011
After milion nines:)

24028 Posts
Default Nash weight of base 17

If I wont to test something like 7*17^n-1 and 9*17^n-1 how to calculate nash weight? Or just to make small sieve and look what sieve is bigger?
Bigger sieve, more weight.
pepi37 is online now   Reply With Quote
Old 2013-11-05, 18:40   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3

5·1,811 Posts
Default

Nice, easy question. ;-)
The weight for either sequence is precisely 0.
All values are divisible by 2.
Batalov is offline   Reply With Quote
Old 2013-11-05, 18:44   #3
pepi37
 
pepi37's Avatar
 
Dec 2011
After milion nines:)

2×641 Posts
Default

Ah: read my lips :something like 7*17^n-1 and 9*17^n-1 :)
14*17^n-1 and 16*17^n-1 is new examples :))
pepi37 is online now   Reply With Quote
Old 2013-11-05, 18:51   #4
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3

5×1,811 Posts
Default

http://mersenneforum.org/search.php
Keyword(s): Nash weight
and press "Search"
Batalov is offline   Reply With Quote
Old 2013-11-06, 08:42   #5
kar_bon
 
kar_bon's Avatar
 
Mar 2006
Germany

B0116 Posts
Default

The Nash weight of a number k*2^n+1 (k odd) is defined as the value of n remaining the sieve for 100000 <= n < 110000 and a max factor of 256.

Using srsieve you can try
srsieve -q -n 100000 -N 109999 -P 256 -G "14*17^n-1"

getting a sieve file with 894 candidates left so Nash weight is here 894.
kar_bon is offline   Reply With Quote
Old 2013-11-06, 11:45   #6
Thomas11
 
Thomas11's Avatar
 
Feb 2003

11·173 Posts
Default

Quote:
Originally Posted by kar_bon View Post
The Nash weight of a number k*2^n+1 (k odd) is defined as the value of n remaining the sieve for 100000 <= n < 110000 and a max factor of 256.
Sorry, kar_bon, but this is not the correct definition of the Nash weight.
It's the number of remaining n for the interval 100000 <= n < 110000 surviving a Nash sieve with an exponent limit of 256.

The Nash sieve doesn't use just the primes up to a given limit (256 in our case) as an ordinary sieve like srsieve does.
Instead it sieves against numbers of the type 2^e-1 (or more precisely it's factorizations), where the exponent e runs up to the given exponent limit of 256. This makes the implementation of the Nash sieve much more complicated than an ordinary sieve.

Regarding the weights this means that a Nash sieve up to e=256 finds more factors than a standard sieve up to p=256. You will notice this difference if you compare the weights obtained by your srsieve procedure to the ones computed either by PSieve or by the Nash weight tool.

And regarding pepi37's question:
For different bases, like b=17, the Nash sieve as described before doesn't provide a proper sieve base due to the limitation to factors of the type 2^e-1.
One could define something like a Generalized Nash sieve/weight by using a factor base of b^e-1 and the standard exponent limit of 256.

Nevertheless, if the aim is just to have some kind of a weight for classifying multiple sequences into low or high weights, the procedure described by kar_bon, e.g. using srsieve up to p=256, might be simpler and faster.

Last fiddled with by Thomas11 on 2013-11-06 at 11:47
Thomas11 is offline   Reply With Quote
Old 2013-11-06, 13:31   #7
pepi37
 
pepi37's Avatar
 
Dec 2011
After milion nines:)

101000000102 Posts
Default

So Thomas , kar-bon example can be used as quick examin of candidate weight?
Where I can download Nash sieve?
pepi37 is online now   Reply With Quote
Old 2013-11-06, 13:54   #8
kar_bon
 
kar_bon's Avatar
 
Mar 2006
Germany

32×313 Posts
Default

I've forgotten this post.

Comparing psieve3.exe with srsieve gives this: the results given by psieve3 are almost the same as for srsieve with -P 511.
kar_bon is offline   Reply With Quote
Old 2013-11-06, 14:11   #9
Thomas11
 
Thomas11's Avatar
 
Feb 2003

11×173 Posts
Default

Quote:
Originally Posted by pepi37 View Post
So Thomas , kar-bon example can be used as quick examin of candidate weight?
Yes, Pepi37, you can use the procedure described by kar_bon as a quick estimate for the weight of a sequence.

The original Nash sieve (Psieve) can be found on Chris Nash's homepage:
http://pages.prodigy.net/chris_nash/psieve.html

However, this link seems to be dead.
And the wayback machine doesn't work either at the moment.

There is also a Java applet written by Jack Brennen, which can be found here. This one computes the so called Proth weight and is for numbers of the form k*2^n+1, but can also used for the k*2^n-1 by entering k as -k.
The Proth weight is related to the Nash weight by a scaling factor of 1/1751.542, where 1751.542 is just the average Nash weight.

My Nash weight tool closely follows Jack Brennen's algorithm and can be found at several places in the forum, e.g. here.

Note that neither the Java applet nor my Nash tool can be used for other bases than b=2.
Thomas11 is offline   Reply With Quote
Old 2013-11-06, 14:30   #10
kar_bon
 
kar_bon's Avatar
 
Mar 2006
Germany

32×313 Posts
Default

Here's psieve3.exe.
Attached Files
File Type: zip psieve3.zip (36.1 KB, 51 views)
kar_bon is offline   Reply With Quote
Old 2013-11-06, 14:53   #11
Thomas11
 
Thomas11's Avatar
 
Feb 2003

11×173 Posts
Default

Quote:
Originally Posted by kar_bon View Post
Here's psieve3.exe.
Thanks for the file, Karsten!

I did a quick modification to my Nash code and for Pepi37's 14*17^n-1 sequence I got the same weight (803) as with PSieve3.exe.

I will have to make it a bit more robust before posting a public binary here. But stay tuned...
Thomas11 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Nash value pepi37 Math 0 2018-03-23 21:27
John Nash's letter to the NSA predecessors Christenson Math 10 2012-02-25 16:39
Nash Weights vs. Sievability LiquidNitrogen Information & Answers 7 2011-08-03 03:06
Base-6 speed for prime testing vs. base-2 jasong Conjectures 'R Us 36 2010-08-03 06:25
How to calculate Nash/robinson weight? cipher No Prime Left Behind 6 2009-05-09 15:35

All times are UTC. The time now is 07:38.

Sun Jul 5 07:38:36 UTC 2020 up 102 days, 5:11, 1 user, load averages: 1.26, 1.32, 1.32

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.