 mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Conjectures 'R Us (https://www.mersenneforum.org/forumdisplay.php?f=81)
-   -   Generalizing algebraic factors on Riesel bases (https://www.mersenneforum.org/showthread.php?t=11143)

 gd_barnes 2008-12-17 08:16

Generalizing algebraic factors on Riesel bases

This will be an important bit of information for any of you that work on new Riesel bases in the future:

After extensive analysis of the patterns of algebraic factors on Riesel bases < 100, I have concluded the following:

For all bases b where b == (4 mod 5), algebraic factors on even-n combine with a numeric factor on odd-n in the following scenario:

k=m^2 and m==(2 or 3 mod 5)

Factors to:

for even-n, let n=2q:
(m*b^q-1)*(m*b^q+1)
-and-
odd-n: factor of 5

In "English terms" :smile:, this states that for any base that leaves a remainder of 4 after dividing by 5 (i.e. 4, 9, 14, 19, etc.), any k that is a perfect square of an integer that leaves a remainder of 2 or 3 after dividing by 5, i.e. k=2^2, 3^2, 7^2, 8^2, etc. can be eliminated from testing on these bases because it is proven composite for all n.

Now that I've updated the pages to include many Riesel bases up to 125, you can see that k=4 and 9 are eliminated on several bases as a result of the above scenario.

You won't see these algebraic factors listed on the web pages for ALL bases that leave a remainder of 4 after dividing by 5. I only list the algebraic factors that are applicable for the base in question and generalized to the greatest extent. For instance on bases 4 and 9, ALL k's that are perfect squares can be removed so I show that instead. Bases that are b==(14 mod 15) have a conjecture of k=4 so algebraic factors that make a full covering set are not applicable.

Having this generalization available would have made Riesel base 24 much easier to begin with. With two different "kinds" of algebraic factors on that base as shown on the pages, having this first "kind" above readily available would have made the second kind (k=6*m^2) much easier to come up with.

A less common but equally important generalization will follow in the next post.

Gary

 gd_barnes 2008-12-17 08:29

For all bases b where b == (36 mod 37), algebraic factors on even-n combine with a numeric factor on odd-n in the following scenario:

k=m^2 and m==(6 or 31 mod 37)

Factors to:

for even-n, let n=2q:
(m*b^q-1)*(m*b^q+1)
-and-
odd-n: factor of 37

Therefore, the above applies to bases 36, 73, 110, etc. for k=6^2, 31^2, 43^2, 68^2, etc.

This pattern of factors was brought to light by me initially missing these factors for the form 36*73^n-1 and erroneously assuming that k=36 was still remaining after initial testing.

Gary

 gd_barnes 2008-12-17 09:24

Not only can we generalize the algebraic factors for a specific factor across bases, I believe we can generalize all prime "numeric" factors across all Riesel bases that combine with algebraic factors to make full covering sets.

Analysis:

1. See the above 2 posts for factors of 5 and 37.

2. The same type of scenario occurs for a factor of 13 on base 12 (and likely bases 25, 38, 51, etc. if they are applicable), a factor of 29 on base 28 (and likely bases 57, 86, 115, etc. if they are applicable), a factor of 17 on base 33 (and likely bases 50, 67, 84, etc. if they are applicable), and a factor of 61 on base 60 (and likely bases 121, 182, 243, etc. if they are applicable). See the web pages.

Therefore I propose the following conjecture to the math community for Riesel bases:

In addition to having full algebraic factors on k's and bases that are perfect squares, there are k's that are perfect squares for many bases that are NOT perfect squares that have a numeric prime factor (f) that combines with algebraic factors to make a full covering set in the following scenarios:

[B]For any prime factor f and any base b, I conjecture that for the following set of conditions:[/B]
b==(f-1 mod f)
-and-
f==(1 mod 4)
-and-
k=m^2
-and-
m==(x or y mod f)
-and-
x+y = f
-and-
x and y are unique for each f
-and-
0 < x, y < f

[B]That f is a prime factor on odd-n and algebraic factors of the form [m*b^(n/2)-1]*[m*b^(n/2)+1] are present on even-n and that these combine to make a full covering set for the form k*b^n-1.[/B]

Listing for all factors up to 1035:
[code]
bases b== factor x & y-values
4mod5 5 2, 3 (2, 3, & 5 are Fibonacci numbers)
12mod13 13 5, 8 (5, 8, & 13 are Fibonacci numbers)
16mod17 17 4, 13
28mod29 29 12, 17
36mod37 37 6, 31
40mod41 41 9, 32
52mod53 53 23, 30
60mod61 61 11, 50
72mod73 73 27, 46
88mod89 89 34, 55 (34, 55, & 89 are Fibonacci numbers)
96mod97 97 22, 75
100mod101 101 10, 91
108mod109 109 33, 76
112mod113 113 15, 98
136mod137 137 37, 100
148mod149 149 44, 105
156mod157 157 28, 129
172mod173 173 80, 93
180mod181 181 19, 162
192mod193 193 81, 112
196mod197 197 14, 183
228mod229 229 107, 122
232mod233 233 89, 144 (89, 144, & 233 are Fibonacci numbers)
240mod241 241 64, 177
256mod257 257 16, 241
268mod269 269 82, 187
276mod277 277 60, 217
280mod281 281 53, 228
292mod293 293 138, 155
312mod313 313 25, 288
316mod317 317 114, 203
336mod337 337 148, 189
348mod349 349 136, 213
352mod353 353 42, 311
372mod373 373 104, 269
388mod389 389 115, 274
396mod397 397 63, 334
400mod401 401 20, 381
408mod409 409 143, 266
420mod421 421 29, 392
432mod433 433 179, 254
448mod449 449 67, 382
456mod457 457 109, 348
460mod461 461 48, 413
508mod509 509 208, 301
520mod521 521 235, 286
540mod541 541 52, 489
556mod557 557 118, 439
568mod569 569 86, 483
576mod577 577 24, 553
592mod593 593 77, 516
600mod601 601 125, 476
612mod613 613 35, 578
616mod617 617 194, 423
640mod641 641 154, 487
652mod653 653 149, 504
660mod661 661 106, 555
672mod673 673 58, 615
676mod677 677 26, 651
700mod701 701 135, 566
708mod709 709 96, 613
732mod733 733 353, 380
756mod757 757 87, 670
760mod761 761 39, 722
768mod769 769 62, 707
772mod773 773 317, 456
796mod797 797 215, 582
808mod809 809 318, 491
820mod821 821 295, 526
828mod829 829 246, 583
852mod853 853 333, 520
856mod857 857 207, 650
876mod877 877 151, 726
880mod881 881 387, 494
928mod929 929 324, 605
936mod937 937 196, 741
940mod941 941 97, 844
952mod953 953 442, 511
976mod977 977 252, 725
996mod997 997 161, 836
1008mod1009 1009 469, 540
1012mod1013 1013 45, 968
1020mod1021 1021 374, 647
1032mod1033 1033 355, 678
[/code]

This is exciting stuff for making the Riesel conjectures easier in the future. :smile:

Thanks,
Gary

 gd_barnes 2008-12-19 20:19

After looking at some testing done by Chris, I've added another factor to the above pattern that holds with what has already been outlined in this thread as follows:

For all bases b where b == (52 mod 53), algebraic factors on even-n combine with a numeric factor on odd-n in the following scenario:

k=m^2 and m==(23 or 30 mod 53)

Factors to:

for even-n, let n=2q:
(m*b^q-1)*(m*b^q+1)
-and-
odd-n: factor of 53

Therefore, the above applies to bases 52, 105, 158, etc. for k=23^2, 30^2, 76^2, 83^2, etc.

Gary

 gd_barnes 2009-10-27 03:10

After looking at some testing done by Willem, I've added another factor to the above pattern that holds with what has already been outlined in this thread as follows:

For all bases b where b == (40 mod 41), algebraic factors on even-n combine with a numeric factor on odd-n in the following scenario:

k=m^2 and m==(9 or 32 mod 41)

Factors to:

for even-n, let n=2q:
(m*b^q-1)*(m*b^q+1)
-and-
odd-n: factor of 41

Therefore, the above applies to bases 40, 81, 122, etc. for k=9^2, 32^2, 50^2, 73^2, etc.

In the case of Willem's Riesel base 40, this only affected k's that were m==(9 or 114 mod 123), which is a subset of m==(9 or 32 mod 41), because the others came were k==(1 mod 3), which has a trivial factor of 3 and so are not considered.

BTW, Willem correctly recognized such k's and eliminated them from his testing. Nice job Willem! :smile:

Although initially somewhat surprising that the factor of 41 as it applies to eliminating k's as a result of combining with algebraic factors had not been encountered up to this point, it is understandable. For b==(40 mod 41), base 40 has a huge conjecture and had not previously been started, bases 81 and 122 have small conjectures that are < than the smallest possible k that the above applies to, (k=81), base 163 with a conjecture of k=186 cannot have odd k's, which eliminates k=81, the only possible k that the above applies to, and bases 204, 245, 286, etc. have not yet been tested.

I would guess that we are down to the final few factors that haven't been found yet that this scenario applies to for bases <= 1024. The conjectures, as a general rule, get smaller as the bases get larger and so it becomes increasingly unlikely for any additional (mainly larger) factors to have an affect, generally because the smallest applicable k-value comes in above the conjecture or is eliminated by trivial factors.

Gary

 gd_barnes 2009-12-01 09:28

I've added factor 113 for bases b==112 mod 113 to the above list after looking at some testing done by Serge that was verified by Willem.

 gd_barnes 2010-03-20 03:17

I've added factor 137 for bases b==136 mod 137 to the above list after looking at base 821.

 gd_barnes 2010-03-25 04:40

I've added factor 97 for bases b==96 mod 97 to the above list after looking at base 96.

 gd_barnes 2010-03-26 08:46

Factor 109 for bases b==108 mod 109 to the above list after looking at base 108.
Factor 193 for bases b==192 mod 193 to the above list after looking at base 192.

 gd_barnes 2010-03-28 07:38

I've added factor 101 for bases b==100 mod 101 to the above list after looking at base 504.

 gd_barnes 2010-04-02 02:42

AT LAST...

I have been able to generalize these "old" style algebraic factors, not only across all bases, but across all factors.

I now see the pattern of why some prime factors can combine with partial algebraic factors to make a full covering set and some cannot. Although I do not have a formal proof, after testing all prime factors up to 100 and observing several already-found factors > 100, I'm fairly confident in the finding. Here it is:

For a numeric factor (f) on odd n to combine with algebraic factors on even n to make a full covering set, f must be:

f==(1 mod 4)

That's it! Now we can easily add all applicable prime factors and bases to the generallized post here.

What I have not been able to determine is the x and y values in the generalization. The main example for a factor of 5 is:

k=m^2 and m==2 or 3 mod 5.

Where the "2" and "3" are the x and y values and the "5" is the factor f. I do know that x + y must equal f but that's all that I can determine at this point.

Having tested this for all factors < 100, I can now see that 2 more must be added for factors of 73 and 89. I have now formally added them.

Technically, all factors up to 1024 need to be added to the post to cover every possible situation on the project. But it becomes increasingly rare for them to have an impact as f gets higher because as it gets higher, x and y are higher, the bases are higher, and the conjectures become lower. It will be a fairly straight forward task for me to add them up to a factor of 250. So I'll do that this evening.

This effort is a precursor to updating the new bases script to take into account algebraic factors. These "old style" algebraic factorizations will be added first because they appear to cover nearly 90% of all k's that can be eliminated by partial algebraic factors (along with adding the more simple full algebraic factorization where k and base are perfect squares). Later on, the "new" style that will be added where factor f occurs on even n and algebraic factors occur on odd n, which has a somewhat increased level of complexity to narrow down. Both of these only occur on Riesel bases. And then finally, there would be cubes and higher powers, which may never be formally added to the script other than checking for both the k and the base being a perfect cube or higher power. The complexity of cubes and higher powers (if both k and base are not a perfect power) increases exponentially over squares and is far more rare. The time is likely not worth the effort.

Gary

All times are UTC. The time now is 09:36.