mersenneforum.org A Sierpinski/Riesel-like problem
 Register FAQ Search Today's Posts Mark Forums Read

 2020-07-04, 16:15 #859 sweety439     Nov 2016 2,141 Posts These Sierpinski bases (up to 1024) cannot be proven with current knowledge and technology, since they have either GFN (for even bases) or half GFN (odd bases) remain: (half GFN is much worse, since for these (probable) primes, the divisor gcd(k+-1,b-1) is not 1 (it is 2), and when n is large (for all numbers of the form (k*b^n+-1)/gcd(k+-1,b-1) whose gcd(k+-1,b-1) is not 1) the known primality tests for such a number are too inefficient to run. In this case one must resort to a probable primality test such as a Miller–Rabin test, unless a divisor of the number can be found) Code: b k 2 65536 6 1296 10 100 12 12 15 225 18 18 22 22 31 1 32 4 36 1296 37 37 38 1 40 1600 42 42 50 1 52 52 55 1 58 58 60 60 62 1 63 1 66 4356 67 1 68 1 70 70 72 72 77 1 78 78 83 1 86 1 89 1 91 1 92 1 93 93 97 1 98 1 99 1 104 1 107 1 108 108 109 1 117 117 122 1 123 1 124 15376 126 15876 127 1 128 16 135 1 136 136 137 1 138 138 143 1 144 1 147 1 148 148 149 1 151 1 155 1 161 1 166 166 168 1 178 178 179 1 180 1049760000 182 1 183 1 186 1 189 1 192 192 193 193 196 196 197 1 200 1 202 1 207 1 210 1944810000 211 1 212 1 214 1 215 1 216 36 217 217 218 1 222 222 223 1 225 225 226 226 227 1 232 232 233 1 235 1 241 1 243 27 244 1 246 1 247 1 249 1 252 1 255 1 257 1 258 1 262 262 263 1 265 1 268 268 269 1 273 273 280 78400 281 1 282 282 283 1 285 1 286 1 287 1 291 1 293 1 294 1 298 1 302 1 303 1 304 1 307 1 308 1 310 310 311 1 316 316 319 1 322 1 324 1 327 1 336 336 338 1 343 49 344 1 346 346 347 1 351 1 354 1 355 1 356 1 357 357 358 358 359 1 361 361 362 1 366 366 367 1 368 1 369 1 372 372 377 1 380 1 381 381 383 1 385 385 387 1 388 388 389 1 390 1 393 393 394 1 397 397 398 1 401 1 402 1 404 1 407 1 408 408 410 1 411 1 413 1 416 1 417 1 418 418 420 176400 422 1 423 1 424 1 437 1 438 438 439 1 443 1 446 1 447 1 450 1 454 1 457 457 458 1 460 460 462 462 465 465 467 1 468 1 469 1 473 1 475 1 480 1 481 481 482 1 483 1 484 1 486 486 489 1 493 1 495 1 497 1 500 1 509 1 511 1 512 2, 4, 16 514 1 515 1 518 1 522 522 524 1 528 1 530 1 533 1 534 1 538 1 541 541 546 546 547 1 549 1 552 1 555 1 558 1 563 1 564 1 570 324900 572 1 574 1 578 1 580 1 586 586 590 1 591 1 593 1 597 1 600 129600000000 601 1 602 1 603 1 604 1 606 606 608 1 611 1 612 612 615 1 618 618 619 1 620 1 621 621 622 1 626 1 627 1 629 1 630 630 632 1 633 633 635 1 637 1 638 1 645 1 647 1 648 1 650 1 651 1 652 652 653 1 655 1 658 658 659 1 660 660 662 1 663 1 666 1 667 1 668 1 670 1 671 1 672 672 675 1 678 1 679 1 683 1 684 1 687 1 691 1 692 1 694 1 698 1 706 1 707 1 708 708 709 1 712 1 717 717 720 1 722 1 724 1 731 1 734 1 735 1 737 1 741 1 743 1 744 1 746 1 749 1 752 1 753 1 754 1 755 1 756 756 759 1 762 1 765 765 766 1 767 1 770 1 771 1 773 1 775 1 777 777 783 1 785 1 787 1 792 1 793 793 794 1 796 796 797 1 801 801 802 1 806 1 807 1 809 1 812 1 813 1 814 1 817 817 818 1 820 820 822 822 823 1 825 1 836 1 838 838 840 1 842 1 844 1 848 1 849 1 851 1 852 852 853 1 854 1 858 858 865 865 867 1 868 1 870 1 872 1 873 1 878 1 880 880 882 882 886 886 887 1 888 1 889 1 893 1 896 1 897 897 899 1 902 1 903 1 904 1 907 1 908 1 910 828100 911 1 915 1 922 1 923 1 924 1 926 1 927 1 932 1 933 933 937 1 938 1 939 1 941 1 942 1 943 1 944 1 945 1 947 1 948 1 953 1 954 1 958 1 961 1 964 1 966 870780120336 967 1 968 1 970 970 974 1 975 1 977 1 978 1 980 1 983 1 987 1 988 1 993 1 994 1 998 1 999 1 1000 10 1002 1 1003 1 1005 1005 1006 1 1008 1008 1009 1 1012 1012 1014 1 1016 1 1017 1017 1020 1020 1024 4, 16 Last fiddled with by sweety439 on 2020-07-10 at 06:28
