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

2020-07-12, 18:35   #892
sweety439

Nov 2016

2×7×132 Posts

Quote:
 Originally Posted by Uncwilly Why do you insist on quoting whole posts all the time?
Why shouldn't I do this?

2020-07-12, 18:42   #893
sweety439

Nov 2016

2×7×132 Posts

Quote:
 Originally Posted by sweety439 Also these cases: S15 k=343: since 343 is cube, all n divisible by 3 have algebra factors, and we only want to know whether it has a covering set of primes for all n not divisible by 3, if so, then this k makes a full covering set with algebraic factors and be excluded from the conjecture; if not, then this k does not make a full covering set with algebraic factors and be included from the conjecture. n-value : factors 1 : 31 · 83 2 : 2^2 · 11 · 877 4 : 2^2 · 809 · 2683 5 : 811 · 160583 7 : 11^2 · 242168453 11 : 31 · 101 · 25357 · 18684739 13 : 397 · 1281101 · 656261029 17 : 11 · 27479311 · 55900668804553 29 : 53 · 197741 · 209188613429183386499227445981 35 : 1337724923 · 18667724069720862256321575167267431 43 : 20943991 · 3055827403675875709696160949928034201885723243 61 : 23539 · (a 61-digit prime) and it does not appear to be any covering set of primes, so there must be a prime at some point. S61 k=324: since 324 is of the form 4*m^4, all n divisible by 4 have algebra factors, and we only want to know whether it has a covering set of primes for all n not divisible by 4, if so, then this k makes a full covering set with algebraic factors and be excluded from the conjecture; if not, then this k does not make a full covering set with algebraic factors and be included from the conjecture. n-value : factors 1 : 59 · 67 2 : 41 · 5881 3 : 13 · 1131413 5 : 5 · 7 · 1563709723 6 : 13 · 256809250661 7 : 23 · 1255679 · 7051433 13 : 191 · 7860337 · 27268229 · 256289843 14 : 1540873 · 1698953 · 244480646906833 31 : 1888149043321 · 441337391577139 · 1721840403480692512106884569347 34 : 10601 · 174221 · (a 54-digit prime) and it does not appear to be any covering set of primes, so there must be a prime at some point.
However, there are cases that cannot have prime:

R88 k=400:

since 400 is square, all even n have algebra factors, and we only want to know whether it has a covering set of primes for all odd n, if so, then this k makes a full covering set with algebraic factors and be excluded from the conjecture; if not, then this k does not make a full covering set with algebraic factors and be included from the conjecture.

n-value : factors
1 : 3 · 3911
3 : 7 · 101 · 128519
5 : 13 · 12119 · 4466239
7 : 3^3 · 3799333 · 53118563
9 : 7 · 167 · 36096764394509957
11 : 13 · 25136498347515268468841
13 : 3 · 1877 · 1156907 · 5976181 · 64998862429
15 : 7^2 · 239 · 6079 · 483551 · 1173283 · 485185295929
17 : 13 · 7417 · 1573883316708285469700513209073

and there is covering set {3, 7, 13} (n == 1 mod 6: factor of 3; n == 3 mod 6: factor of 7; n == 5 mod 6: factor of 13), thus for R88, k=400 proven composite by partial algebra factors.

R10 k=343:

since 343 is cube, all n divisible by 3 have algebra factors, and we only want to know whether it has a covering set of primes for all n not divisible by 3, if so, then this k makes a full covering set with algebraic factors and be excluded from the conjecture; if not, then this k does not make a full covering set with algebraic factors and be included from the conjecture.

n-value : factors
1 : 3 · 127
2 : 37 · 103
4 : 3 · 127037
5 : 17 · 37 · 73 · 83
7 : 3^2 · 42345679
8 : 37 · 113 · 613 · 1487
10 : 3 · 2399 · 52954163
11 : 37 · 103003003003

