N:\sr2sieve>sr2sieve -i sr_2.abcd -p 1e6 -P 1e9 -x
sr2sieve 1.8.11 -- A sieve for multiple sequences k*b^n+/-1 or b^n+/-k.
Read 752555 terms for 89 sequences from ABCD format file `sr_2.abcd'.
Split 89 base 2 sequences into 178 base 2^2 subsequences.
ERROR: 4216856631*2^n-1: Square-free part 4216856631 of k too large.

Still does not work... ideas?

[QUOTE=f1pokerspeed;336015]N:\sr2sieve>sr2sieve -i sr_2.abcd -p 1e6 -P 1e9 -x
sr2sieve 1.8.11 -- A sieve for multiple sequences k*b^n+/-1 or b^n+/-k.
Read 752555 terms for 89 sequences from ABCD format file `sr_2.abcd'.
Split 89 base 2 sequences into 178 base 2^2 subsequences.
ERROR: 4216856631*2^n-1: Square-free part 4216856631 of k too large.

Still does not work... ideas?[/QUOTE]

My bad. That is enabled by default and cannot be disabled. Unfortunately it is not easy to fix the code to handle k larger than 31 bits and such a change could significantly impact performance.

That's understandable. I suppose I am relegated to the confines of srsieve...

[QUOTE=f1pokerspeed;336028]That's understandable. I suppose I am relegated to the confines of srsieve...[/QUOTE]

Did you try NewPGen? It can handle large k values. I don't know about the speed.

[QUOTE=Puzzle-Peter;336085]Did you try NewPGen? It can handle large k values. I don't know about the speed.[/QUOTE]
I agree worth trying. It isn't as fast as sr1sieve but it might be faster than srsieve for one k.

NewPGen seems to work very well and is quite convenient here - although I wish it could sieve all of the candidates at once, rather than just one K at a time. Thanks for the tip.

[QUOTE=f1pokerspeed;336155]NewPGen seems to work very well and is quite convenient here - although I wish it could sieve all of the candidates at once, rather than just one K at a time. Thanks for the tip.[/QUOTE]

Use few instances of NewPGen in parallel :) One for each K

If it is multiple ks I would guess that srsieve is the way forward. I read it wrong I thought you had 1 k that wouldn't work in sr2sieve.
It would be worth checking how many of your ks have squares in them and the squarefree part is small enough.

Can someone re-post the latest version of srsieve?
The link to [URL]http://home.roadrunner.com/~mrodenkirch/srsieve_1.0.6.zip[/URL] appears broken.