2020-07-05, 16:11   #860
sweety439

Nov 2016

2,141 Posts

We don't know the conjectures yet on bases 66, 120, 156, 180, 210, 240, 280, 330, 358, 420, 456, 462, 546, ... and Sierp 190, 540 and Riesel 276, 486. They are definitely k > 1M. They're just too unmanageable with today's computing power and knowledge. That said, if people are open to the idea, I might suggest searching some of those up to k=100K at some point to get future generations of prime searchers started on those huge efforts. To me, the main thing is collecting data for us and for future generations to analyze.

There are upper bounds of these conjectures: (the lower bounds of these conjectures are all 1000001, since all k<=1M are checked)

S66: 21314443 (if not this number, then must be == 4 mod 5 or == 12 mod 13)
S120: 374876369 (if not this number, then must be == 6 mod 7 or == 16 mod 17)
S156: 18406311208 (if not this number, then must be == 4 mod 5 or == 30 mod 31)
S180: 1679679 (if not this number, then must be == 178 mod 179)
S190: 3146151 (if not this number, then must be == 2 mod 3 or == 6 mod 7)
S210: 147840103 (if not this number, then must be == 10 mod 11 or == 18 mod 19)
S240: 1722187 (if not this number, then must be == 238 mod 239)
S280: 82035074042274 (if not this number, then must be == 2 mod 3 or == 30 mod 31)
S330: 16636723 (if not this number, then must be == 6 mod 7 or == 46 mod 47)
S358: 27478218 (if not this number, then must be == 2 mod 3 or == 6 mod 7 or == 16 mod 17)
S420: 2288555 (if not this number, then must be == 418 mod 419)
S456: 14836963 (if not this number, then must be == 4 mod 5 or == 6 mod 7 or == 12 mod 13)
S462: 6880642 (if not this number, then must be == 460 mod 461)
S540: 1091739 (if not this number, then must be == 6 mod 7 or == 10 mod 11)
S546: 45119296 (if not this number, then must be == 4 mod 5 or == 108 mod 109)