and there is covering set {3, 37} (n == 1 mod 3: factor of 3; n == 2 mod 3: factor of 37), thus for R10, k=343 proven composite by partial algebra factors.

Last fiddled with by sweety439 on 2020-07-12 at 19:13

 2020-07-12, 18:49 #894 sweety439     Nov 2016 236610 Posts For Sierpinski side: Case gcd(k+1,b-1) = 1 is the same as the Sierpinski side of CRUS Case k = 1, b even is the same as finding the smallest generalized Fermat prime base b Case k = 1, b odd is the same as finding the smallest half generalized Fermat prime base b Case k = b-2 is the same as finding the smallest prime of the form ((b-2)*b^n+1)/(b-1) For Riesel side: Case gcd(k-1,b-1) = 1 is the same as the Riesel side of CRUS Case k = 1 is the same as finding the smallest generalized repunit prime base b Case k = b-1 is the same as finding the smallest Williams prime base b (primes of the form (b-1)*b^n-1, some authors use base (b-1) instead of base b for (b-1)*b^n-1, but I don't think this is good, since the "base" should be the number with an exponent)
2020-07-12, 18:50   #895
sweety439

Nov 2016

44768 Posts

Quote:
 Originally Posted by sweety439 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
Since a large probable prime n can be proven to be prime if and only if at least one of n-1 and n+1 can be trivially written into a product.

Thus, if n is large, a probable prime (k*b^n+-1)/gcd(k+-1,b-1) can be proven to be prime if and only if gcd(k+-1,b-1) = 1.

2020-07-12, 18:54   #896
sweety439

Nov 2016

44768 Posts

Quote:
 Originally Posted by sweety439 Since a large probable prime n can be proven to be prime if and only if at least one of n-1 and n+1 can be trivially written into a product. Thus, if n is large, a probable prime (k*b^n+-1)/gcd(k+-1,b-1) can be proven to be prime if and only if gcd(k+-1,b-1) = 1.
If gcd(k+-1,b-1) = 1 (+ for Sierpinski, - for Riesel), then this is completely the same as the Sierpinski/Riesel problem in CRUS for this (k,b) combo, these Sierpinski/Riesel problems just extend the Sierpinski/Riesel problems in CRUS to the k such that gcd(k+-1,b-1) (+ for Sierpinski, - for Riesel) is not 1, since in this case, k*b^n+-1 is always divisible by gcd(k+-1,b-1), thus we should take out this factor and find the smallest n such that (k*b^n+-1)/gcd(k+-1,b-1) is prime.

2020-07-12, 18:55   #897
carpetpool

"Sam"
Nov 2016

22×79 Posts

Quote:
 Originally Posted by sweety439 Since a large probable prime n can be proven to be prime if and only if at least one of n-1 and n+1 can be trivially written into a product. Thus, if n is large, a probable prime (k*b^n+-1)/gcd(k+-1,b-1) can be proven to be prime if and only if gcd(k+-1,b-1) = 1.
That is incorrect. What if we only know 12.5% of the factorization of n^2-1 (CHG proof), and thus, niether n+1, nor n-1 has to be trivially written as a product ? What if the factors found were non-trivial?

Also, have you considered where

n^2+n+1, n^2-n+1, n^2+1,

are partially factored?

I could keep going you know.

Last fiddled with by carpetpool on 2020-07-12 at 19:05

2020-07-12, 19:14   #898
sweety439

Nov 2016

44768 Posts

Quote:
 Originally Posted by sweety439 If k is square and k == -1 mod p and b == -1 mod p for some odd prime p (this situation only exists for p == 1 mod 4) or k is square and k == 2^(r-1)+1 mod 2^r and b == 2^(r-1)+1 mod 2^r for some r >= 2 (this situation only exists for r >= 4) Then this k proven composite by partial algebraic factors (has algebraic factors (difference of two squares) for even n and divisible by a prime (p or 2, respectively) for odd n)
