[quote=Batalov;207886]Intuitively, nobody expects that effect, so I didn't mean it as any criticism.

That would be a very nice addition. Time savings! Plus, if you will be implementing this, then you may want to chisel the new smaller base from the [I]k[/I] and add it to the exponent.

If you (internally to PF, before GWnum) completely factor the [I]k[/I] and [I]b[/I], pfgw could also immediately catch and report some algebraic factorizations; here's a test case: suppose I submit [FONT=Fixedsys]26*234^149885-1[/FONT][FONT=Verdana] (or amidst the ABC file) then[/FONT]

[FONT=Courier New]k= 26=2*13[/FONT]
[FONT=Courier New]b=234=2*3^2*13[/FONT]
[FONT=Courier New]n is odd[/FONT]

...and the program could immediately report "is composite by algebraic" and optionally report the factors (or the smaller one): all a^2-b^2 and a^odd+-b^odd could be caught (it is not always trivial to catch all of them by eye, right?).

I am sure a lot of users could be very happy with that addition.

-Serge


[SIZE=1][COLOR=green]P.S. I thought of a small obvious caveat in this algebra (not relevant for the Sierp/Riesel forms): [/COLOR][/SIZE]
[SIZE=1][COLOR=green]If a-b=1 (which is rare but we don't want any induced bugs), then no use for the minus form. (Example 6^2-5^2.)[/COLOR][/SIZE][/quote]


That would be an outstanding addition to PFGW but...here is where I really think it is needed: In sr(x)sieve! Sr(x)sieve will tell you that certain k's have algebraic factors but all that means is that there are even n's remaining in the file on k's that are perfect squares. (I think it may do higher powers now but am not sure. I'm also not sure if it can deduce such a situation on 26*234^n-1 where the odd n's have algebraic factors.)

I guess my question about sr(x)sieve is: If it can tell me that there are some n's that have algebraic factors, why not just remove them automatically instead of forcing one to manually remove them?

Serge, wouldn't you agree that such k's and/or n-values should be removed by a sieving program instead of being found by a primality searching program?


Gary

Reserving Riesel Bases 654 and 694 as new to n=25K.

[QUOTE=Batalov;207886]Intuitively, nobody expects that effect, so I didn't mean it as any criticism.

That would be a very nice addition. Time savings! Plus, if you will be implementing this, then you may want to chisel the new smaller base from the [I]k[/I] and add it to the exponent.

If you (internally to PF, before GWnum) completely factor the [I]k[/I] and [I]b[/I], pfgw could also immediately catch and report some algebraic factorizations; here's a test case: suppose I submit [FONT=Fixedsys]26*234^149885-1[/FONT][FONT=Verdana] (or amidst the ABC file) then[/FONT]

[FONT=Courier New]k= 26=2*13[/FONT]
[FONT=Courier New]b=234=2*3^2*13[/FONT]
[FONT=Courier New]n is odd[/FONT]

...and the program could immediately report "is composite by algebraic" and optionally report the factors (or the smaller one): all a^2-b^2 and a^odd+-b^odd could be caught (it is not always trivial to catch all of them by eye, right?).

I am sure a lot of users could be very happy with that addition.[/QUOTE]

I agree with Gary. Sieving should be used to remove algebraic factorizations. You can find some here, [url]http://www.leyland.vispa.com/numth/factorization/cullen_woodall/algebraic.txt[/url] and those are just for generalized Cullens and Woodalls. There are undoubtably more than listed on that page.

Riesel 635
 

Riesel Base 635
Conjectured k = 52
Covering Set = 3, 53
Trivial Factors k == 1 mod 2(2) and k == 1 mod 317(317)

Found Primes: 23k's File attached

Remaining k's: Tested to n=25K
6*635^n-1
38*635^n-1

Base Released

Riesel 688
 

Riesel Base 688
Conjectured k = 105
Covering Set = 13, 53
Trivial Factors k == 1 mod 3(3) and k == 1 mod 229(229)

Found Primes: 68 k's File attached

Remaining k's: Tested to n=25K
9*688^n-1

Trivial Factor Eliminations: 34k's

Base Released

Riesel 741
 

Riesel Base 741
Conjectured k = 160
Covering Set = 7, 53
Trivial Factors k == 1 mod 2(2) and k == 1 mod 5 and k == 1 mod 37(37)

Found Primes: 60k's File attached

Remaining k's: Tested to n=25K
64*741^n-1

Trivial Factor Eliminations: 18k's

Base Released

[quote=Batalov;208043]R288:
[I]b[/I]=288 = [B]2[/B][sup][B]5[/B][/sup]*3[sup]2[/sup]
[I]k[/I]=18 = [B]2[/B]*3[sup]2[/sup]
[I]k[/I]=392 = [B]2[/B][sup][B]3[/B][/sup]*7[sup]2[/sup]
For both [I]k[/I] and even [I]n[/I], trivial factors, for odd [I]n[/I], we have differences of squares.
[/quote]
Similar elimination for R864, with k=6 and 96.
[I]b[/I]=864 = 2[sup]5[/sup]*3[sup]3[/sup]
[I]k[/I]=6 = 2*3
[I]k[/I]=96 = 2[sup]5[/sup]*3 (all odd powers; with n odd they pair up nicely)

Riesel Base 1007
 

2*1007^8-1
4*1007^1-1
6*1007^2-1

With conjectured k=8, this conjecture is proven.

Riesel Base 993
 

2*993^2-1
4*993^3-1
6*993^18-1

With conjectured k=8, this conjecture is proven.

Riesel Base 857
 

2*857^2-1
4*857^195-1
8*857^22-1

With a conjecture of k=10, k=6 remains. I'll continue on it

Serge has uncovered a whole slew of "new" algebraic factors and there appears to be a clear pattern. Sometime after I get back from my trip, I'll have to add it to the "generalizing algebraic factors for Riesel bases" thread.

Although not all of the time, frequently on bases where k's are eliminated by partial algebraic factors on even n with odd n having a factor of x, there are other k's that are eliminated by partial algebraic factors on ODD n with EVEN n having a factor of x.

Serge, you've already uncovered at least 3 bases with this situation. If you have time and haven't done it already and would like to go through all of the Riesel bases looking for just that situation, that would help us greatly. Thanks! :-)

In the mean time, I'll mention this again: If after sieving to a nominal depth, you find a k that has < ~0.5% of all n-values remaining, there is a very good chance that it has partial algebraic factors that will help eliminate it. Frequently they will be < 0.1%. If you come up with that situation and cannot see algebraic factors, post the situation somewhere here and one of us will take a look at it.

Algebraic factors are far more numerous than I would have imagined when I started the project. Alas, the project was originally intended for bases <= 32 and powers-of-2 bases <= 1024 so I would not have thought to check for these exception situations.


Gary