fnsieve

rogue · 2011-11-23, 16:49

By request, I have created a sieve program that can handle k*b^n+c sequences for fixed k, b, and n with variable c. You can d/l it from here:

home.roadrunner.com/~mrodenkirch/fnsieve_1.0.0.zip

It only handles one sequence at a time and c can be negative, for example:

fnsieve -P1e9 -c-100 -C10000 10^^20000+c

It will output an ABC file to be used by pfgw, although I presume that LLR can also read the output format. With this program it should be easy to add many new PRPs to Henri & Renaud Lifchitz's site: http://www.primenumbers.net/prptop/prptop.php.

It includes a 64-bit Windows build. Since it is mostly hacked from srsieve, it can be built on Linux and OS X as well.

If you have any questions or run into any problems, you know where to find me.

Phil MjX · 2011-11-23, 22:12

Hi Mark !

Thank you for the sieve : it may be very usefull for brilliant number search too !
A concern for me under windows 7 (64 bits) and precompiled binary:

>fnsieve_win64 -A 1 -c 1 -C 10000000 -s 10 -r 30 10^^80+c

With this command line, the search seems to slow down a lot at p=2^32, with no screen report every 30 seconds and no factor found for minutes...

...and if I interrrupt the sieve after a few minutes, the fnsieve.log message is
11/23/11 22:31:48 fnsieve stopped: at p=4294974457 because SIGINT was received.

I have tried with negative c, same problem (the p is different, but only just over 2^32)
With -c and -C as only flags, huge slowdown again
With exponents of 800 or 8000, with -C 10000...nothing better !

No memory explosion, 25% of my quad is busy...everything seems OK.

(edit, in fact, one factor has popped out after p=2^32 with -C=1e8, but I have the feeling that some were missed between 2^32 and the p limit of p=4294987951, so I'd think there may be a bug somewere rather than a prime gap).

Have I done something wrong, or is the sieve much, much, much slower for p > 2^32 ?

Indeed, thanks for the tool !
Kind regards,

Philippe

rogue · 2011-11-23, 22:26

It's quite possible that it has a bug. I'll look into it.

Phil MjX · 2011-11-23, 23:04

Thanks a lot! The sieve is blazing fast up to 2^32 and hopefully after!

Philippe

firejuggler · 2011-11-24, 00:32

1337*1337^1337+-1580 is 3-PRP! (0.6404s+0.0002s)
1337*1337^1337+2844 is 3-PRP! (0.3435s+0.0002s)

from -10k to +10k
( 4800+ digits, minimum size is 22000)

rogue · 2011-11-24, 00:54

I found the problem which occurs for p > 2^32. I'll try to fix it tonight or tomorrow.

firejuggler · 2011-11-24, 01:12

And if i can add a request, add a switch to remove +1 and/or -1 c value.

rogue · 2011-11-24, 01:37

Quote:

Originally Posted by firejuggler

And if i can add a request, add a switch to remove +1 and/or -1 c value.

Do you mean a specific c or a list of c? I don't understand why you would need to do that. (It's not a difficult change, just a question of why.)

BTW, I don't have a Win64 box available to me until Monday, so although I can release the code, building for Win64 is a different issue. I think that I can build it on WinXP, but I cannot test it on that platform. My code changes do work on OS X though, so I expect them to work on Win64.

firejuggler · 2011-11-24, 02:18

524042*51^10120-1 is prime, and i know that the +1 side is not. Would i look thru c value between -1e6 and 1e6, those two value does not need to be included into the result, rather than run 2 run, -1e6 ,-3 then 3, 1e6.

*edit : seem dumb now, but for large b^n, it can remove 2 test at least

rogue · 2011-11-24, 18:17

I've posted 1.0.1 here: http://home.roadrunner.com/~mrodenki...ieve_1.0.1.zip. The included build is for Win64. I can't test it as I don't have a Win64 box available to me.

The only change is to address sieving for p > 2^32. The other change will need to wait until next week.

science_man_88 · 2011-11-24, 18:20

Quote:

Originally Posted by rogue

I can't test it as I don't have a Win64 box available to me.

The only change is to address sieving for p > 2^32. The other change will need to wait until next week.