R66: 101954772 (if not this number, then must be == 1 mod 5 or == 1 mod 13)
R120: 166616308 (if not this number, then must be == 1 mod 7 or == 1 mod 17)
R156: 2113322677 (if not this number, then must be == 1 mod 5 or == 1 mod 31)
R180: 7674582 (if not this number, then must be == 1 mod 179)
R210: 80176412 (if not this number, then must be == 1 mod 11 or == 1 mod 19)
R240: 2952972 (if not this number, then must be == 1 mod 239)
R276: 1552307 (if not this number, then must be == 1 mod 5 or == 1 mod 11)
R280: 513613045571841 (if not this number, then must be == 1 mod 3 or == 1 mod 31)
R330: 16527822 (if not this number, then must be == 1 mod 7 or == 1 mod 47)
R358: 27606383 (if not this number, then must be == 1 mod 3 or == 1 mod 7 or == 1 mod 17)
R420: 6548233 (if not this number, then must be == 1 mod 419)
R456: 76303920 (if not this number, then must be == 1 mod 5 or == 1 mod 7 or == 1 mod 13)
R462: 2924772 (if not this number, then must be == 1 mod 461)
R486: 1525283 (if not this number, then must be == 1 mod 5 or == 1 mod 97)
Attached Files
 Conjectured smallest Sierpinski number.txt (8.3 KB, 0 views) Conjectured smallest Riesel number.txt (8.3 KB, 0 views)

Last fiddled with by sweety439 on 2020-07-10 at 16:26

 2020-07-07, 08:10 #861 sweety439     Nov 2016 214110 Posts Any Riesel k that is a perfect square will always be lower weight than average because the even-n have algebraic factors.
 2020-07-07, 08:19 #862 sweety439     Nov 2016 2,141 Posts A Sierpinski form (k*b^n+1)/gcd(k+1,b-1) has algebra factors if and only if k*b^n is perfect odd power A070265 or of the form 4*m^4 A101046 A Riesel form (k*b^n-1)/gcd(k-1,b-1) has algebra factors if and only if k*b^n is perfect power A001597 Situations in which srsieve will make that statement: 1. For any k on any Riesel base that is a perfect square, when sieving, all n-values that are divisible by 2 can be manually removed. 2. For any k on any Sierpinski base that is of the form 4*m^4, all n-values that are divisible by 4 can be manually removed. 3. For any k on any (Riesel or Sierpinski) base that is a perfect cube, all n-values that are divisible by 3 can be manually removed. 4. (etc.) for k's that are perfect 5th powers, 7th powers, 11th powers, or any prime power where p=power, any n's divisible by p can be manually removed. Taken to an extreme, for k=2048, which is 2^11, you could manually eliminate all n-values that are divisible by 11. A special case is k=1: * For Riesel base, all n-values that are not prime can be manually removed. * For Sierpinski base, all n-values that are not power of 2 can be manually removed. To put the above in a different way: You can only eliminate the k if manually removing all of these n-values leaves you with no n's remaining, which would have been the case had you attempted to sieve 900*67^n-1. Had you sieved it, you would have ended up with a sieve file with very few EVEN n-values remaining and zero ODD n-values remaining. Once you manually removed the n's divisible by 2, you would have had nothing left. That means that the k-value can be removed from conjecture testing because it has partial algebraic factors that combine with a numeric factor to make a full "covering set" of factors. Analysis on both k=125 and 729 shows that they should remain because there is no factor or factors that eliminate the n's that the algebraic factors do not. When sieving, as per the above, on k=125, you can manually remove all n-values divisible by 3. On k=729, that is one of the few that you can eliminate n-values that are divisible by 2 -or- that are divisible by 3. In effect, you're only left with n-values that are n==(1 or 5 mod 6). If you manually remove those n's, you'll stop getting that message from srsieve. k=729 would normally be extremely low weight except for the fact that it is divisible by 3, which eliminates any possibility of a factor of 3 for all n-values. That increases the weight to something like a k that is a perfect square. A k-value that would be extremely low-weight is one that is a perfect square and cube but is not divisible by 2 or 3. I think the lowest one of that nature would be 5^6=15625, which would only be an issue on very few bases. Last fiddled with by sweety439 on 2020-07-07 at 08:26
 2020-07-07, 08:43 #863 sweety439     Nov 2016 2,141 Posts Exclusions: k's that are multiples of the base where (k+-1)/gcd(k+-1,b-1) (+ for Sierp, - for Riesel) is not prime. I'll give some examples for S22: k=44, 154, 220, 242, 264, 374, 440 would be excluded from testing because 45/3, 155, 221, 243/3, 265, 375/3, 441/21 are not primes. k=22, 66, 88, 110, 132, 176, 198, 286, 308, 330, 352, 396, 418 would be INcluded in testing because 23, 67, 89, 111/3, 133/7, 177/3, 199, 287/7, 309/3, 331, 353, 397, 419 are primes. The exclusions for multiples of the base are the same on all bases. Check for (k-1)/gcd(k+-1,b-1) being prime on the Riesel side and check for (k+1)/gcd(k+-1,b-1) being prime on the Sierp side. If it's prime, include it; if it's not prime, exclude it. Last fiddled with by sweety439 on 2020-07-07 at 08:45
 2020-07-07, 09:01 #864 sweety439     Nov 2016 214110 Posts So far, there is only two Riesel k and base <= 128 where algebraic factors on even-n combine with a covering set of MORE than one factor on odd-n to eliminate a k. That is 1369*30^n-1 and (400*88^n-1)/3
 2020-07-07, 09:24 #865 sweety439     Nov 2016 2,141 Posts (101*73^2146-1)/4 is (probable) prime!!! R73 has only k=79 remain, reserve it to n=10K
