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: [url]http://www.primenumbers.net/prptop/prptop.php[/url].

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.

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

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

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

Philippe

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)

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

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

[QUOTE=firejuggler;279648]And if i can add a request, add a switch to remove +1 and/or -1 c value.[/QUOTE]

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.

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

I've posted 1.0.1 here: [url]http://home.roadrunner.com/~mrodenkirch/fnsieve_1.0.1.zip[/url]. 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.

[QUOTE=rogue;279737] 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.[/QUOTE]

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