I have a windows 64 bit system but it's kinda partially bogged down by prime95 and aliquot sequence stuff.

2011-11-23, 16:49	#1
rogue "Mark" Apr 2003 Between here and the 18D2₁₆ Posts	fnsieve By request, I have created a sieve program that can handle k*b^n+c sequences for fixed k, b, and n with variable c. You can d/l it from here: home.roadrunner.com/~mrodenkirch/fnsieve_1.0.0.zip It only handles one sequence at a time and c can be negative, for example: fnsieve -P1e9 -c-100 -C10000 10^^20000+c It will output an ABC file to be used by pfgw, although I presume that LLR can also read the output format. With this program it should be easy to add many new PRPs to Henri & Renaud Lifchitz's site: http://www.primenumbers.net/prptop/prptop.php. It includes a 64-bit Windows build. Since it is mostly hacked from srsieve, it can be built on Linux and OS X as well. If you have any questions or run into any problems, you know where to find me.

2011-11-23, 22:12	#2
Phil MjX Sep 2004 271₈ Posts	Hi Mark ! Thank you for the sieve : it may be very usefull for brilliant number search too ! A concern for me under windows 7 (64 bits) and precompiled binary: >fnsieve_win64 -A 1 -c 1 -C 10000000 -s 10 -r 30 10^^80+c With this command line, the search seems to slow down a lot at p=2^32, with no screen report every 30 seconds and no factor found for minutes... ...and if I interrrupt the sieve after a few minutes, the fnsieve.log message is 11/23/11 22:31:48 fnsieve stopped: at p=4294974457 because SIGINT was received. I have tried with negative c, same problem (the p is different, but only just over 2^32) With -c and -C as only flags, huge slowdown again With exponents of 800 or 8000, with -C 10000...nothing better ! No memory explosion, 25% of my quad is busy...everything seems OK. (edit, in fact, one factor has popped out after p=2^32 with -C=1e8, but I have the feeling that some were missed between 2^32 and the p limit of p=4294987951, so I'd think there may be a bug somewere rather than a prime gap). Have I done something wrong, or is the sieve much, much, much slower for p > 2^32 ? Indeed, thanks for the tool ! Kind regards, Philippe Last fiddled with by Phil MjX on 2011-11-23 at 22:22

2011-11-23, 22:26	#3
rogue "Mark" Apr 2003 Between here and the 2×3²×353 Posts	It's quite possible that it has a bug. I'll look into it.

2011-11-23, 23:04	#4
Phil MjX Sep 2004 B9₁₆ Posts	Thanks a lot! The sieve is blazing fast up to 2^32 and hopefully after! Philippe

2011-11-24, 00:32	#5
firejuggler Apr 2010 Over the rainbow 2·1,303 Posts	13371337^1337+-1580 is 3-PRP! (0.6404s+0.0002s) 13371337^1337+2844 is 3-PRP! (0.3435s+0.0002s) from -10k to +10k ( 4800+ digits, minimum size is 22000)

2011-11-24, 00:54	#6
rogue "Mark" Apr 2003 Between here and the 2×3²×353 Posts	I found the problem which occurs for p > 2^32. I'll try to fix it tonight or tomorrow.

2011-11-24, 01:12	#7
firejuggler Apr 2010 Over the rainbow 2×1,303 Posts	And if i can add a request, add a switch to remove +1 and/or -1 c value.

2011-11-24, 02:18	#9
firejuggler Apr 2010 Over the rainbow 2·1,303 Posts	52404251^10120-1 is prime, and i know that the +1 side is not. Would i look thru c value between -1e6 and 1e6, those two value does not need to be included into the result, rather than run 2 run, -1e6 ,-3 then 3, 1e6. edit : seem dumb now, but for large b^n, it can remove 2 test at least

2011-11-24, 18:17	#10
rogue "Mark" Apr 2003 Between here and the 2×3²×353 Posts	I've posted 1.0.1 here: http://home.roadrunner.com/~mrodenki...ieve_1.0.1.zip. The included build is for Win64. I can't test it as I don't have a Win64 box available to me. The only change is to address sieving for p > 2^32. The other change will need to wait until next week.