[QUOTE=TheCount;357656]Can someone re-post the latest version of srsieve?
The link to [URL]http://home.roadrunner.com/~mrodenkirch/srsieve_1.0.6.zip[/URL] appears broken.[/QUOTE]
[URL="http://home.roadrunner.com/~mrodenkirch/srsieve_1.0.7.zip"][COLOR=#0066cc]http://home.roadrunner.com/~mrodenkirch/srsieve_1.0.7.zip[/COLOR][/URL]

This is what I wanted, but the zip seems to contain v 1.0.5, not v 1.0.7.

[QUOTE=TheCount;357661]This is what I wanted, but the zip seems to contain v 1.0.5, not v 1.0.7.[/QUOTE]

It is 1.0.7. I forgot to change the version.h file.

Some problems with compilation v. 1.0.7. I've tried gcc 4.1.2 and 4.4.7

[CODE]files.c: In function ‘add_seq_knc’:
files.c:373: error: called object ‘filter_k’ is not a function
files.c: In function ‘read_input_file’:
files.c:711: error: ‘null’ undeclared (first use in this function)
files.c:711: error: (Each undeclared identifier is reported only once
files.c:711: error: for each function it appears in.)
make: *** [files.o] Error 1[/CODE]

sr1sieve 1.4.5 and sr2sieve 1.9.3 are both compiled and work well.
I've "patched" srsieve sources, it is now able to compile but crashes with "Floating point exception" error. :sad:

[QUOTE=unconnected;357698]Some problems with compilation v. 1.0.7. I've tried gcc 4.1.2 and 4.4.7

[CODE]files.c: In function ‘add_seq_knc’:
files.c:373: error: called object ‘filter_k’ is not a function
files.c: In function ‘read_input_file’:
files.c:711: error: ‘null’ undeclared (first use in this function)
files.c:711: error: (Each undeclared identifier is reported only once
files.c:711: error: for each function it appears in.)
make: *** [files.o] Error 1[/CODE][/QUOTE]

filter_k is declared on line 47. Try "NULL" instead of "null".

[QUOTE=unconnected;357720]sr1sieve 1.4.5 and sr2sieve 1.9.3 are both compiled and work well.
I've "patched" srsieve sources, it is now able to compile but crashes with "Floating point exception" error. :sad:[/QUOTE]

I think I have some changes I made on my Mac to address some issues, but never ported them back to Windows. I'll take a look tonight.

Can you in sr1sieve set -f option by default - so you dont have add it in command line ( like in sr2sieve)?

[QUOTE=pepi37;357766]Can you in sr1sieve set -f option by default - so you dont have add it in command line ( like in sr2sieve)?[/QUOTE]

Not everyone wants and output file of factors from sr1sieve. I assume that most just use the -o option to write a file with the factors removed.

Rogue,

when compiling on Mac Os X 10.9 I get the following error:

[CODE]imac-van-cedric-vonck:srsieve_1.0.7 cedricvonck$ make
gcc -O2 -fomit-frame-pointer -ffast-math -march=k8 -m64 -Wall -DHAVE_CMOV -DUSE_ASM -DNDEBUG -c -o srsieve.o srsieve.c
gcc -O2 -fomit-frame-pointer -ffast-math -march=k8 -m64 -Wall -DHAVE_CMOV -DUSE_ASM -DNDEBUG -c -o arithmetic32.o arithmetic32.c
gcc -O2 -fomit-frame-pointer -ffast-math -march=k8 -m64 -Wall -DHAVE_CMOV -DUSE_ASM -DNDEBUG -c -o arithmetic64.o arithmetic64.c
gcc -O2 -fomit-frame-pointer -ffast-math -march=k8 -m64 -Wall -DHAVE_CMOV -DUSE_ASM -DNDEBUG -c -o bitmap.o bitmap.c
In file included from bitmap.c:18:
In file included from ./memset_fast32.h:21:
./asm-x86-64-gcc.h:394:41: error: fields must have a constant size: 'variable length array in structure' extension will never be supported
"=m" (*(struct { uint_fast32_t dummy[count]; } *)dst)
^
1 error generated.
make: *** [bitmap.o] Error 1
imac-van-cedric-vonck:srsieve_1.0.7 cedricvonck$ gcc -v
Configured with: --prefix=/Applications/Xcode.app/Contents/Developer/usr --with-gxx-include-dir=/Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX10.9.sdk/usr/include/c++/4.2.1
Apple LLVM version 5.0 (clang-500.2.79) (based on LLVM 3.3svn)
Target: x86_64-apple-darwin13.0.0
Thread model: posix
imac-van-cedric-vonck:srsieve_1.0.7 cedricvonck$
[/CODE]

Can you please help me?
Thank you

[QUOTE=CedricVonck;359173]Rogue,

when compiling on Mac Os X 10.9 I get the following error:

[CODE]imac-van-cedric-vonck:srsieve_1.0.7 cedricvonck$ make
gcc -O2 -fomit-frame-pointer -ffast-math -march=k8 -m64 -Wall -DHAVE_CMOV -DUSE_ASM -DNDEBUG -c -o srsieve.o srsieve.c
gcc -O2 -fomit-frame-pointer -ffast-math -march=k8 -m64 -Wall -DHAVE_CMOV -DUSE_ASM -DNDEBUG -c -o arithmetic32.o arithmetic32.c
gcc -O2 -fomit-frame-pointer -ffast-math -march=k8 -m64 -Wall -DHAVE_CMOV -DUSE_ASM -DNDEBUG -c -o arithmetic64.o arithmetic64.c
gcc -O2 -fomit-frame-pointer -ffast-math -march=k8 -m64 -Wall -DHAVE_CMOV -DUSE_ASM -DNDEBUG -c -o bitmap.o bitmap.c
In file included from bitmap.c:18:
In file included from ./memset_fast32.h:21:
./asm-x86-64-gcc.h:394:41: error: fields must have a constant size: 'variable length array in structure' extension will never be supported
"=m" (*(struct { uint_fast32_t dummy[count]; } *)dst)
^
1 error generated.
make: *** [bitmap.o] Error 1
imac-van-cedric-vonck:srsieve_1.0.7 cedricvonck$ gcc -v
Configured with: --prefix=/Applications/Xcode.app/Contents/Developer/usr --with-gxx-include-dir=/Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX10.9.sdk/usr/include/c++/4.2.1
Apple LLVM version 5.0 (clang-500.2.79) (based on LLVM 3.3svn)
Target: x86_64-apple-darwin13.0.0
Thread model: posix
imac-van-cedric-vonck:srsieve_1.0.7 cedricvonck$
[/CODE]

Can you please help me?
Thank you[/QUOTE]

I ran into the same problem. I just changed the routine to use memset, but ran into another problem. The application crashes. I suspect a compiler bug in the latest Xcode.

Has the stop on removal rate feature been added to sr1sieve? I have tried using -R and -r, and neither argument is handled by the program...

[QUOTE=f1pokerspeed;364465]Has the stop on removal rate feature been added to sr1sieve? I have tried using -R and -r, and neither argument is handled by the program...[/QUOTE]

No. -r is used when sieving for RieselSieve and I don't even know if they use it for that project. -R was never added to sr1sieve.

srsieve 1.0.7 bug
 

While demonstrating srsieve to a friend we happened to try 2^n-1 for n=1 to 1M with the following results in the output file:

[CODE]
pmin=16481841017
2^n-1
1
3
7
13
17
19
31
61
89
.
.
.
etc
[/CODE]

It would appear to have incorrectly factored out n=2 and n=5. while this, of it's self, is not a real worry I was wondering if it was a problem in the code which may be propagated into the 'normal' search areas.

(Note. Geoffrey Reynolds' srsieve ver. 0.6.17 doesn't have this problem)

It seems to be something that was introduced in 1.0.7. 1.0.6 has the correct output. I'll look into it.

Where can I find the latest version of srsieve's source? The link posted previously no longer works.

[QUOTE=wombatman;391882]Where can I find the latest version of srsieve's source? The link posted previously no longer works.[/QUOTE]

[URL]http://www.bc-team.org/downloads.php?cat=7[/URL]

[QUOTE=wombatman;391882]Where can I find the latest version of srsieve's source? The link posted previously no longer works.[/QUOTE]

Sorry about that. My provider no longer hosts websites and I've been too busy to look for a new one.

If you're using git for source code management, GitHub is free and awesome.

[QUOTE=rebirther;391983][URL]http://www.bc-team.org/downloads.php?cat=7[/URL][/QUOTE]

Thanks rebirther--no idea how I forgot about that since that's where I got all the sievers in the 1st place. :davieddy:

*BUMP*

I was using "srsieve" and it seems to be faster than "newpgen" for the sieve I was using.

It is sieving k*b^n+c for variable k or n. Would it be hard to add sieving for fixed k and n, and variable c instead for general consecutive prime sieving?

[QUOTE=ATH;476083]*BUMP*

I was using "srsieve" and it seems to be faster than "newpgen" for the sieve I was using.

It is sieving k*b^n+c for variable k or n. Would it be hard to add sieving for fixed k and n, and variable c instead for general consecutive prime sieving?[/QUOTE]

I wrote something called fnsieve (and fnsievecl) a while ago. I believe that will do what you want. If you need sources/exes, please let me know.

Yes please. I found the thread but the download links in it does not work anymore:
[url]http://mersenneforum.org/showthread.php?t=16250[/url]

[QUOTE=ATH;476173]Yes please. I found the thread but the download links in it does not work anymore:
[url]http://mersenneforum.org/showthread.php?t=16250[/url][/QUOTE]

I'll post corrected links to them later today.

I updated the link in a recent post to [URL="http://www.mersenneforum.org/showthread.php?t=16250"]this thread[/URL].

In 1.1.1, I fixed a bug with ABCD file creation. srsieve/srfile can create lines like this:

[code]
ABCD 42989431*2^$a+1ABCD 42989433*2^$a+1 [14520]
[/code]

if a sequence doesn't have any terms. In this case 42989431*2^$a+1 has no terms, but it still created the ABCD header.

[QUOTE=rogue;477072]In 1.1.1, I fixed a bug with ABCD file creation. srsieve/srfile can create lines like this:

[code]
ABCD 42989431*2^$a+1ABCD 42989433*2^$a+1 [14520]
[/code]if a sequence doesn't have any terms. In this case 42989431*2^$a+1 has no terms, but it still created the ABCD header.[/QUOTE]

I have found difference in number of candidates that produce new and old srsieve.
Or your srsieve is better then Batalov script so removes more factors, or something is fishy

old srsieve ( 1.06) produces 6954 candidates in range 1M - 1M5 in sequence 64*259^n+1
new srsieve ( 1.11) produces 7948 candidates in range 1M - 1M5 in sequence 64*259^n+1

when I run Batalov script in new npeg file it found additional 994 factors that new srsieve didnot remove

6954+994=7948 : so in the final both number of candidates match

Also I noticed that Batalov trick of removing factors "3333333333333333333333 | 64*259*^1000449+1" doesnot work with new or with old srsieve ( and so far it only doesnot work on this sequence)

-------------------------------------------------------------------------------------------------------------------------------------
old srsieve ( 1.06) produces 22935 candidates in range 1M - 1M5 in sequence 64*100^n+1
new srsieve ( 1.11) produces 19183 candidates in range 1M - 1M5 in sequence 64*100^n+1

In npgen file from srsieve 1.06 Batalov script found additional 2387 factors
In npgen file from srsieve 1.11 Batalov script doesnot found no additional factors

22935-2387=20548

So difference after removing factors from Batalov script is 1365 candidates less created with new srsieve(1.11)

Batalov trick in this case work and factors can be removed when are in form "3333333333333333333333 | 64*100^1001012+1"

-------------------------------------------------------------------------------------------------------------------------------------
old srsieve ( 1.06) produces 23386 candidates in range 1M - 1M5 in sequence 4*155^n+1
new srsieve ( 1.11) produces 16650 candidates in range 1M - 1M5 in sequence 4*155^n+1

In npgen file from srsieve 1.06 Batalov script found additional 6736 factors
In npgen file from srsieve 1.11 Batalov script doesnot found no additional factors

23386-6736= 16650 - so remain number of candidate is match

-------------------------------------------------------------------------------------------------------------------------------------
old srsieve ( 1.06) produces 44043 candidates in range 1M - 1M5 in sequence 4*100^n+1
new srsieve ( 1.11) produces 36735 candidates in range 1M - 1M5 in sequence 4*100^n+1

In npgen file from srsieve 1.06 Batalov script found additional 4734 factors
In npgen file from srsieve 1.11 Batalov script doesnot found no additional factors

44043-4734= 39309

So difference after removing factors from Batalov script is 2574 candidates

There is also difference in sequence 64*500^n+1....

I found the issue, but I need to run tests to verify that it doesn't output invalid algebraic factors.

Since srsieve finds algebraic factors not found by Serge's script, I recommend that you run the algebraic log file thru pfgw to verify that it returns "is Zero" for each algebraic factor.

Yes, something is wrong I tested srsieve 1.06 and 1.11 with the line:
srsieve -n 1000000 -N 1500000 -f -m 2 "64*259^n+1" > NUL

So it saves all factors to srfactors.txt but does not output them to screen.

Sieving up to 4.25*10^11 version 1.06 found 328,968 factors while 1.11 found 370,214 factors.

Testing the factors with a quick GMP program shows they are all correct factors, but [I]both[/I] versions are missing factors. 1.06 finds 5 is a factor of 166,667 numbers and 1.11 finds only 125,000. The correct number is 250,001: 1000000,1000002,1000004,...,1500000.

1.06 finds that 11 is a factor of 33,333 numbers while 1.11 finds the correct number: of factors: 50,000: 1000001,1000011,1000021,...,1499991

1.06 finds that 17 is a factor of 66,668 numbers while 1.11 finds the correct number of factors: 100,000.

[CODE]1.06:
5 | 64*259^1000000+1
5 | 64*259^1000004+1
5 | 64*259^1000006+1
5 | 64*259^1000010+1
5 | 64*259^1000012+1
5 | 64*259^1000016+1
5 | 64*259^1000018+1
5 | 64*259^1000022+1
5 | 64*259^1000024+1
5 | 64*259^1000028+1
5 | 64*259^1000030+1
.
.
1.11
5 | 64*259^1000002+1
5 | 64*259^1000006+1
5 | 64*259^1000010+1
5 | 64*259^1000014+1
5 | 64*259^1000018+1
5 | 64*259^1000022+1
5 | 64*259^1000026+1
5 | 64*259^1000030+1
.
.
1.06
11 | 64*259^1000001+1
11 | 64*259^1000021+1
11 | 64*259^1000031+1
11 | 64*259^1000051+1
11 | 64*259^1000061+1
11 | 64*259^1000081+1
11 | 64*259^1000091+1
.
.
1.11
11 | 64*259^1000001+1
11 | 64*259^1000011+1
11 | 64*259^1000021+1
11 | 64*259^1000031+1
11 | 64*259^1000041+1
11 | 64*259^1000051+1
11 | 64*259^1000061+1
11 | 64*259^1000071+1
11 | 64*259^1000081+1
11 | 64*259^1000091+1
.
.
1.06
17 | 64*259^1000003+1
17 | 64*259^1000007+1
17 | 64*259^1000015+1
17 | 64*259^1000019+1
17 | 64*259^1000027+1
17 | 64*259^1000039+1
17 | 64*259^1000043+1
17 | 64*259^1000055+1
.
.
1.11
17 | 64*259^1000003+1
17 | 64*259^1000007+1
17 | 64*259^1000015+1
17 | 64*259^1000019+1
17 | 64*259^1000023+1
17 | 64*259^1000027+1
17 | 64*259^1000035+1
17 | 64*259^1000039+1
17 | 64*259^1000043+1
17 | 64*259^1000047+1
17 | 64*259^1000055+1
.
.
[/CODE]

It will not write factors to the screen. It writes them to a log.

I will take a look at this later to see if that is solved by the fix I've made.

Note that some terms might be divisible by both an algebraic factor and 5 and as algebraic factorization is done first, it won't also find that the term is divisible by 5. Now if the term is divisible by 5 and is still remaining after sieving, then we have a problem.

You might be right, I started a sieve using newpgen to compare, and it seems to be the same remaining as 1.11, but I'm doing a new smaller test sieving only to 10^8, so it do not take many hours for each test.

If this is the case maybe add the algebraic factors somehow to srfactors.txt when -f is used?


Edit: I just noticed 1.11 created the algebraic factors in "alg_64_259_+1.log", I missed that.

Ok, so sieving the same range to 10^8 srsieve 1.11 matches NewPGen, both have 7,191 numbers remaining.

1.11 has 367,809 factors in srfactors.txt + 125,001 algebraic factors in "alg_64_259_+1.log" and 367,809 + 125,001 + 7,191 = 500,001 matching the range 1M-1.5M.

1.06 on the other hand has only 326,989 factors in srfactors.txt and it has no file with algebraic factors, but it has only 6,345 numbers remaining. So if that is correct it found 166,667 algebraic factors, and is more efficient than 1.11 and newpgen, or was this a bug you found back in 1.06?

There is a bug in v1.11 where it misses factors found in 1.06. That is fixed and I'm testing the fix right now. I'm testing all k from 2 to 2500 and all b from 2 to 1100 and all n from 1000 to 5000 and c of both +1 and -1. All algebraic factors go to a single file and can be double-checked with pfgw. Higher n don't really matter because if it misses factors for low n (or has a bug for low n), then it will occur on higher n. I expect close to 350,000,000 algebraic factors in that range. Generating the algebraic factors doesn't take long, but it does take a long time to run all of those thru pfgw. Also, since the log with the algebraic factors is many GB, I am doing it in ranges of k.

I also found a bug when searching for factors for 4*x^4*b^n+1. It eliminates the correct n, but write the wrong algebraic factor to the log.

Here is 1.1.2. It addresses the issues listed above. It took more than 30 hours to verify all algebraic factors in the range that i tested.

Very nice, thanks. It finds even more algebraic factors than 1.06 now, but 1.06 finds normal factors of the same numbers.

The test case "64*259^n+1", 1000000<=n<=1500000, Pmax=1e8

[CODE] factors algebraic remaining Total
srsieve 1.06 326,989 166,667 6,345 500,001
srsieve 1.11 367,809 125,001 7,191 500,001
srsieve 1.12 285,322 208,334 6,345 500,001

newpgen 2.82 ? ? 7,191
[/CODE]

Newpgen can only output the factors it finds above p=1M. Between 1M and 100M it finds 2,768 factors matching srsieve 1.11 while 1.06 and 1.12 finds 2,159 factors in that range. I do not know if it finds algebraic factors, it is not outputting them at least.

[QUOTE=ATH;478177]Very nice, thanks. It finds even more algebraic factors than 1.06 now, but 1.06 finds normal factors of the same numbers.

The test case "64*259^n+1", 1000000<=n<=1500000, Pmax=1e8

[CODE] factors algebraic remaining Total
srsieve 1.06 326,989 166,667 6,345 500,001
srsieve 1.11 367,809 125,001 7,191 500,001
srsieve 1.12 285,322 208,334 6,345 500,001

newpgen 2.82 ? ? 7,191
[/CODE]

Newpgen can only output the factors it finds above p=1M. Between 1M and 100M it finds 2,768 factors matching srsieve 1.11 while 1.06 and 1.12 finds 2,159 factors in that range. I do not know if it finds algebraic factors, it is not outputting them at least.[/QUOTE]

newpgen knows nothing about algebraic factorizations. The algebraic factors found by srsieve are found before any sieving is done. I'm guessing that the difference between 2768 and 2159 is that the other 609 terms were removed due to algebraic factorizations. That can be easily verified by looking at the remaining n by newpgen that are not in srsieve's output and finding them in the alg_xx.log file.

[QUOTE=ATH;478177]Very nice, thanks.
[/QUOTE]
Nice test case, how about the running time? Are we talking seconds, or centuries? Does it worth upgrading, for us old salts still using the old 1.06? (you know, if it works, do not fix it...)

The test was too short really, so I tried with sieving up to 10^9 instead without outputting the factors found to file or screen:

srsieve 1.06: 108.8 sec
srsieve 1.12: 109.6 sec

But 1.12 finds more algebraic factors. In this sequence 1.06 finds the same amount of normal factors to even it out but I do not know if this is always the case?

So, the new one is useful only in the case when algebraic factors are larger than the sieve limit. Which may be or may be not the case, according with what you are sieving. Good to know. Thanks for running the test.

[QUOTE=LaurV;478200]Nice test case, how about the running time? Are we talking seconds, or centuries? Does it worth upgrading, for us old salts still using the old 1.06? (you know, if it works, do not fix it...)[/QUOTE]

After all I put back to 1.06: because it works and nobody else found error in time this version is used ( and it used for years)
1.12 if nice one: but I dont like different number of candidates left. Ok, maybe is same way with 1.06 but we dont have anything to compare with.
So I stick with 1.06.
Last word: we talk about srsieve 1.06
Using of srfile is different thing since it correct bug I found ( sequence has not data, but header is still created)

[QUOTE=pepi37;478219]but I dont like different number of candidates left.[/QUOTE]

What is that supposed to mean? If 1.1.2 removes algebraic factors that 1.0.6 cannot find, I see no reason to stick with 1.0.6.

[QUOTE=rogue;478229]What is that supposed to mean? If 1.1.2 removes algebraic factors that 1.0.6 cannot find, I see no reason to stick with 1.0.6.[/QUOTE]
With all respect for you, as person and programmer , you released few times program without proper testing. And I rather stick to 1.0.6 and then do one more pass from Batalov script, then to user 1.1.2 and watch logs and find is any error or not.

[QUOTE=LaurV;478213]So, the new one is useful only in the case when algebraic factors are larger than the sieve limit. Which may be or may be not the case, according with what you are sieving. Good to know. Thanks for running the test.[/QUOTE]

The algebraic factors are definitely not found by normal factoring because the smallest one is: 4*259^333335+1. It just happens that all the numbers with algebraic factors also have small "normal" factors, but I do not know if that is always the case.

Aaaa.. oohhh, I just now realized what is happening... :blush:

I am fairly certain that if a number splits into two algebraic factors then it has twice the probability of each prime being a factor in a lot of cases. This will depend on the form of algebraic factor in the case of k^2*2^(2n)-1 = (k*2^n-1)*(k*2^n+1) both factors will obviously be different modulo p.
In the case of k^3*2^(3n)-1=(k*2^n - 1) (k^2*2^(2n) + k*2^n + 1) it is less obvious to me that that is necessarily the case. I suspect some primes will be like that but not all. In fact I have proven that it is not [url]http://factordb.com/index.php?query=%28k*2%5En+-+1%29%2513+%2B+%28%28k%5E2*2%5E%282n%29+%2B+k*2%5En+%2B+1%29+%2513%29&use=k&k=1&n=1&VP=on&VC=on&EV=on&OD=on&PR=on&FF=on&PRP=on&CF=on&U=on&C=on&perpage=20&format=1[/url]

It looks like it needs to be a difference of squares split.

Rogue , can you fix , or make srfile to work. I was preparing new set of sieve files, and somewhere srsieve found alg factors, and somewhere found some but not all ( Batalov script found more) So I try to remove those "extra" alg factors, but srfile dont remove it from sieve files.
Example

command

srfile t16_b470_k32.npg -k factors.txt -g

Rest is in attachment

first factor found by batalov script is

3333333333333333333333 | 32*470*^100545+1

and that candidate is at 23 position at sieve file but it is not removed ( none "batalovs factor is removed)
So it looks like trick with 3333333333333333333333 | doesnot work anymore.
Can you fix this?
Thanks

[QUOTE=pepi37;485319]Rogue , can you fix , or make srfile to work. I was preparing new set of sieve files, and somewhere srsieve found alg factors, and somewhere found some but not all ( Batalov script found more) So I try to remove those "extra" alg factors, but srfile dont remove it from sieve files.
Example

command

srfile t16_b470_k32.npg -k factors.txt -g

Rest is in attachment

first factor found by batalov script is

3333333333333333333333 | 32*470*^100545+1

and that candidate is at 23 position at sieve file but it is not removed ( none "batalovs factor is removed)
So it looks like trick with 3333333333333333333333 | doesnot work anymore.
Can you fix this?
Thanks[/QUOTE]

I'll look at why srsieve doesn't find it, but off the top of my head the issue is that the format of the candidate for which the factor was found is invalid. It has an extra *.

[QUOTE=rogue;485344]I'll look at why srsieve doesn't find it, but off the top of my head the issue is that the format of the candidate for which the factor was found is invalid. It has an extra *.[/QUOTE]

Yes, now I sow that extra one. I will find why that extra * appear. both was learning something with this issue.
Thanks Rogue

[QUOTE=pepi37;485319]Rogue , can you fix , or make srfile to work. I was preparing new set of sieve files, and somewhere srsieve found alg factors, and somewhere found some but not all ( Batalov script found more) So I try to remove those "extra" alg factors, but srfile dont remove it from sieve files.
Example

command

srfile t16_b470_k32.npg -k factors.txt -g

Rest is in attachment

first factor found by batalov script is

3333333333333333333333 | 32*470*^100545+1

and that candidate is at 23 position at sieve file but it is not removed ( none "batalovs factor is removed)
So it looks like trick with 3333333333333333333333 | doesnot work anymore.
Can you fix this?
Thanks[/QUOTE]

I'll have to take a look at see what algebraic form this factor has. Note that the factor is divisible by 3, thus the candidate is divisible by 3 and thus the candidate would be removed via sieving immediately.

[QUOTE=rogue;485443]I'll have to take a look at see what algebraic form this factor has. Note that the factor is divisible by 3, thus the candidate is divisible by 3 and thus the candidate would be removed via sieving immediately.[/QUOTE]

It's a fifth power plus one so the algebraic factor is: [k^(1/5)]*470^(n/5)+1

The fact that it has a factor of 3 is inconsequential. It should be removed in the algebraic factor process. Many forms of this nature will not have such a small factor.

[QUOTE=gd_barnes;485562]It's a fifth power plus one so the algebraic factor is: [k^(1/5)]*470^(n/5)+1

The fact that it has a factor of 3 is inconsequential. It should be removed in the algebraic factor process. Many forms of this nature will not have such a small factor.[/QUOTE]

Hnmm. I wonder how that one was missed. I'll look into it.

It has been pointed out to me that srsieve incorrectly removes all terms for 1296*268^n-1. I have tracked down the problem, but before I post the next version of the code, I would like to know if there are any other outstanding issues with the algebraic factor code in srsieve.

The issue I mentioned above is fixed. When the issue occurs it removes all terms, so if sieving commenced with remaining terms, then the issue was not triggered.

Hi.
Can sr1sieve read a file with 10 million of candidates (10,000,000 rows) ?
Thank you very much
Giovanni

[QUOTE=calimero22;496048]Hi.
Can sr1sieve read a file with 10 million of candidates (10,000,000 rows) ?
Thank you very much
Giovanni[/QUOTE]

Yes

Thank you!!
Giovanni

The time has come for me to port srsieve into my mtsieve framework. It will be called srsieve2, not to be confused with sr2sieve. I've already started the process and am slowing working thru the bugs. Here are some of the changes you will see in srsieve2:
[list][*]it will be multi-threaded out of the box, thanks to the framework[*]it will report a factor removal rate out of the box, thanks to the framework[*]it will not support newpgen or srsieve formats, but will support ABCD and ABC formats[*]srfile will not be mirgrated as srsieve2 will handle all file conversions if necessary along with removal of factors and sequences[*]various switches for srsieve will not be supported including -r -s -S -m -B -H -F -L -M -g -G -w -a -c -C -d -y -z- Z -A -v -q. Some of these exist in one form or another in srsieve2[*]you can input sequences to srsieve2 with -s. This can reference a file or if you have multiple sequences use -s for each distinct sequence[*]it will support -P up to 2^62 without needing a recompile[*]sr2sieve will eventually be merged into srsieve2. I don't know if sr1sieve can be merged without hurting its performance[*]when sr2sieve is merged, I hope to support the building of Legendre tables for k up to 2^62[*]there is a possibility that srsieve2 will be slower than srsieve, but I'm doing everything I can to prevent that from happening. Right now it appears that srsieve2 is slightly faster, but the testing I have done is very limited[*]AVX support is possible, but I don't know if there will be a speed boost if I implement it[*]I discovered that srsieve misses some algebraic factorizations. The srsieve code is fixed. I hope to post an updated exe within a couple of days. srsieve2 uses the same logic so that will find those same algebraic factorizations.[/list]
Please let me know if there is a "must have" feature that exists in srsieve that is not slated for support in srsieve2 and I will consider your request.

Also, if you want a feature in srsieve2 that does not exist in srsieve or the mtsieve framework, please let me know and I will consider it.

Finally, I will be needing some help me test this when it is done. It isn't so much about validating factors, but comparing the speed and outputs between srsieve and srsieve2.

[QUOTE=rogue;506983][LIST][*]it will not support newpgen or srsieve formats, but will support ABCD and ABC formats[/QUOTE][/LIST]Maybe is just me, or just I doing work with npg files, but if it is not too much trouble leave it.
Everything else is ok.
I dont know why you have such "negative pick" on npg files. it may be obsolete , but in the end it is just one switch you need .
Thanks

Some suggestions:

Support for multiple values of c in k*b^n+c would potentially be useful along with optional removal of all values of c when a factor is found(for finding twins etc).

Support for starting a sieve for a range of k rather than having to specify all the sequences manually.

Support for outputting files split by k or subranges of n to save on manual editing of potentially large files. Often testing is done in very different sections to sieving.

[QUOTE=pepi37;507001][/LIST]Maybe is just me, or just I doing work with npg files, but if it is not too much trouble leave it.
Everything else is ok.
I dont know why you have such "negative pick" on npg files. it may be obsolete , but in the end it is just one switch you need .
Thanks[/QUOTE]

For this type of sieve, newpgen provides no value. There is no reason for me to write additional code to support it. Some of my other sieves support newpgen mainly so that I could quickly compare that those programs generated the correct results.

[QUOTE=henryzz;507018]Some suggestions:

Support for multiple values of c in k*b^n+c would potentially be useful along with optional removal of all values of c when a factor is found(for finding twins etc).

Support for starting a sieve for a range of k rather than having to specify all the sequences manually.

Support for outputting files split by k or subranges of n to save on manual editing of potentially large files. Often testing is done in very different sections to sieving.[/QUOTE]

I believe that srsieve supports multiple values for c (assuming varying k and n as well). If you want a sieve for fixed k, b, and n, but variable c, then there is fkbcsieve. If you are searching for twins with fixed k, b, and n, there is twinsieve. Both of these are part of mtsieve.

By "range of k", is this for a large range of n or a small range of n? I'm not saying that I won't do it, but there might be other sieves that will do as you ask. BTW, you can use Excel with NotePad++ to generate a file of sequences to sieve.

I understand the desire for "split by k" or "split by n", but if you truly want to split the work across multiple clients, then PRPNet might be an option. I will consider the request in either case.

[QUOTE=rogue;507028]For this type of sieve, newpgen provides no value. There is no reason for me to write additional code to support it. Some of my other sieves support newpgen mainly so that I could quickly compare that those programs generated the correct results.[/QUOTE]


Are we talking about this srsieve?

I , and many others use it to make initial sieve file



srsieve --newpgen -v -n 3 -N 400000 -P 20000000 "k*b^n+1"

[QUOTE=rogue;507029]I believe that srsieve supports multiple values for c (assuming varying k and n as well). If you want a sieve for fixed k, b, and n, but variable c, then there is fkbcsieve. If you are searching for twins with fixed k, b, and n, there is twinsieve. Both of these are part of mtsieve.[/quote]
And almost all these programs are limited to twins. It is a fairly easy extension which could be useful. Many people would value being able to sieve at least k*2^n+-1 simultaneously due to it being faster than separately.

[QUOTE]By "range of k", is this for a large range of n or a small range of n? I'm not saying that I won't do it, but there might be other sieves that will do as you ask. BTW, you can use Excel with NotePad++ to generate a file of sequences to sieve.[/QUOTE]
A fairly large range of both k and n. It is possible to work around this one but why not make it easy?

[quote]
I understand the desire for "split by k" or "split by n", but if you truly want to split the work across multiple clients, then PRPNet might be an option. I will consider the request in either case.[/QUOTE]

Often people don't want to load the whole file into PRPNet at once. Often the larger n will want further sieving.

[QUOTE=pepi37;507030]Are we talking about this srsieve?

I , and many others use it to make initial sieve file

srsieve --newpgen -v -n 3 -N 400000 -P 20000000 "k*b^n+1"[/QUOTE]

Initial sieve file for what program?

One of the many challenges in the code is to understand how the various compiler switches for this programs are intended to be used. There will be some big challenges to merging sr2sieve into this code because of those switches, but I need to integrate all of the filtering logic from srsieve first.

[QUOTE=rogue;507034]Initial sieve file for what program?[/QUOTE]


sr1sieve for example?

[QUOTE=pepi37;507038]sr1sieve for example?[/QUOTE]

I see. I have considered modifying sr1sieve to support ABCD or ABC format for the input file format. I'm not opposed to doing that.

In any case it will likely be weeks before srsieve2 is released.

It isn't as if srfile will suddenly break

[QUOTE=henryzz;507042]It isn't as if srfile will suddenly break[/QUOTE]

Of course not, but since I don't know if or when sr1sieve will be merged, I would prefer that users not have to rely on srfile or other means of converting files before using sr1sieve. How many times have one of us tried to use sr1sieve and forgot to convert the input file?

What's really annoying is that the default file format output by srsieve isn't compatible with either sr1sieve or sr2sieve. Problems like that will be solved when srsieve2 is ready for public use.

srsieve 1.1.4
 

Here is srsieve 1.1.4. There two changes.

The first is that I added an output line to srsieve that tells how much CPU processor time was used. I will be using this to compare the speed of srsieve to srsieve2.

The second is the change to find more algebraic factorizations:[list][*]k = x^f as x*b^(n/f)-1 is a factor of k*b^n-1 where k = x^f and n%f = 0[*]k = x^f as x*b^(n/f)+1 is a factor of k*b^n+1 where k = x^f and n%f = 0 and f is odd[/list]
I know that a previous iteration of the code found these, but in an attempt (by me) to reduce the amount of code, these got lost in the mix.

I am considering changing the default file format of srsieve to ABCD. sr2sieve supports that format out of the box and sr1sieve will in its next version. Does anyone see a need for the default file format of srsieve to remain unchanged?

As promised, here is the latest sr1sieve. Input files can be in the NPG, ABC, or ABCD format. There is also a -F switch that allows one to specify the format of the output file (if one is to be created). -FA (default) is ABCD format. -FD is ABC format. -FN is NPG format.

Adding more formats to sr1sieve is a very welcome change.
I would probably recommend the ABC rather than ABCD format as a default as it is easier to manipulate files in ABC. Not many people need the space saving nature of the ABCD format. Also I think that less programs support ABCD format(does prpnet?)

[QUOTE=henryzz;507094]Adding more formats to sr1sieve is a very welcome change.
I would probably recommend the ABC rather than ABCD format as a default as it is easier to manipulate files in ABC. Not many people need the space saving nature of the ABCD format. Also I think that less programs support ABCD format(does prpnet?)[/QUOTE]

I see your point, especially with sr1sieve outputting as ABCD. Since it only supports a single sequence, the output file shouldn't be unmanageable.

[QUOTE=rogue;507091]As promised, here is the latest sr1sieve. Input files can be in the NPG, ABC, or ABCD format. There is also a -F switch that allows one to specify the format of the output file (if one is to be created). -FA (default) is ABCD format. -FD is ABC format. -FN is NPG format.[/QUOTE]
Multithread mode on windows working?

[QUOTE=pepi37;507097]Multithread mode on windows working?[/QUOTE]

I haven't tried. If it doesn't work let me know, but I can't make any promises on fixing it.

[QUOTE=rogue;507101]I haven't tried. If it doesn't work let me know, but I can't make any promises on fixing it.[/QUOTE]




unknown option -- t and then stop
So it doesnot work on Windows
On Linux was working ( so I assume that will work also and now) :)

[QUOTE=pepi37;507104]unknown option -- t and then stop
So it doesnot work on Windows
On Linux was working ( so I assume that will work also and now) :)[/QUOTE]

I see that now. I cannot fix this on Windows because Windows handles threading in a different way than *nix bases OSes. Making the changes to supporting multi-threading on Windows is not a small task. It would require a near rewrite of the code. It would probably be easier to port to the mtsieve framework.

[QUOTE=pepi37;507104]unknown option -- t and then stop
So it doesnot work on Windows
On Linux was working ( so I assume that will work also and now) :)[/QUOTE]

Do you have Windows 10? If so, enable the Linux Subsystem for Windows. It's a nearly fully functioning Ubuntu shell built in. The only major limitation I've found is that can't handle GUI-based programs at all. You have to set up your Windows-based X server, and I haven't attempted that yet.

Using it, I've had no issue with multithreaded sr1sieve.

[QUOTE=wombatman;507134]Do you have Windows 10? If so, enable the Linux Subsystem for Windows. It's a nearly fully functioning Ubuntu shell built in. The only major limitation I've found is that can't handle GUI-based programs at all. You have to set up your Windows-based X server, and I haven't attempted that yet.

Using it, I've had no issue with multithreaded sr1sieve.[/QUOTE]


I have two linux machine so it is not problem using MT sr1sieve in case I need it.

No, I have Win 7, but , maybe Rogue will port it to mtsieve and we have brand new , shiny MT sr1sieve :)