2020-07-07, 09:32   #866
sweety439

Nov 2016

2,141 Posts

Quote:
 Originally Posted by sweety439 (101*73^2146-1)/4 is (probable) prime!!! R73 has only k=79 remain, reserve it to n=10K

 2020-07-07, 18:04 #867 sweety439     Nov 2016 85D16 Posts Checking whether a k-value makes a full covering set with algebraic factors not always very easy. The way I do it is to look for patterns in the factors of the various n-values for specific k-values. If there are algebraic factors, it's most common for them to be in a pattern of f*(f+2), i.e.: 11*13 179*181 etc. In other cases there may be a consistent steady increase in the differences of their factors, which is especially tricky to find but indicates the existence of algebraic factors. e.g. for the case R15 k=47 n-value : factors 1 : 2^5 · 11 2 : 17 · 311 3 : 2^4 · 4957 4 : 31 · 38377 6 : 11 · 43 · 565919 8 : 199 · 1627 · 186019 10 : 17 · 61 · 13067776451 12 : 37 · 82406457849451 20 : 15061 · 236863181 · 2190492030407 Analysis: For n=1 & 3 (and all odd n), all values are divisible by 2 so we only consider even n's. For n=4, the two prime factors does not close. For n=6 & 10, multiplying the 2 lower prime factors together does not come close to the higher prime factor so little chance of algebraic factors. For n=12, the large lowest prime factor that bears no relation to the other prime factor means that there is unlikely to be a pattern to the occurrences of large prime factors so there must be a prime at some point. R33 k=257: n-value : factors 1 : 5 · 53 2 : 2 · 4373 3 : 397 · 727 4 : 2^2 · 2381107 5 : 5^3 · 7 · 359207 7 : 11027 · 31040117 15 : 13337 · 706661 · 51076716238627 19 : 38231 · 14932493857679888742000509 For n=15 & 19 same explanation as R15 k=47 R36 k=1555: n-value : factors 1 : 11 · 727 2 : 31 · 37 · 251 3 : 67 · 154691 4 : 37 · 127 · 271 · 293 7 : 4943 · 3521755879 9 : 59 · 382386761790283 For n=7 & 9 same explanation as R15 k=47 The prime factors for n=12, n=15, and n=7 respectively make it clear to me that these k-values should all yield primes at some point so you are correct to include them as remaining. The higher-math folks may be able to chime in and answer why there are an abnormally large # of k's that are perfect squares that end up remaining even though they don't have known algebraic factors for most bases. IMHO, it's because there ARE algebraic factors for a subset of the universe of n-values on them but not for all of the n-values. Hence they are frequently lower weight than the other k's but NOT zero weight and so should eventually yield a prime.
2020-07-07, 18:08   #868
sweety439

