A Sierpinski/Riesel-like problem

[sweety439]

Originally Posted by Uncwilly

Why do you insist on quoting whole posts all the time?

Why shouldn't I do this?

[sweety439]

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.

[sweety439]

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)

[sweety439]

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)

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.

[sweety439]

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.

[carpetpool]

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.

[sweety439]

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

[sweety439]

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)

[sweety439]

These bases b have many small Sierpinski/Riesel numbers k:

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

[Uncwilly]

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:

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.

[sweety439]

Found an error of S81: (34*81^734+1)/gcd(34+1,81-1) is prime

Double checking S81....