 mersenneforum.org Generalizing algebraic factors on Riesel bases
 Register FAQ Search Today's Posts Mark Forums Read  2008-12-17, 08:16 #1 gd_barnes   May 2007 Kansas; USA 2·52·7·29 Posts 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" , 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 Last fiddled with by gd_barnes on 2008-12-17 at 08:31   2008-12-17, 08:29 #2 gd_barnes   May 2007 Kansas; USA 2·52·7·29 Posts 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 Last fiddled with by gd_barnes on 2008-12-17 at 08:37   2008-12-17, 09:24 #3 gd_barnes   May 2007 Kansas; USA 2·52·7·29 Posts 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: 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 This is exciting stuff for making the Riesel conjectures easier in the future. Thanks, Gary Last fiddled with by gd_barnes on 2010-10-08 at 17:09 Reason: add all factors up to 1024   2008-12-19, 20:19 #4 gd_barnes   May 2007 Kansas; USA 2·52·7·29 Posts 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   2009-10-27, 03:10 #5 gd_barnes   May 2007 Kansas; USA 27A616 Posts 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   2009-12-01, 09:28 #6 gd_barnes   May 2007 Kansas; USA 2·52·7·29 Posts 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.   2010-03-20, 03:17 #7 gd_barnes   May 2007 Kansas; USA 2×52×7×29 Posts I've added factor 137 for bases b==136 mod 137 to the above list after looking at base 821.   2010-03-25, 04:40 #8 gd_barnes   May 2007 Kansas; USA 2×52×7×29 Posts I've added factor 97 for bases b==96 mod 97 to the above list after looking at base 96.   2010-03-26, 08:46 #9 gd_barnes   May 2007 Kansas; USA 2×52×7×29 Posts 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. Last fiddled with by gd_barnes on 2010-03-26 at 09:01   2010-03-28, 07:38 #10 gd_barnes   May 2007 Kansas; USA 2×52×7×29 Posts I've added factor 101 for bases b==100 mod 101 to the above list after looking at base 504.   2010-04-02, 02:42 #11 gd_barnes   May 2007 Kansas; USA 2·52·7·29 Posts 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 Last fiddled with by gd_barnes on 2010-04-02 at 03:13   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post pepi37 Conjectures 'R Us 95 2017-07-04 13:37 R. Gerbicz Conjectures 'R Us 22 2009-12-29 20:21 Siemelink Conjectures 'R Us 105 2009-09-04 06:40 henryzz ElevenSmooth 13 2007-12-18 09:12 robert44444uk Conjectures 'R Us 139 2007-12-17 05:17

All times are UTC. The time now is 02:40.

Wed Jul 8 02:40:22 UTC 2020 up 105 days, 13 mins, 0 users, load averages: 1.57, 2.12, 2.26 