mersenneforum.org Nash weight of base 17
 Register FAQ Search Today's Posts Mark Forums Read

 2013-11-05, 18:33 #1 pepi37     Dec 2011 After milion nines:) 3×11×43 Posts 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.
 2013-11-05, 18:40 #2 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 41·229 Posts Nice, easy question. ;-) The weight for either sequence is precisely 0. All values are divisible by 2.
 2013-11-05, 18:44 #3 pepi37     Dec 2011 After milion nines:) 58B16 Posts 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 :))
 2013-11-05, 18:51 #4 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 41×229 Posts http://mersenneforum.org/search.php Keyword(s): Nash weight and press "Search"
 2013-11-06, 08:42 #5 kar_bon     Mar 2006 Germany B4116 Posts 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.
2013-11-06, 11:45   #6
Thomas11

Feb 2003

77416 Posts

Quote:
 Originally Posted by kar_bon 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

 2013-11-06, 13:31 #7 pepi37     Dec 2011 After milion nines:) 58B16 Posts So Thomas , kar-bon example can be used as quick examin of candidate weight? Where I can download Nash sieve?
 2013-11-06, 13:54 #8 kar_bon     Mar 2006 Germany 43×67 Posts 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.
2013-11-06, 14:11   #9
Thomas11

Feb 2003

22·32·53 Posts

Quote:
 Originally Posted by pepi37 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

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.

2013-11-06, 14:30   #10
kar_bon

Mar 2006
Germany

43×67 Posts

Here's psieve3.exe.
Attached Files
 psieve3.zip (36.1 KB, 108 views)

2013-11-06, 14:53   #11
Thomas11

Feb 2003

22·32·53 Posts

Quote:
 Originally Posted by kar_bon 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...

 Similar Threads Thread Thread Starter Forum Replies Last Post pepi37 Math 0 2018-03-23 21:27 Christenson Math 10 2012-02-25 16:39 LiquidNitrogen Information & Answers 7 2011-08-03 03:06 jasong Conjectures 'R Us 36 2010-08-03 06:25 cipher No Prime Left Behind 6 2009-05-09 15:35

All times are UTC. The time now is 08:22.

Wed Apr 14 08:22:45 UTC 2021 up 6 days, 3:03, 0 users, load averages: 1.25, 1.45, 1.55