Nov 2016

2,141 Posts

Quote:
 Originally Posted by sweety439 Checking whether a k-value makes a full covering set with algebraic factors not always very easy. The way I do it is to look for patterns in the factors of the various n-values for specific k-values. If there are algebraic factors, it's most common for them to be in a pattern of f*(f+2), i.e.: 11*13 179*181 etc. In other cases there may be a consistent steady increase in the differences of their factors, which is especially tricky to find but indicates the existence of algebraic factors. e.g. for the case R15 k=47 n-value : factors 1 : 2^5 · 11 2 : 17 · 311 3 : 2^4 · 4957 4 : 31 · 38377 6 : 11 · 43 · 565919 8 : 199 · 1627 · 186019 10 : 17 · 61 · 13067776451 12 : 37 · 82406457849451 20 : 15061 · 236863181 · 2190492030407 Analysis: For n=1 & 3 (and all odd n), all values are divisible by 2 so we only consider even n's. For n=4, the two prime factors does not close. For n=6 & 10, multiplying the 2 lower prime factors together does not come close to the higher prime factor so little chance of algebraic factors. For n=12, the large lowest prime factor that bears no relation to the other prime factor means that there is unlikely to be a pattern to the occurrences of large prime factors so there must be a prime at some point. R33 k=257: n-value : factors 1 : 5 · 53 2 : 2 · 4373 3 : 397 · 727 4 : 2^2 · 2381107 5 : 5^3 · 7 · 359207 7 : 11027 · 31040117 15 : 13337 · 706661 · 51076716238627 19 : 38231 · 14932493857679888742000509 For n=15 & 19 same explanation as R15 k=47 R36 k=1555: n-value : factors 1 : 11 · 727 2 : 31 · 37 · 251 3 : 67 · 154691 4 : 37 · 127 · 271 · 293 7 : 4943 · 3521755879 9 : 59 · 382386761790283 For n=7 & 9 same explanation as R15 k=47 The prime factors for n=12, n=15, and n=7 respectively make it clear to me that these k-values should all yield primes at some point so you are correct to include them as remaining. The higher-math folks may be able to chime in and answer why there are an abnormally large # of k's that are perfect squares that end up remaining even though they don't have known algebraic factors for most bases. IMHO, it's because there ARE algebraic factors for a subset of the universe of n-values on them but not for all of the n-values. Hence they are frequently lower weight than the other k's but NOT zero weight and so should eventually yield a prime.
In fact, (k*b^n+1)/gcd(k+1,b-1) has algebra factors if and only if k*b^n is either perfect odd power or of the form 4*m^4, and (k*b^n-1)/gcd(k-1,b-1) has algebra factors if and only if k*b^n is perfect power, thus forms like (257*33^n-1)/32 cannot have algebra factors, since there is no n such that 257*33^n is perfect power (after all, the exponent of the prime 257 in the prime factorization of 257*33^n is 1 for all n, but any prime factor in the prime factorization of a perfect power cannot have exponent 1).

Last fiddled with by sweety439 on 2020-07-07 at 18:09

2020-07-07, 19:27   #869
sweety439

Nov 2016

2,141 Posts

Quote:
 Originally Posted by sweety439 (101*73^2146-1)/4 is (probable) prime!!! R73 has only k=79 remain, reserve it to n=10K
(79*73^9339-1)/6 is (probable) prime!!!

R73 is proven!!!

 Similar Threads Thread Thread Starter Forum Replies Last Post sweety439 sweety439 20 2020-07-03 17:22 sweety439 sweety439 10 2018-12-14 21:59 sweety439 sweety439 12 2017-12-01 21:56 robert44444uk Conjectures 'R Us 139 2007-12-17 05:17 rogue Conjectures 'R Us 11 2007-12-17 05:08

All times are UTC. The time now is 19:01.

Wed Aug 5 19:01:16 UTC 2020 up 19 days, 14:48, 3 users, load averages: 2.27, 1.91, 1.80