[QUOTE=pepi37;507147]I have two linux machine so it is not problem using MT sr1sieve in case I need it.

No, I have Win 7, but , maybe Rogue will port it to mtsieve and we have brand new , shiny MT sr1sieve :)[/QUOTE]

That could be months away.

[QUOTE=rogue;507164]That could be months away.[/QUOTE]
Until that : Linux exist :)

It seems that sr2sieve crashes with k > 2^32 even with -x. Can anyone reproduce? I'm asking because I wonder if the bug is in mingw gcc or in sr2sieve itself. I haven't changed sr2sieve in the area where it is terminating. I'm also asking because I want to see if sr2sieve will work with large k so that I can avoid implementing two versions of code as srsieve and sr2sieve use different logic and I would prefer to only implement one of them (the faster one) in srsieve2.

Update: This is not a gcc bug. It is a bug in the asm code used by sr2sieve. It makes an assumption about available memory so if there are many sequences (in my case I have over 6000 of them), it segfaults.

Here is a fixed version of sr2sieve. The big change is the one to avoid the segfault. I did this by only doing 32 powmods at a time instead of all of them (all as in all sequences). I also added text to the error message suggesting to run with -x when it is unable to build the Legendre table.

In a side by side comparison sr2sieve with -x is about 50% faster than srsieve. That is with over 6000 sequences in the input file.

