Generalizing algebraic factors on Riesel bases

[gd_barnes]

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" , 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]

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]

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:

For any prime factor f and any base b, I conjecture that for the following set of conditions:
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

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.

Listing for all factors up to 1035:

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

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


Thanks,
Gary

[gd_barnes]

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]

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!

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]

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]

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

[gd_barnes]

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

[gd_barnes]

I have added:

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]

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

[gd_barnes]

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