Thus, the second case (i.e. has algebra factors for even n and divisible by 2 for odd n) only exists for bases b == 1 mod 8

2020-07-12, 19:16   #899
sweety439

Nov 2016

2×7×132 Posts

Quote:
 Originally Posted by sweety439 Thus, the second case (i.e. has algebra factors for even n and divisible by 2 for odd n) only exists for bases b == 1 mod 8
and such k's are square numbers k such that the highest power of 2 dividing (k-1) is the same as the highest power of 2 dividing (b-1)

(not consider the case that b is square, since any square k for any square Riesel base b proven composite by full algebra factors)

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

 2020-07-12, 19:47 #900 sweety439     Nov 2016 2·7·132 Posts These bases b have many small Sierpinski/Riesel numbers k: Code: base Sierpinski numbers k Riesel numbers k 5 == 7, 11 mod 24 == 13, 17 mod 24 8 == 47, 79, 83, 181 mod 195 == 14, 112, 116, 148 mod 195 9 == 31, 39 mod 80 == 41, 49 mod 80 11 == 5, 7 mod 12 == 5, 7 mod 12 12 == 521, 597, 1143, 1509 mod 1885 == 376, 742, 1288, 1364 mod 1885 13 == 15, 27 mod 56 == 29, 41 mod 56 14 == 4, 11 mod 15 == 4, 11 mod 15 16 == 38, 194, 524, 608, 647, 719 mod 819 == 100, 172, 211, 295, 625, 781 mod 819 17 == 31, 47 mod 96 == 49, 65 mod 96 18 == 398, 512, 571, 989 mod 1235 == 246, 664, 723, 837 mod 1235 19 == 9, 11 mod 20 == 9, 11 mod 20 20 == 8, 13 mod 21 == 8, 13 mod 21 21 == 23, 43 mod 88 == 45, 65 mod 88 23 == 5, 7 mod 12 == 5, 7 mod 12 25 == 79, 103 mod 208 == 105, 129 mod 208 27 == 13, 15 mod 28 == 13, 15 mod 28 29 == 4, 11 mod 15 or == 7, 11 mod 24 or == 19, 31 mod 40 == 4, 11 mod 15 or == 13, 17 mod 24 or == 9, 21 mod 40 32 == 10, 23 mod 33 == 10, 23 mod 33 Last fiddled with by sweety439 on 2020-07-12 at 19:50
2020-07-12, 20:26   #901
Uncwilly
6809 > 6502

"""""""""""""""""""
Aug 2003
101×103 Posts

210528 Posts

There are several reasons not to quote an entire post:
1. It causes the reader to have to scroll past the giant block to get to fresh content.
- - If someone is trying to catch up on a thread it slows them down.
2. It does not help the reader know particularly what bit of the quote that is being referred to.
3. If it is the immediately preceding post, a quote is not needed at all.
4. If someone is searching the forum to find something, excessive quoting produces extra hits that are chaff and not wheat.
5. It slows forum operation and adds extra unneeded volume to the database.

An example of an effective quote:

Quote:
 Originally Posted by In a previous post Here are 5 examples of dogs I like
I also now like these 2 more:
Dog 6
Dog 7

Notice that the limited quote tells the user what is being referred to. The concept of Hypertext was that things could be referenced without placing an entire work in the document. This is done all of the time in documents, a small bit is quoted and there are footnotes to the original work.

Last fiddled with by Uncwilly on 2020-07-12 at 20:27

 2020-07-14, 11:51 #902 sweety439     Nov 2016 44768 Posts Found an error of S81: (34*81^734+1)/gcd(34+1,81-1) is prime Double checking S81....

 Similar Threads Thread Thread Starter Forum Replies Last Post sweety439 sweety439 11 2020-09-23 01:42 sweety439 sweety439 20 2020-07-03 17:22 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 23:00.

Wed Oct 28 23:00:56 UTC 2020 up 48 days, 20:11, 1 user, load averages: 1.80, 1.73, 1.83