I would appreciate if some users of srsieve/srsieve compare the speeds of sr2sieve -x with srsieve to see if that holds true. If it does, then srsieve2 will implement the bsgs logic from sr2sieve.

[QUOTE=rogue;507179]Here is a fixed version of sr2sieve. The big change is the one to avoid the segfault. I did this by only doing 32 powmods at a time instead of all of them (all as in all sequences). I also added text to the error message suggesting to run with -x when it is unable to build the Legendre table.

In a side by side comparison sr2sieve with -x is about 50% faster than srsieve. That is with over 6000 sequences in the input file.

I would appreciate if some users of srsieve/srsieve compare the speeds of sr2sieve -x with srsieve to see if that holds true. If it does, then srsieve2 will implement the bsgs logic from sr2sieve.[/QUOTE]

I spoke too soon, even with -x sr2sieve can't do some values of k. I'll see if I can address that as I don't want two implementations of bsgs.

[QUOTE=rogue;507181]I spoke too soon, even with -x sr2sieve can't do some values of k. I'll see if I can address that as I don't want two implementations of bsgs.[/QUOTE]


This is part of my script and it look like this

sr2 -q -i sr_%n%.abcd -P 1000000000



log file



01/30/19 20:42:26 sr2sieve 1.9.4 started: 1000015 <= n <= 2999995, 20000000 <= p <= 1000000000
but there is no output file and no factors

I just realized that sr2sieve doesn't verify that k < 2^32, so that is problem.

The attached version will not allow you to use sr2sieve if k >= 2^32. It is annoying that sr2sieve did not do such validation previously.

I will look into addressing this.

[QUOTE=rogue;507199]I just realized that sr2sieve doesn't verify that k < 2^32, so that is problem.

The attached version will not allow you to use sr2sieve if k >= 2^32. It is annoying that sr2sieve did not do such validation previously.

I will look into addressing this.[/QUOTE]


Still not working