A Prime Game:
Write down a multidigit prime number (i.e. a prime number > 10), and I can always strike out 0 or more digits to get a prime in this list:
{11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 227, 251, 257, 277, 281, 349, 409, 449, 499, 521, 557, 577, 587, 727, 757, 787, 821, 827, 857, 877, 881, 887, 991, 2087, 2221, 5051, 5081, 5501, 5581, 5801, 5851, 6469, 6949, 8501, 9001, 9049, 9221, 9551, 9649, 9851, 9949, 20021, 20201, 50207, 60649, 80051, 666649, 946669, 5200007, 22000001, 60000049, 66000049, 66600049, 80555551, 555555555551, 5000000000000000000000000000027}
e.g.
- Write down the prime 149 → I can delete the digit 4, to get the prime 19
- Write down the prime 439 → I can delete the digit 9, to get the prime 43
- Write down the prime 857 → I can delete zero digits, to get the prime 857
- Write down the prime 2081 → I can delete the digit 0, to get the prime 281
- Write down the largest known double Mersenne prime 170141183460469231731687303715884105727 (2127−1) → I can delete all digits except the third-leftmost 1 and the second-rightmost 3, to get the prime 13
- Write down the largest known Fermat prime 65537 → I can delete the 6 and the 3, to get the prime 557 (also I can choose to delete the 6 and two 5's, to get the prime 37) (also I can choose to delete two 5's and the 3, to get the prime 67) (also I can choose to delete the 6, one 5, and the 7, to get the prime 53)
- Write down the famous repunit prime 1111111111111111111 (with 19 1's) → I can delete 17 1's, to get the prime 11
- Write down the prime 1000000000000000000000000000000000000000000000000000000000007 (which is the next prime after 1060) → I can delete all 0's, to get the prime 17
- Write down the prime 95801 → I can delete the 9, to get the prime 5801
- Write down the prime 946969 → I can delete the first 9 and two 6's, to get the prime 499
- Write down the prime 90000000581 → I can delete five 0's, the 5, and the 8, to get the prime 9001
- Write down the prime 8555555555555555555551 → I can delete the 8 and nine 5's, to get the prime 555555555551
Now we extend this prime game to bases other than 10.
The minimal elements (https://en.wikipedia.org/wiki/Minimal_element) (https://mathworld.wolfram.com/MaximalElement.html for maximal element, the dual of minimal element, unfortunely there is no article "minimal element" in mathworld, a minimal element of a set (https://en.wikipedia.org/wiki/Set_(mathematics), https://mathworld.wolfram.com/Set.html) under a partial ordering binary relation (https://en.wikipedia.org/wiki/Binary_relation, https://mathworld.wolfram.com/BinaryRelation.html) is a maximal element of the same set under its converse relation (https://en.wikipedia.org/wiki/Converse_relation), a converse relation of a partial ordering relation must also be a partial ordering relation) of the prime numbers (https://en.wikipedia.org/wiki/Prime_number, https://primes.utm.edu/glossary/xpage/Prime.html, https://www.rieselprime.de/ziki/Prime, https://mathworld.wolfram.com/PrimeNumber.html, https://www.numbersaplenty.com/set/prime_number/, http://www.numericana.com/answer/primes.htm#definition, https://oeis.org/A000040) which are > b written in the positional numeral system (https://en.wikipedia.org/wiki/Positional_numeral_system) with radix (https://en.wikipedia.org/wiki/Radix, https://primes.utm.edu/glossary/xpage/Radix.html, https://www.rieselprime.de/ziki/Base, https://mathworld.wolfram.com/Radix.html) b, as digit (https://en.wikipedia.org/wiki/Numerical_digit, https://www.rieselprime.de/ziki/Digit, https://mathworld.wolfram.com/Digit.html) strings (https://en.wikipedia.org/wiki/String_(computer_science), https://mathworld.wolfram.com/String.html) under the subsequence (https://en.wikipedia.org/wiki/Subsequence, https://mathworld.wolfram.com/Subsequence.html) ordering (https://en.wikipedia.org/wiki/Partially_ordered_set, https://mathworld.wolfram.com/PartialOrder.html, https://mathworld.wolfram.com/PartiallyOrderedSet.html), for 2 ≤ b ≤ 36 (I stop at base 36 since this base is a maximum base for which it is possible to write the numbers with the symbols 0, 1, 2, ..., 9 and A, B, C, ..., Z, references: http://www.tonymarston.net/php-mysql/converter.html, https://www.dcode.fr/base-36-cipher, http://www.urticator.net/essay/5/567.html, http://www.urticator.net/essay/6/624.html, https://docs.python.org/3/library/functions.html#int, https://reference.wolfram.com/language/ref/BaseForm.html, https://en.wikipedia.org/wiki/Base36, https://web.archive.org/web/20150320103231/https://en.wikipedia.org/wiki/Base_36, https://baseconvert.com/, https://www.calculand.com/unit-converter/zahlen.php?og=Base+2-36&ug=1, also see https://primes.utm.edu/notes/words.html for the English words which are prime numbers when viewed as a number base 36), using A−Z to represent digit values 10 to 35.
"The set of strings ordered by subsequence" is a partially ordered set (https://en.wikipedia.org/wiki/Partially_ordered_set, https://mathworld.wolfram.com/PartialOrder.html, https://mathworld.wolfram.com/PartiallyOrderedSet.html), since this binary relation (https://en.wikipedia.org/wiki/Binary_relation, https://mathworld.wolfram.com/BinaryRelation.html) is reflexive (https://en.wikipedia.org/wiki/Reflexive_relation, https://mathworld.wolfram.com/Reflexive.html), antisymmetric (https://en.wikipedia.org/wiki/Antisymmetric_relation), and transitive (https://en.wikipedia.org/wiki/Transitive_relation), and thus we can draw its Hasse diagram (https://en.wikipedia.org/wiki/Hasse_diagram, https://mathworld.wolfram.com/HasseDiagram.html) and find its greatest element (https://en.wikipedia.org/wiki/Greatest_element), least element (https://en.wikipedia.org/wiki/Least_element), maximal elements (https://en.wikipedia.org/wiki/Maximal_element, https://mathworld.wolfram.com/MaximalElement.html), and minimal elements (https://en.wikipedia.org/wiki/Minimal_element), however, the greatest element and least element may not exist, and for an infinite set (such as the set of the "prime numbers > b" strings in base b (for a given base b ≥ 2), for the proofs for that there are infinitely many primes, see https://en.wikipedia.org/wiki/Euclid%27s_theorem, https://mathworld.wolfram.com/EuclidsTheorems.html, http://www.numericana.com/answer/primes.htm#euclid, https://primes.utm.edu/notes/proofs/infinite/, https://primes.utm.edu/notes/proofs/infinite/euclids.html, https://primes.utm.edu/notes/proofs/infinite/topproof.html, https://primes.utm.edu/notes/proofs/infinite/goldbach.html, https://primes.utm.edu/notes/proofs/infinite/kummers.html, https://primes.utm.edu/notes/proofs/infinite/Saidak.html)), the maximal elements also may not exist, thus we are only interested on finding the minimal elements of these sets, and we define "minimal set" of a set as the set of the minimal elements of this set, under a given partially ordered binary relation (this binary relation is "is a subsequence of" in this article))
By the theorem that there are no infinite (https://en.wikipedia.org/wiki/Infinite_set, https://primes.utm.edu/glossary/xpage/Infinite.html, https://mathworld.wolfram.com/InfiniteSet.html) antichains (https://en.wikipedia.org/wiki/Antichain, https://mathworld.wolfram.com/Antichain.html) (i.e. a subset of a partially ordered set such that any two distinct elements in the subset are incomparable (https://en.wikipedia.org/wiki/Comparability, https://mathworld.wolfram.com/ComparableElements.html)) for the subsequence ordering (i.e. the set of the minimal elements of any set under the subsequence ordering must be finite, even if this set is infinite, such as the set of the "prime numbers > b" strings in base b (for a given base b ≥ 2), for the proofs for that there are infinitely many primes, see https://en.wikipedia.org/wiki/Euclid%27s_theorem, https://mathworld.wolfram.com/EuclidsTheorems.html, http://www.numericana.com/answer/primes.htm#euclid, https://primes.utm.edu/notes/proofs/infinite/, https://primes.utm.edu/notes/proofs/infinite/euclids.html, https://primes.utm.edu/notes/proofs/infinite/topproof.html, https://primes.utm.edu/notes/proofs/infinite/goldbach.html, https://primes.utm.edu/notes/proofs/infinite/kummers.html, https://primes.utm.edu/notes/proofs/infinite/Saidak.html), there must be only finitely such minimal elements in every base b.
Addition (https://en.wikipedia.org/wiki/Addition, https://www.rieselprime.de/ziki/Addition, https://mathworld.wolfram.com/Addition.html) and multiplication (https://en.wikipedia.org/wiki/Multiplication, https://www.rieselprime.de/ziki/Multiplication, https://mathworld.wolfram.com/Multiplication.html) are the basic operations of arithmetic (https://en.wikipedia.org/wiki/Arithmetic, https://www.rieselprime.de/ziki/Arithmetic, https://mathworld.wolfram.com/Arithmetic.html) (which is also the basics of mathematics (https://en.wikipedia.org/wiki/Mathematics, https://www.rieselprime.de/ziki/Mathematics, https://mathworld.wolfram.com/Mathematics.html)). In the addition operation, the identity element (https://en.wikipedia.org/wiki/Identity_element, https://mathworld.wolfram.com/IdentityElement.html) is 0, and all natural numbers > 0 can be written as the sum of many 1’s, and the number 1 cannot be broken up; in the multiplication operation, the identity element is 1, and all natural numbers > 1 can be written as the product of many prime numbers, and the prime numbers cannot be broken up. Also, prime numbers are central in number theory (https://en.wikipedia.org/wiki/Number_theory, https://www.rieselprime.de/ziki/Number_theory, https://mathworld.wolfram.com/NumberTheory.html) because of the fundamental theorem of arithmetic (https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic, https://primes.utm.edu/glossary/xpage/FundamentalTheorem.html, https://mathworld.wolfram.com/FundamentalTheoremofArithmetic.html, http://www.numericana.com/answer/primes.htm#fta): every natural number greater than 1 is either a prime itself or can be factorized (https://en.wikipedia.org/wiki/Integer_factorization, https://www.rieselprime.de/ziki/Factorization, https://mathworld.wolfram.com/PrimeFactorization.html, https://mathworld.wolfram.com/PrimeFactorizationAlgorithms.html, http://www.numericana.com/answer/factoring.htm) as a product of primes that is unique up to (https://en.wikipedia.org/wiki/Up_to) their order. Also, primes are the natural numbers n > 1 such that if n divides (https://en.wikipedia.org/wiki/Divides, https://primes.utm.edu/glossary/xpage/Divides.html, https://primes.utm.edu/glossary/xpage/Divisor.html, https://www.rieselprime.de/ziki/Factor, https://mathworld.wolfram.com/Divides.html, https://mathworld.wolfram.com/Divisor.html, https://mathworld.wolfram.com/Divisible.html, http://www.numericana.com/answer/primes.htm#divisor) x×y (x and y are natural numbers), then n divides either x or y (or both). Also, prime numbers are the numbers n such that the ring (https://en.wikipedia.org/wiki/Ring_(mathematics), https://mathworld.wolfram.com/Ring.html) of integers modulo n (https://en.wikipedia.org/wiki/Integers_modulo_n, https://mathworld.wolfram.com/Mod.html) (i.e. the ring Zn) is a field (https://en.wikipedia.org/wiki/Field_(mathematics), https://mathworld.wolfram.com/Field.html) (also is an integral domain (https://en.wikipedia.org/wiki/Integral_domain, https://mathworld.wolfram.com/IntegralDomain.html), also is a division ring (https://en.wikipedia.org/wiki/Division_ring), also has no zero divisors (https://en.wikipedia.org/wiki/Zero_divisor, https://mathworld.wolfram.com/ZeroDivisor.html) other than 0 (for the special case that n = 1, it is the zero ring (https://en.wikipedia.org/wiki/Zero_ring, https://mathworld.wolfram.com/TrivialRing.html))). Also, see https://primes.utm.edu/ (The Prime Pages, https://en.wikipedia.org/wiki/PrimePages, https://www.rieselprime.de/ziki/The_Prime_Pages) and https://www.primegrid.com/ (Primegrid, https://en.wikipedia.org/wiki/PrimeGrid, https://www.rieselprime.de/ziki/PrimeGrid) and http://www.numericana.com/answer/primes.htm (the set of the primes) and http://www.numericana.com/answer/factoring.htm (factoring into primes). Besides, "the set of the minimal elements of the base b representations of the prime numbers > b under the subsequence ordering" to "the set of the prime numbers (except b itself) digit strings with length > 1 in base b" to "the partially ordered binary relation by subsequence" is "the set of the prime numbers" to "the set of the integers > 1" to "the partially ordered binary relation by divisibility" (and indeed, the "> 1" in "the prime numbers (except b itself) digit strings with length > 1 in base b" can be corresponded to the "> 1" in "the integers > 1") (for the reason why b itself is excluded (when b is prime, if b is composite, then there is no difference to include the b itself or not), see the sections below and https://mersenneforum.org/showpost.php?p=531632&postcount=7, the main reason is that b is the only prime ending with 0), thus the problem in this article is very important and beautiful.
This problem is an extension of the original minimal prime problem (https://cs.uwaterloo.ca/~cbright/reports/mepn.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_17.pdf), https://cs.uwaterloo.ca/~shallit/Papers/br10.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_18.pdf), https://cs.uwaterloo.ca/~cbright/talks/minimal-slides.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_19.pdf), https://doi.org/10.1080/10586458.2015.1064048 (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_20.pdf), https://scholar.colorado.edu/downloads/hh63sw661 (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_16.pdf), https://github.com/curtisbright/mepn-data, https://github.com/curtisbright/mepn, https://github.com/RaymondDevillers/primes) to cover Conjectures ‘R Us Sierpinski/Riesel conjectures base b (http://www.noprimeleftbehind.net/crus/, http://www.noprimeleftbehind.net/crus/Sierp-conjectures.htm, http://www.noprimeleftbehind.net/crus/Sierp-conjectures-powers2.htm, http://www.noprimeleftbehind.net/crus/Riesel-conjectures.htm, http://www.noprimeleftbehind.net/crus/Riesel-conjectures-powers2.htm, http://www.noprimeleftbehind.net/crus/Sierp-conjecture-reserves.htm, http://www.noprimeleftbehind.net/crus/Riesel-conjecture-reserves.htm, http://www.noprimeleftbehind.net/crus/tab/CRUS_tab.htm, https://www.rieselprime.de/Others/CRUS_tab.htm, http://www.noprimeleftbehind.net/crus/vstats_new/crus-stats.htm, http://www.noprimeleftbehind.net/crus/vstats_new/crus-top20.htm, http://www.noprimeleftbehind.net/crus/vstats_new/crus-unproven.htm, http://www.noprimeleftbehind.net/crus/vstats_new/crus-proven.htm, http://www.noprimeleftbehind.net/crus/vstats_new/all_ck_sierpinski.txt, http://www.noprimeleftbehind.net/crus/vstats_new/all_ck_riesel.txt, https://primes.utm.edu/bios/page.php?id=1372, https://srbase.my-firewall.org/sr5/, http://www.rechenkraft.net/yoyo/y_status_sieve.php, https://www.utm.edu/staff/caldwell/preprints/2to100.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_3.pdf), http://www.bitman.name/math/article/1259 (in Italian)) with k-values < b, i.e. finding the smallest prime of the form k×bn+1 and k×bn−1 (or proving that such prime does not exist) for all k < b (also to cover dual (http://www.kurims.kyoto-u.ac.jp/EMIS/journals/INTEGERS/papers/i61/i61.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_1.pdf), https://www.rechenkraft.net/wiki/Five_or_Bust, https://oeis.org/A076336/a076336c.html, http://www.mit.edu/~kenta/three/prime/dual-sierpinski/ezgxggdm/dualsierp-excerpt.txt, http://mit.edu/kenta/www/three/prime/dual-sierpinski/ezgxggdm/dualsierp.txt.gz, https://mersenneforum.org/showpost.php?p=144991&postcount=1, https://mersenneforum.org/showthread.php?t=10761, https://mersenneforum.org/showthread.php?t=6545) Sierpinski/Riesel conjectures base b with k-values < b, i.e. finding the smallest prime of the form bn+k and bn−k (which are the dual forms of k×bn+1 and k×bn−1, respectively) (or proving that such prime does not exist) for all k < b) (also to cover finding the smallest prime of some classic forms (or proving that such prime does not exist), such as bn+2, bn−2, bn+(b−1), bn−(b−1), 2×bn+1, 2×bn−1, (b−1)×bn+1, (b−1)×bn−1, with n ≥ 1, for the same base b (of course, for some bases b the original minimal prime base b problem already covers finding the smallest prime of these forms, e.g. the original minimal prime base b problem covers finding the smallest prime of the form (b−1)×bn+1 if and only if b−1 is not prime, and the original minimal prime base b problem covers finding the smallest prime of the form (b−1)×bn−1 if and only if neither b−1 nor b−2 is prime, but I want the problem covers finding the smallest prime of these forms for all bases b)). The original minimal prime base b problem does not cover Conjectures ‘R Us Sierpinski/Riesel conjectures base b with conjectured k (http://www.noprimeleftbehind.net/crus/tab/CRUS_tab.htm, https://www.rieselprime.de/Others/CRUS_tab.htm, http://www.noprimeleftbehind.net/crus/vstats_new/all_ck_sierpinski.txt, http://www.noprimeleftbehind.net/crus/vstats_new/all_ck_riesel.txt) < b, since in Riesel side, the prime is not minimal prime in original definition if either k−1 or b−1 (or both) is prime, and in Sierpinski side, the prime is not minimal prime in original definition if k is prime (e.g. 25×3034205−1 is not minimal prime in base 30 in original definition, since it is OT34205 in base 30, and T (= 29 in decimal) is prime, but it is minimal prime in base 30 if only primes > base are counted), but this extended version of minimal prime base b problem does. (There is someone else who also exclude the single-digit primes, but his research is about substring (https://en.wikipedia.org/wiki/Substring) instead of subsequence, see https://www.mersenneforum.org/showpost.php?p=235383&postcount=42, subsequences can contain consecutive elements which were not consecutive in the original sequence, a subsequence which consists of a consecutive run of elements from the original sequence, such as 234 from 123456, is a substring, substring is a refinement of the subsequence, subsequence is a generalization of substring, substring must be subsequence, but subsequence may not be substring, 514 is a subsequence of 352148, but not a substring of 352148, see the list below of the comparation of "subsequence" and "substring")
(we do not research substring in this article, because for substring ordering, "the set of the minimal elements of the base 10 representations of the prime numbers > 10" are very likely to be infinite (and thus almost unsolvable), since all primes of the form 1{0}3 (i.e. https://oeis.org/A159352, for the exponents see https://oeis.org/A049054, also see https://stdkmd.net/nrr/1/10003.htm) or 3{0}1 (i.e. https://oeis.org/A259866, for the exponents see https://oeis.org/A056807, also see https://stdkmd.net/nrr/3/30001.htm) are minimal elements of the base 10 representations of the prime numbers > 10 under the substring ordering, and there is likely infinitely many primes of the form 1{0}3 and infinitely many primes of the form 3{0}1, see https://web.archive.org/web/20100628035147/http://www.math.niu.edu/~rusin/known-math/98/exp_primes and https://mersenneforum.org/showpost.php?p=564786&postcount=3 and https://mersenneforum.org/showpost.php?p=461665&postcount=7)
However, including the base (b) itself results in automatic elimination of all possible extension numbers with "0 after 1" from the set (when the base is prime, if the base is composite, then there is no difference to include the base (b) itself or not), which is quite restrictive (since when the base is prime, then the base (b) itself is the only prime ending with 0, i.e. having trailing zero (https://en.wikipedia.org/wiki/Trailing_zero), since in any base, all numbers ending with 0 (i.e. having trailing zero) are divisible by the base (b), thus cannot be prime unless it is equal the base (b), i.e. "10" in base b, note that the numbers cannot have leading zero (https://en.wikipedia.org/wiki/Leading_zero), since typically this is not the way we write numbers (in any base), thus for all primes in our sets (i.e. all primes > base (b)), all zero digits must be "between" other digits). (for the reference of this, see https://mersenneforum.org/showpost.php?p=531632&postcount=7)
Besides, this problem is better than the original minimal prime problem since this problem is regardless whether 1 is considered as prime or not, i.e. no matter 1 is considered as prime or not prime (https://primes.utm.edu/notes/faq/one.html, https://primefan.tripod.com/Prime1ProCon.html, https://cs.uwaterloo.ca/journals/JIS/VOL15/Caldwell2/cald6.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_24.pdf), http://www.numericana.com/answer/numbers.htm#one), the sets in this problem are the same, while the sets in the original minimal prime problem are different, e.g. in base 10, if 1 is considered as prime, then the set in the original minimal prime problem is {1, 2, 3, 5, 7, 89, 409, 449, 499, 6469, 6949, 9049, 9649, 9949, 60649, 666649, 946669, 60000049, 66000049, 66600049}, while if 1 is not considered as prime, then the set in the original minimal prime problem is {2, 3, 5, 7, 11, 19, 41, 61, 89, 409, 449, 499, 881, 991, 6469, 6949, 9001, 9049, 9649, 9949, 60649, 666649, 946669, 60000049, 66000049, 66600049}, however, in base 10, the set in this problem is always {11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 227, 251, 257, 277, 281, 349, 409, 449, 499, 521, 557, 577, 587, 727, 757, 787, 821, 827, 857, 877, 881, 887, 991, 2087, 2221, 5051, 5081, 5501, 5581, 5801, 5851, 6469, 6949, 8501, 9001, 9049, 9221, 9551, 9649, 9851, 9949, 20021, 20201, 50207, 60649, 80051, 666649, 946669, 5200007, 22000001, 60000049, 66000049, 66600049, 80555551, 555555555551, 5000000000000000000000000000027}, no matter 1 is considered as prime or not prime.
The third reason for excluding the single-digit primes is that they are trivial like that Conjectures ‘R Us Sierpinski/Riesel conjectures base b requires exponent n ≥ 1 for these primes (see https://mersenneforum.org/showpost.php?p=447679&postcount=27), n = 0 is not acceptable to avoid the trivial primes (e.g. 2×bn+1, 4×bn+1, 6×bn+1, 10×bn+1, 12×bn+1, 16×bn+1, 3×bn−1, 4×bn−1, 6×bn−1, 8×bn−1, 12×bn−1, 14×bn−1, ... cannot be quickly eliminated with n = 0, or the conjectures become much more easy and uninteresting), for the same reason, this minimal prime puzzle requires ≥ b (i.e. ≥ 2 digits) for these primes, single-digit primes are not acceptable to avoid the trivial primes (e.g. families containing digit 2, 3, 5, 7, B, D, H, J, N, T, V, ... cannot be quickly eliminated with the single-digit prime, or the conjectures become much more easy and uninteresting).
The fourth reason for excluding the primes ≤ b is that starting with b+1 makes the formula of the number of possible (first digit,last digit) combo of a minimal prime in base b more simple and smooth number (https://en.wikipedia.org/wiki/Smooth_number, https://mathworld.wolfram.com/SmoothNumber.html), it is (b−1)×eulerphi(b) (https://oeis.org/A062955), where eulerphi is Euler's totient function (https://en.wikipedia.org/wiki/Euler%27s_totient_function, https://primes.utm.edu/glossary/xpage/EulersPhi.html, https://mathworld.wolfram.com/TotientFunction.html, http://www.numericana.com/answer/modular.htm#phi, https://oeis.org/A000010), since b−1 is the number of possible first digit (except 0, all digits can be first digit), and eulerphi(b) is the number of possible last digit (only digits coprime to b can be last digit), by rule of product, there are (b−1)×eulerphi(b) possible (first digit,last digit) combo, and if start with b, then when b is prime, there is an additional possible (first digit,last digit) combo: (1,0), and hence the formula will be (b−1)×eulerphi(b)+1 if b is prime, or (b−1)×eulerphi(b) if b is composite (the fully formula will be (b−1)×eulerphi(b)+isprime(b) or (b−1)×eulerphi(b)+floor((b−eulerphi(b)) / (b−1))), which is more complex, and if start with 1 (i.e. the original minimal prime problem), the formula is much more complex.
It is found that both "number of minimal primes base b" and "length of the largest minimal prime base b" are roughly (https://en.wikipedia.org/wiki/Asymptotic_analysis, https://primes.utm.edu/glossary/xpage/AsymptoticallyEqual.html, https://mathworld.wolfram.com/Asymptotic.html) eγ×(b−1)×eulerphi(b), where e = 2.718281828459... is the base of the natural logarithm (https://en.wikipedia.org/wiki/E_(mathematical_constant), https://mathworld.wolfram.com/e.html, https://oeis.org/A001113), γ = 0.577215664901 is the Euler–Mascheroni constant (https://en.wikipedia.org/wiki/Euler%27s_constant, https://primes.utm.edu/glossary/xpage/Gamma.html, https://mathworld.wolfram.com/Euler-MascheroniConstant.html, https://oeis.org/A001620), eulerphi is Euler's totient function (https://en.wikipedia.org/wiki/Euler%27s_totient_function, https://primes.utm.edu/glossary/xpage/EulersPhi.html, https://mathworld.wolfram.com/TotientFunction.html, http://www.numericana.com/answer/modular.htm#phi, https://oeis.org/A000010), you can see the condensed table for bases 2 ≤ b ≤ 36 in the bottom of this article, eγ×(b−1)×eulerphi(b) is an exponential sequence (https://en.wikipedia.org/wiki/Exponential_growth, https://mathworld.wolfram.com/ExponentialGrowth.html) for (b−1)×eulerphi(b) (https://oeis.org/A062955), and since (b−1)×eulerphi(b) has polynomial growth (https://en.wikipedia.org/wiki/Polynomial, https://mathworld.wolfram.com/Polynomial.html) for b (since it is always between b−1 and b2), thus eγ×(b−1)×eulerphi(b) has exponential growth for b, and "largest minimal prime base b" is roughly beγ×(b−1)×eulerphi(b), which has double exponential growth (https://en.wikipedia.org/wiki/Double_exponential_function) for b. (there are also asymptotic analysis for other sets of primes in various bases b, such as the left-truncatable primes and the right-truncatable primes (https://en.wikipedia.org/wiki/Truncatable_prime, https://primes.utm.edu/glossary/xpage/LeftTruncatablePrime.html, https://primes.utm.edu/glossary/xpage/RightTruncatablePrime.html, https://mathworld.wolfram.com/TruncatablePrime.html, https://www.numbersaplenty.com/set/truncatable_prime/) in various bases b, see http://chesswanks.com/num/LTPs/ for the left-truncatable primes in bases b ≤ 120 and http://fatphil.org/maths/rtp/rtp.html for the right-truncatable primes in bases b ≤ 90)
This problem covers finding the smallest prime of these forms in the same base b (or proving that such prime does not exist): (while the original minimal prime problem does not cover some of these forms for some bases (or all bases) b)
(below (as well as the "left b" files), family "12{3}45" means sequence {1245, 12345, 123345, 1233345, 12333345, 123333345, ...}, where the members are expressed as base b strings, like the numbers in https://stdkmd.net/nrr/aaaab.htm, https://stdkmd.net/nrr/abbbb.htm, https://stdkmd.net/nrr/aaaba.htm, https://stdkmd.net/nrr/abaaa.htm, https://stdkmd.net/nrr/abbba.htm, https://stdkmd.net/nrr/abbbc.htm, https://stdkmd.net/nrr/prime/primesize.txt, https://stdkmd.net/nrr/prime/primesize.zip, https://stdkmd.net/nrr/prime/primecount.htm, https://stdkmd.net/nrr/prime/primecount.txt, https://stdkmd.net/nrr/prime/primedifficulty.htm, https://stdkmd.net/nrr/prime/primedifficulty.txt, e.g. 1{3} (in decimal) is the numbers in https://stdkmd.net/nrr/1/13333.htm, and {1}3 (in decimal) is the numbers in https://stdkmd.net/nrr/1/11113.htm, and 1{2}3 (in decimal) is the numbers in https://stdkmd.net/nrr/1/12223.htm, also, superscripts always means exponents (https://en.wikipedia.org/wiki/Exponentiation, https://www.rieselprime.de/ziki/Exponent, https://mathworld.wolfram.com/Exponent.html, https://mathworld.wolfram.com/Power.html, https://mathworld.wolfram.com/Exponentiation.html), subscripts are always used to indicate repetitions of digits, e.g. 1234567 = 123333567, all subscripts are written in decimal)
In fact, this problem covers finding the smallest prime of these form in the same base b: (where x, y, z are any digits in base b)
- x{0}y
- x{y} (unless y = 1) (see https://stdkmd.net/nrr/abbbb.htm)
- {x}y (unless x = 1) (see https://stdkmd.net/nrr/aaaab.htm)
- x{0}yz (unless there is a prime of the form x{0}y or x{0}z)
- xy{0}z (unless there is a prime of the form x{0}z or y{0}z)
- xy{x} (unless either x = 1 or there is a prime of the form y{x} (or both)) (see https://stdkmd.net/nrr/abaaa.htm)
- {x}yx (unless either x = 1 or there is a prime of the form {x}y (or both)) (see https://stdkmd.net/nrr/aaaba.htm)
The primes in forms x{y}, {x}y, xy{x}, {x}yx in base b are near-repdigit primes (https://primes.utm.edu/glossary/xpage/NearRepdigitPrime.html, https://primes.utm.edu/top20/page.php?id=15, https://oeis.org/A164937, https://stdkmd.net/nrr/#factortables_nr, https://stdkmd.net/nrr/records.htm#nrprime, https://stdkmd.net/nrr/records.htm#nrprp) in base b.
Proving that "the set of the minimal elements of the base b representations of the prime numbers > b under the subsequence ordering" = the set S is equivalent to (https://en.wikipedia.org/wiki/Logical_equivalence):
- Prove that all elements in S, when read as base b representation, are primes > b.
- Prove that all proper subsequence of all elements in S, when read as base b representation, which are > b, are composite (https://en.wikipedia.org/wiki/Composite_number, https://primes.utm.edu/glossary/xpage/Composite.html, https://www.rieselprime.de/ziki/Composite_number, https://mathworld.wolfram.com/CompositeNumber.html, https://oeis.org/A002808).
- Prove that all primes > b, when written in base b, contain at least one element in S as subsequence (equivalently, prove that all strings not containing any element in S as subsequence, when read as base b representation, which are > b, are composite).
("the set of the minimal elements of the base b representations of the prime numbers > b under the subsequence ordering" = S is proved if and only if all these three problems are proved, i.e. "the set of the minimal elements of the base b representations of the prime numbers > b under the subsequence ordering" = S is a theorem if and only if all these three "conjectures" are theorems)
e.g. proving that "the set of the minimal elements of the base 10 representations of the prime numbers > 10 under the subsequence ordering" = {11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 227, 251, 257, 277, 281, 349, 409, 449, 499, 521, 557, 577, 587, 727, 757, 787, 821, 827, 857, 877, 881, 887, 991, 2087, 2221, 5051, 5081, 5501, 5581, 5801, 5851, 6469, 6949, 8501, 9001, 9049, 9221, 9551, 9649, 9851, 9949, 20021, 20201, 50207, 60649, 80051, 666649, 946669, 5200007, 22000001, 60000049, 66000049, 66600049, 80555551, 555555555551, 5000000000000000000000000000027}, is equivalent to:
- Prove that all of 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 227, 251, 257, 277, 281, 349, 409, 449, 499, 521, 557, 577, 587, 727, 757, 787, 821, 827, 857, 877, 881, 887, 991, 2087, 2221, 5051, 5081, 5501, 5581, 5801, 5851, 6469, 6949, 8501, 9001, 9049, 9221, 9551, 9649, 9851, 9949, 20021, 20201, 50207, 60649, 80051, 666649, 946669, 5200007, 22000001, 60000049, 66000049, 66600049, 80555551, 555555555551, 5000000000000000000000000000027 are primes > 10.
- Prove that all proper subsequence of all elements in {11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 227, 251, 257, 277, 281, 349, 409, 449, 499, 521, 557, 577, 587, 727, 757, 787, 821, 827, 857, 877, 881, 887, 991, 2087, 2221, 5051, 5081, 5501, 5581, 5801, 5851, 6469, 6949, 8501, 9001, 9049, 9221, 9551, 9649, 9851, 9949, 20021, 20201, 50207, 60649, 80051, 666649, 946669, 5200007, 22000001, 60000049, 66000049, 66600049, 80555551, 555555555551, 5000000000000000000000000000027} which are > 10 are composite.
- Prove that all primes > 10 contain at least one element in {11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 227, 251, 257, 277, 281, 349, 409, 449, 499, 521, 557, 577, 587, 727, 757, 787, 821, 827, 857, 877, 881, 887, 991, 2087, 2221, 5051, 5081, 5501, 5581, 5801, 5851, 6469, 6949, 8501, 9001, 9049, 9221, 9551, 9649, 9851, 9949, 20021, 20201, 50207, 60649, 80051, 666649, 946669, 5200007, 22000001, 60000049, 66000049, 66600049, 80555551, 555555555551, 5000000000000000000000000000027} as subsequence (equivalently, prove that all numbers > 10 not containing any element in {11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 227, 251, 257, 277, 281, 349, 409, 449, 499, 521, 557, 577, 587, 727, 757, 787, 821, 827, 857, 877, 881, 887, 991, 2087, 2221, 5051, 5081, 5501, 5581, 5801, 5851, 6469, 6949, 8501, 9001, 9049, 9221, 9551, 9649, 9851, 9949, 20021, 20201, 50207, 60649, 80051, 666649, 946669, 5200007, 22000001, 60000049, 66000049, 66600049, 80555551, 555555555551, 5000000000000000000000000000027} as subsequence are composite, since they are contraposition (https://en.wikipedia.org/wiki/Contraposition), P ⟶ Q and ¬Q ⟶ ¬P are logically equivalent (https://en.wikipedia.org/wiki/Logical_equivalence)).
(since for base b = 10, all these three problems are proved, i.e. all they are theorems, thus, "the set of the minimal elements of the base 10 representations of the prime numbers > 10 under the subsequence ordering" = {11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 227, 251, 257, 277, 281, 349, 409, 449, 499, 521, 557, 577, 587, 727, 757, 787, 821, 827, 857, 877, 881, 887, 991, 2087, 2221, 5051, 5081, 5501, 5581, 5801, 5851, 6469, 6949, 8501, 9001, 9049, 9221, 9551, 9649, 9851, 9949, 20021, 20201, 50207, 60649, 80051, 666649, 946669, 5200007, 22000001, 60000049, 66000049, 66600049, 80555551, 555555555551, 5000000000000000000000000000027} is also proved, i.e. "the set of the minimal elements of the base 10 representations of the prime numbers > 10 under the subsequence ordering" = {11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 227, 251, 257, 277, 281, 349, 409, 449, 499, 521, 557, 577, 587, 727, 757, 787, 821, 827, 857, 877, 881, 887, 991, 2087, 2221, 5051, 5081, 5501, 5581, 5801, 5851, 6469, 6949, 8501, 9001, 9049, 9221, 9551, 9649, 9851, 9949, 20021, 20201, 50207, 60649, 80051, 666649, 946669, 5200007, 22000001, 60000049, 66000049, 66600049, 80555551, 555555555551, 5000000000000000000000000000027} is also a theorem)
Theorem (https://en.wikipedia.org/wiki/Theorem, https://mathworld.wolfram.com/Theorem.html, https://primes.utm.edu/notes/proofs/): The set of the minimal elements of the base 10 representations of the prime numbers > 10 under the subsequence ordering is {11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 227, 251, 257, 277, 281, 349, 409, 449, 499, 521, 557, 577, 587, 727, 757, 787, 821, 827, 857, 877, 881, 887, 991, 2087, 2221, 5051, 5081, 5501, 5581, 5801, 5851, 6469, 6949, 8501, 9001, 9049, 9221, 9551, 9649, 9851, 9949, 20021, 20201, 50207, 60649, 80051, 666649, 946669, 5200007, 22000001, 60000049, 66000049, 66600049, 80555551, 555555555551, 5000000000000000000000000000027}
Proof (https://en.wikipedia.org/wiki/Mathematical_proof, https://mathworld.wolfram.com/Proof.html, https://primes.utm.edu/notes/proofs/): (this proof uses the notation in http://www.wiskundemeisjes.nl/wp-content/uploads/2007/02/minimal.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_12.pdf), i.e. "X ◁ Y" means "X is a subsequence of Y") (below, 𝜆 is the empty string (https://en.wikipedia.org/wiki/Empty_string)) (bold for minimal primes)
Assume p is a prime > 10, and the last digit of p must lie in {1,3,7,9}
Case 1: p ends with 1.
In this case we can write p = x1. If x contains 1, 3, 4, 6, or 7, then (respectively) 11 ◁ p, 31 ◁ p, 41 ◁ p, 61 ◁ p, or 71 ◁ p. Hence we may assume all digits of x are 0, 2, 5, 8, or 9.
Case 1.1: p begins with 2.
In this case we can write p = 2y1. If 5 ◁ y, then 251 ◁ p. If 8 ◁ y, then 281 ◁ p. If 9 ◁ y, then 29 ◁ p. Hence we may assume all digits of y are 0 or 2.
If 22 ◁ y, then 2221 ◁ p. Hence we may assume y contains zero or one 2's.
If y contains no 2's, then p ∈ 2{0}1. But then, since the sum of the digits of p is 3, p is divisible by 3, so p cannot be prime.
If y contains exactly one 2, then we can write p = 2z2w1, where z,w ∈ {0}. If 0 ◁ z and 0 ◁ w, then 20201 ◁ p. Hence we may assume either z or w is empty.
If z is empty, then p ∈ 22{0}1, and the smallest prime p ∈ 22{0}1 is 22000001.
If w is empty, then p ∈ 2{0}21, and the smallest prime p ∈ 2{0}21 is 20021.
Case 1.2: p begins with 5.
In this case we can write p = 5y1. If 2 ◁ y, then 521 ◁ p. If 9 ◁ y, then 59 ◁ p. Hence we may assume all digits of y are 0, 5, or 8.
If 05 ◁ y, then 5051 ◁ p. If 08 ◁ y, then 5081 ◁ p. If 50 ◁ y, then 5501 ◁ p. If 58 ◁ y, then 5581 ◁ p. If 80 ◁ y, then 5801 ◁ p. If 85 ◁ y, then 5851 ◁ p. Hence we may assume y ∈ {0} ∪ {5} ∪ {8}.
If y ∈ {0}, then p ∈ 5{0}1. But then, since the sum of the digits of p is 6, p is divisible by 3, so p cannot be prime.
If y ∈ {5}, then p ∈ 5{5}1, and the smallest prime p ∈ 5{5}1 is 555555555551.
If y ∈ {8}, since if 88 ◁ y, then 881 ◁ p, hence we may assume y ∈ {𝜆,8}, and thus p ∈ {51,581}, but 51 and 581 are both composite.
Case 1.3: p begins with 8.
In this case we can write p = 8y1. If 2 ◁ y, then 821 ◁ p. If 8 ◁ y, then 881 ◁ p. If 9 ◁ y, then 89 ◁ p. Hence we may assume all digits of y are 0 or 5.
If 50 ◁ y, then 8501 ◁ p. Hence we may assume y ∈ {0}{5}.
If 005 ◁ y, then 80051 ◁ p. Hence we may assume y ∈ {0} ∪ {5} ∪ 0{5}.
If y ∈ {0}, then p ∈ 8{0}1. But then, since the sum of the digits of p is 9, p is divisible by 3, so p cannot be prime.
If y ∈ {5}, since if 55555555555 ◁ y, then 555555555551 ◁ p, hence we may assume y ∈ {𝜆, 5, 55, 555, 5555, 55555, 555555, 5555555, 55555555, 555555555, 5555555555}, and thus p ∈ {81, 851, 8551, 85551, 855551, 8555551, 85555551, 855555551, 8555555551, 85555555551, 855555555551}, but all of these numbers are composite.
If y ∈ 0{5}, since if 55555555555 ◁ y, then 555555555551 ◁ p, hence we may assume y ∈ {0, 05, 055, 0555, 05555, 055555, 0555555, 05555555, 055555555, 0555555555, 05555555555}, and thus p ∈ {801, 8051, 80551, 805551, 8055551, 80555551, 805555551, 8055555551, 80555555551, 805555555551, 8055555555551}, and of these numbers only 80555551 and 8055555551 are primes, but 80555551 ◁ 8055555551, thus only 80555551 is minimal prime.
Case 1.4: p begins with 9.
In this case we can write p = 9y1. If 9 ◁ y, then 991 ◁ p. Hence we may assume all digits of y are 0, 2, 5, or 8.
If 00 ◁ y, then 9001 ◁ p. If 22 ◁ y, then 9221 ◁ p. If 55 ◁ y, then 9551 ◁ p. If 88 ◁ y, then 881 ◁ p. Hence we may assume y contains at most one 0, at most one 2, at most one 5, and at most one 8.
If y only contains at most one 0 and does not contain any of {2,5,8}, then y ∈ {𝜆,0}, and thus p ∈ {91,901}, but 91 and 901 are both composite. If y only contains at most one 0 and only one of {2,5,8}, then the sum of the digits of p is divisible by 3, p is divisible by 3, so p cannot be prime. Hence we may assume y contains at least two of {2,5,8}.
If 25 ◁ y, then 251 ◁ p. If 28 ◁ y, then 281 ◁ p. If 52 ◁ y, then 521 ◁ p. If 82 ◁ y, then 821 ◁ p. Hence we may assume y contains no 2's (since if y contains 2, then y cannot contain either 5's or 8's, which is a contradiction).
If 85 ◁ y, then 9851 ◁ p. Hence we may assume y ∈ {58,580,508,058}, and thus p ∈ {9581,95801,95081,90581}, and of these numbers only 95801 is prime, but 95801 is not minimal prime since 5801 ◁ 95801.
Case 2: p ends with 3.
In this case we can write p = x3. If x contains 1, 2, 4, 5, 7, or 8, then (respectively) 13 ◁ p, 23 ◁ p, 43 ◁ p, 53 ◁ p, 73 ◁ p, or 83 ◁ p. Hence we may assume all digits of x are 0, 3, 6, or 9, and thus all digits of p are 0, 3, 6, or 9. But then, since the digits of p all have a common factor 3, p is divisible by 3, so p cannot be prime.
Case 3: p ends with 7.
In this case we can write p = x7. If x contains 1, 3, 4, 6, or 9, then (respectively) 17 ◁ p, 37 ◁ p, 47 ◁ p, 67 ◁ p, or 97 ◁ p. Hence we may assume all digits of x are 0, 2, 5, 7, or 8.
Case 3.1: p begins with 2.
In this case we can write p = 2y7. If 2 ◁ y, then 227 ◁ p. If 5 ◁ y, then 257 ◁ p. If 7 ◁ y, then 277 ◁ p. Hence we may assume all digits of y are 0 or 8.
If 08 ◁ y, then 2087 ◁ p. If 88 ◁ y, then 887 ◁ p. Hence we may assume y ∈ {0} ∪ 8{0}.
If y ∈ {0}, then p ∈ 2{0}7. But then, since the sum of the digits of p is 9, p is divisible by 3, so p cannot be prime.
If y ∈ 8{0}, then p ∈ 28{0}7. But then p is divisible by 7, since for n ≥ 0 we have 7 × 40n1 = 280n7.
Case 3.2: p begins with 5.
In this case we can write p = 5y7. If 5 ◁ y, then 557 ◁ p. If 7 ◁ y, then 577 ◁ p. If 8 ◁ y, then 587 ◁ p. Hence we may assume all digits of y are 0 or 2.
If 22 ◁ y, then 227 ◁ p. Hence we may assume y contains zero or one 2's.
If y contains no 2's, then p ∈ 5{0}7. But then, since the sum of the digits of p is 12, p is divisible by 3, so p cannot be prime.
If y contains exactly one 2, then we can write p = 5z2w7, where z,w ∈ {0}. If 0 ◁ z and 0 ◁ w, then 50207 ◁ p. Hence we may assume either z or w is empty.
If z is empty, then p ∈ 52{0}7, and the smallest prime p ∈ 52{0}7 is 5200007.
If w is empty, then p ∈ 5{0}27, and the smallest prime p ∈ 5{0}27 is 5000000000000000000000000000027.
Case 3.3: p begins with 7.
In this case we can write p = 7y7. If 2 ◁ y, then 727 ◁ p. If 5 ◁ y, then 757 ◁ p. If 8 ◁ y, then 787 ◁ p. Hence we may assume all digits of y are 0 or 7, and thus all digits of p are 0 or 7. But then, since the digits of p all have a common factor 7, p is divisible by 7, so p cannot be prime.
Case 3.4: p begins with 8.
In this case we can write p = 8y7. If 2 ◁ y, then 827 ◁ p. If 5 ◁ y, then 857 ◁ p. If 7 ◁ y, then 877 ◁ p. If 8 ◁ y, then 887 ◁ p. Hence we may assume y ∈ {0}, and thus p ∈ 8{0}7. But then, since the sum of the digits of p is 15, p is divisible by 3, so p cannot be prime.
Case 4: p ends with 9.
In this case we can write p = x9. If x contains 1, 2, 5, 7, or 8, then (respectively) 19 ◁ p, 29 ◁ p, 59 ◁ p, 79 ◁ p, or 89 ◁ p. Hence we may assume all digits of x are 0, 3, 4, 6, or 9.
If 44 ◁ x, then 449 ◁ p. Hence we may assume x contains zero or one 4's.
If x contains no 4's, then all digits of x are 0, 3, 6, or 9, and thus all digits of p are 0, 3, 6, or 9. But then, since the digits of p all have a common factor 3, p is divisible by 3, so p cannot be prime. Hence we may assume that x contains exactly one 4.
Case 4.1: p begins with 3.
In this case we can write p = 3y4z9, where all digits of y, z are 0, 3, 6, or 9. We must have 349 ◁ p.
Case 4.2: p begins with 4.
In this case we can write p = 4y9, where all digits of y are 0, 3, 6, or 9. If 0 ◁ y, then 409 ◁ p. If 3 ◁ y, then 43 ◁ p. If 9 ◁ y, then 499 ◁ p. Hence we may assume y ∈ {6}, and thus p ∈ 4{6}9. But then p is divisible by 7, since for n ≥ 0 we have 7 × 6n7 = 46n9.
Case 4.3: p begins with 6.
In this case we can write p = 6y4z9, where all digits of y, z are 0, 3, 6, or 9. If 0 ◁ z, then 409 ◁ p. If 3 ◁ z, then 43 ◁ p. If 6 ◁ z, then 6469 ◁ p. If 9 ◁ z, then 499 ◁ p. Hence we may assume z is empty.
If 3 ◁ y, then 349 ◁ p. If 9 ◁ y, then 6949 ◁ p. Hence we may assume all digits of y are 0 or 6.
If 06 ◁ y, then 60649 ◁ p. Hence we may assume y ∈ {6}{0}.
If 666 ◁ y, then 666649 ◁ p. If 00000 ◁ y, then 60000049 ◁ p. Hence we may assume y ∈ {𝜆, 0, 00, 000, 0000, 6, 60, 600, 6000, 60000, 66, 660, 6600, 66000, 660000}, and thus p ∈ {649, 6049, 60049, 600049, 6000049, 6649, 66049, 660049, 6600049, 66000049, 66649, 666049, 6660049, 66600049, 666000049}, and of these numbers only 66000049 and 66600049 are primes.
Case 4.4: p begins with 9.
In this case we can write p = 9y4z9, where all digits of y, z are 0, 3, 6, or 9. If 0 ◁ y, then 9049 ◁ p. If 3 ◁ y, then 349 ◁ p. If 6 ◁ y, then 9649 ◁ p. If 9 ◁ y, then 9949 ◁ p. Hence we may assume y is empty.
If 0 ◁ z, then 409 ◁ p. If 3 ◁ z, then 43 ◁ p. If 9 ◁ z, then 499 ◁ p. Hence we may assume z ∈ {6}, and thus p ∈ 94{6}9, and the smallest prime p ∈ 94{6}9 is 946669.
The reader may enjoy trying to write the proof for bases b = 2, 3, 4, 5, 6, 7, 8, 9, 12, of course, the proof for base b = 2 is trivial, since all primes p > 2 must start and end with 1 in base 2, thus we must have 11 ◁ p, however, for some bases b like 24 (the currently largest "proven" base b, including the primality proving for the primes in the set), it is almost impossible to write the proof by hand, since base b = 24 has too many (3409) minimal primes to write the proof, thus the C++ program code (for computer to compute (https://en.wikipedia.org/wiki/Computing) the proof) is made.
(in fact, the fully proof should also include the primality proving (https://en.wikipedia.org/wiki/Primality_test, https://www.rieselprime.de/ziki/Primality_test, https://mathworld.wolfram.com/PrimalityTest.html, https://primes.utm.edu/prove/prove3.html, https://primes.utm.edu/prove/prove4.html) for all primes in the set (like https://web.archive.org/web/20020809212051/http://www.users.globalnet.co.uk/~aads/C0034177.html (for the generalized repunit prime in base b = 3 with length 4177) and https://web.archive.org/web/20020701171455/http://www.users.globalnet.co.uk/~aads/C0066883.html (for the generalized repunit prime in base b = 6 with length 6883) and https://web.archive.org/web/20020809122706/http://www.users.globalnet.co.uk/~aads/C0071699.html (for the generalized repunit prime in base b = 7 with length 1699) and https://web.archive.org/web/20020809122635/http://www.users.globalnet.co.uk/~aads/C0101031.html (for the generalized repunit prime in base b = 10 with length 1031) and https://web.archive.org/web/20020809122237/http://www.users.globalnet.co.uk/~aads/C0114801.html (for the generalized repunit prime in base b = 11 with length 4801) and https://web.archive.org/web/20020809122947/http://www.users.globalnet.co.uk/~aads/C0130991.html (for the generalized repunit prime in base b = 13 with length 991) and https://web.archive.org/web/20020809124216/http://www.users.globalnet.co.uk/~aads/C0131021.html (for the generalized repunit prime in base b = 13 with length 1021) and https://web.archive.org/web/20020809125049/http://www.users.globalnet.co.uk/~aads/C0131193.html (for the generalized repunit prime in base b = 13 with length 1193) and https://web.archive.org/web/20020809124458/http://www.users.globalnet.co.uk/~aads/C0152579.html (for the generalized repunit prime in base b = 15 with length 2579) and https://web.archive.org/web/20020809124537/http://www.users.globalnet.co.uk/~aads/C0220857.html (for the generalized repunit prime in base b = 22 with length 857) and https://web.archive.org/web/20020809152611/http://www.users.globalnet.co.uk/~aads/C0315581.html (for the generalized repunit prime in base b = 31 with length 5581) and https://web.archive.org/web/20020809124929/http://www.users.globalnet.co.uk/~aads/C0351297.html (for the generalized repunit prime in base b = 35 with length 1297) and https://stdkmd.net/nrr/pock/p746.htm (for the prime 67457 in decimal) and https://stdkmd.net/nrr/pock/p875.htm (for the prime 68747 in decimal) and https://stdkmd.net/nrr/pock/p1204.htm (for the prime 612037 in decimal) and https://stdkmd.net/nrr/pock/p1364.htm (for the prime 613637 in decimal) and https://stdkmd.net/nrr/pock/p1657.htm (for the prime 916561 in decimal) and https://stdkmd.net/nrr/pock/p1756.htm (for the prime 191755 in decimal, in fact, this prime can be quickly proven prime using the N+1 primality proving (https://primes.utm.edu/prove/prove3_2.html, http://bln.curtisbright.com/2013/10/09/the-n-1-and-n1-primality-tests/, http://factordb.com/nmoverview.php?method=2)) and https://stdkmd.net/nrr/pock/p2065.htm (for the prime 720641 in decimal) and https://stdkmd.net/nrr/pock/p2080.htm (for the prime 420791 in decimal) and https://stdkmd.net/nrr/pock/p2240.htm (for the prime 622397 in decimal) and https://stdkmd.net/nrr/pock/p2566.htm (for the prime 225651 in decimal) and https://stdkmd.net/nrr/pock/p3021.htm (for the prime 193020 in decimal, in fact, this prime can be quickly proven prime using the N+1 primality proving (https://primes.utm.edu/prove/prove3_2.html, http://bln.curtisbright.com/2013/10/09/the-n-1-and-n1-primality-tests/, http://factordb.com/nmoverview.php?method=2)) and https://stdkmd.net/nrr/pock/p4417.htm (for the prime 844161 in decimal) and http://primes.utm.edu/lists/single_primes/50005cert.txt (for the prime https://primes.utm.edu/primes/page.php?id=12806) and https://web.archive.org/web/20150911225651/https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0104&L=nmbrthry&P=R1807&D=0 (for the prime https://primes.utm.edu/primes/page.php?id=11084) and http://xenon.stanford.edu/~tjw/pp/7176_24691/index.html (for the prime https://primes.utm.edu/primes/page.php?id=123456) and https://web.archive.org/web/20170515153924/http://bitc.bme.emory.edu/~lzhou/blogs/?p=263 (for the primes corresponding to https://oeis.org/A181980) and https://web.archive.org/web/20131020160719/http://www.primes.viner-steward.org/andy/E/33281741.html (for the prime https://primes.utm.edu/primes/page.php?id=82858), or using an elliptic curve primality proving (https://primes.utm.edu/prove/prove4_2.html, https://en.wikipedia.org/wiki/Elliptic_curve_primality, https://primes.utm.edu/glossary/xpage/ECPP.html, https://mathworld.wolfram.com/EllipticCurvePrimalityProving.html, https://primes.utm.edu/top20/page.php?id=27) implementation such as PRIMO (http://www.ellipsa.eu/public/primo/primo.html, http://www.rieselprime.de/dl/Primo309.zip, https://primes.utm.edu/bios/page.php?id=46, https://www.rieselprime.de/ziki/Primo, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/primo-433-lx64, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/Primo309) to compute primality certificates (https://en.wikipedia.org/wiki/Primality_certificate, https://primes.utm.edu/glossary/xpage/Certificate.html, https://mathworld.wolfram.com/PrimalityCertificate.html, http://www.lix.polytechnique.fr/Labo/Francois.Morain/Primes/myprimes.html, https://stdkmd.net/nrr/cert/, http://factordb.com/certoverview.php)) and the compositeness proving for all proper subsequence of all primes in the set (usually by trial division (https://en.wikipedia.org/wiki/Trial_division, https://primes.utm.edu/glossary/xpage/TrialDivision.html, https://www.rieselprime.de/ziki/Trial_factoring, https://mathworld.wolfram.com/TrialDivision.html, http://www.numericana.com/answer/factoring.htm#trial) (usually to 109, this will covered by sieving (https://www.rieselprime.de/ziki/Sieving, https://www.rieselprime.de/ziki/Sieving_a_range_of_sequences, https://mathworld.wolfram.com/Sieve.html, http://www.rechenkraft.net/yoyo/y_status_sieve.php) for the numbers > 101000) or Fermat primality test (https://primes.utm.edu/prove/prove2_2.html, https://en.wikipedia.org/wiki/Fermat_primality_test, https://en.wikipedia.org/wiki/Fermat_pseudoprime, https://primes.utm.edu/glossary/xpage/PRP.html, https://www.rieselprime.de/ziki/Fermat_pseudoprimality_test, https://mathworld.wolfram.com/FermatPseudoprime.html, http://www.numericana.com/answer/pseudo.htm#pseudoprime, http://ntheory.org/data/psps.txt, https://sites.google.com/view/fermat-pseudoprime, https://sites.google.com/view/bases-fermat-pseudoprime, https://oeis.org/A001567, https://oeis.org/A005935, https://oeis.org/A052155, https://oeis.org/A083876, https://oeis.org/A181780, https://oeis.org/A063994, https://oeis.org/A194946, https://oeis.org/A195327, https://oeis.org/A002997, https://oeis.org/A191311, https://oeis.org/A090086, https://oeis.org/A007535) (usually base 2 and base 3)), but in the proof above we assume that we know whether a number is prime or not)
Determining the set of the minimal elements of a arbitrary set of strings under the subsequence ordering is in general unsolvable, and can be difficult even when this set is relatively simple (such as the base b representations of the prime numbers > b), also, determining the set of the minimal elements of a arbitrary set of strings under the subsequence ordering may be an open problem (https://en.wikipedia.org/wiki/Open_problem, https://en.wikipedia.org/wiki/List_of_unsolved_problems_in_mathematics, https://primes.utm.edu/glossary/xpage/OpenQuestion.html, https://mathworld.wolfram.com/UnsolvedProblems.html, http://www.numericana.com/answer/open.htm, https://primes.utm.edu/notes/conjectures/) or NP-complete (https://en.wikipedia.org/wiki/NP-complete, https://mathworld.wolfram.com/NP-CompleteProblem.html) or an undecidable problem (https://en.wikipedia.org/wiki/Undecidable_problem, https://mathworld.wolfram.com/Undecidable.html), or an example of Gödel's incompleteness theorems (https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems, https://mathworld.wolfram.com/GoedelsFirstIncompletenessTheorem.html) (like the continuum hypothesis (https://en.wikipedia.org/wiki/Continuum_hypothesis, https://mathworld.wolfram.com/ContinuumHypothesis.html) and the halting problem (https://en.wikipedia.org/wiki/Halting_problem, https://mathworld.wolfram.com/HaltingProblem.html)), or as hard as the unsolved problems in mathematics, such as the Riemann hypothesis (https://en.wikipedia.org/wiki/Riemann_hypothesis, https://primes.utm.edu/glossary/xpage/RiemannHypothesis.html, https://mathworld.wolfram.com/RiemannHypothesis.html, http://www.numericana.com/answer/open.htm#rh) and the abc conjecture (https://en.wikipedia.org/wiki/Abc_conjecture, https://mathworld.wolfram.com/abcConjecture.html, http://www.numericana.com/answer/open.htm#abc) and the Schinzel's hypothesis H (https://en.wikipedia.org/wiki/Schinzel%27s_hypothesis_H, https://mathworld.wolfram.com/SchinzelsHypothesis.html, http://www.numericana.com/answer/open.htm#h), which are the three famous hard problems in number theory (https://en.wikipedia.org/wiki/Number_theory, https://www.rieselprime.de/ziki/Number_theory, https://mathworld.wolfram.com/NumberTheory.html).
The following is a "semi-algorithm" (https://en.wikipedia.org/wiki/Semi-algorithm) that is guaranteed to produce the minimal elements of a arbitrary set of strings under the subsequence ordering, but it is not so easy to implement:
- M := ∅
- while (L ≠ ∅) do
- choose x, a shortest string in L
- M := M ∪ {x}
- L := L − sup({x})
In practice, for arbitrary L, we cannot feasibly carry out step 5. Instead, we work with L', some regular overapproximation to L, until we can show L' = ∅ (which implies L = ∅). In practice, L' is usually chosen to be a finite union of sets of the form L1{L2}L3, where each of L1, L2, L3 is finite. In the case we consider in this project, we then have to determine whether such a family contains a prime > b or not.
To solve this problem (i.e. to compute (https://en.wikipedia.org/wiki/Computing) the set of the minimal elements of the base b representations of the prime numbers > b under the subsequence ordering), we need to determine whether a given family contains a prime. In practice, if family x{Y}z (where x and z are strings (may be empty) of digits in base b, Y is a set of digits in base b) could not be ruled out as only containing composites and Y contains two or more digits, then a relatively small prime > b could always be found in this family. Intuitively, this is because there are a large number of small strings in such a family, and at least one is likely to be prime (e.g. there are 2n−2 strings of length n in the family 1{3,7}9, and there are over a thousand strings of length 12 in the family 1{3,7}9, thus it is very impossible that these numbers are all composite). In the case Y contains only one digit, this family is of the form x{y}z, and there is only a single string of each length > (the length of x + the length of z), and it is not known if the following decision problem (https://en.wikipedia.org/wiki/Decision_problem, https://mathworld.wolfram.com/DecisionProblem.html) is recursively solvable:
Problem: Given strings x, z (may be empty), a digit y, and a base b, does there exist a prime number whose base-b expansion is of the form xynz for some n ≥ 0? (If we say "yes", then we should find a such prime (the smallest such prime may be very large, e.g. > 1025000, and if so, then we should use primality testing programs such as PFGW or LLR to find it, and before using these programs, we should use sieving programs such as srsieve (or sr1/2/5sieve) to remove the numbers either having small prime factors or having algebraic factors) and prove its primality (and if we want to solve the problem in this article, we should check whether this prime is the smallest such prime or not, i.e. prove all smaller numbers of the form xynz with n ≥ 0 are composite, usually by trial division or Fermat primality test), and if we say "no", then we should prove that such prime does not exist, may by covering congruence, algebraic factorization, or combine of them)
An algorithm to solve this problem, for example, would allow us to decide if there are any additional Fermat primes (https://en.wikipedia.org/wiki/Fermat_number, https://primes.utm.edu/glossary/xpage/FermatNumber.html, https://www.rieselprime.de/ziki/Fermat_number, https://mathworld.wolfram.com/FermatNumber.html, https://mathworld.wolfram.com/FermatPrime.html, https://pzktupel.de/Primetables/TableFe1.php, http://www.prothsearch.com/fermat.html, http://www.fermatsearch.org/) (of the form 22n+1) other than the known ones (corresponding to n = 0, 1, 2, 3, 4). To see this, take b = 2, x = 1, y = 0, and z = 0161. Since if 2n+1 is prime then n must be a power of two (http://yves.gallot.pagesperso-orange.fr/primes/math.html), a prime of the form xynz in base b must be a new Fermat prime. Besides, it would allow us to decide if there are infinitely many Mersenne primes (https://en.wikipedia.org/wiki/Mersenne_prime, https://primes.utm.edu/glossary/xpage/MersenneNumber.html, https://primes.utm.edu/glossary/xpage/Mersennes.html, https://www.rieselprime.de/ziki/Mersenne_number, https://www.rieselprime.de/ziki/Mersenne_prime, https://mathworld.wolfram.com/MersenneNumber.html, https://mathworld.wolfram.com/MersennePrime.html, https://pzktupel.de/Primetables/TableMe1.php, https://primes.utm.edu/top20/page.php?id=4, https://www.mersenne.org/, https://www.mersenne.org/primes/, https://www.mersenne.ca/, https://primes.utm.edu/mersenne/) (of the form 2p−1 with prime p). To see this, take b = 2, x = 𝜆 (the empty string (https://en.wikipedia.org/wiki/Empty_string)), y = 1, and z = 1n+1, where n is the exponent of the Mersenne prime which we want to know whether it is the largest Mersenne prime or not. Since if 2n−1 is prime then n must be a prime (https://primes.utm.edu/notes/proofs/Theorem2.html), a prime of the form xynz in base b must be a new Mersenne prime. Also, it would allow us to decide whether 78557 is the smallest Sierpinski number (i.e. odd numbers k such that k×2n+1 is composite for all n ≥ 1) (http://www.prothsearch.com/sierp.html, http://www.primegrid.com/forum_thread.php?id=1647, http://www.primegrid.com/forum_thread.php?id=972, http://www.primegrid.com/forum_thread.php?id=1750, http://www.primegrid.com/forum_thread.php?id=5758, http://www.primegrid.com/stats_sob_llr.php, http://www.primegrid.com/stats_psp_llr.php, http://www.primegrid.com/stats_esp_llr.php, https://web.archive.org/web/20160405211049/http://www.seventeenorbust.com/, https://en.wikipedia.org/wiki/Sierpi%C5%84ski_number, https://primes.utm.edu/glossary/xpage/SierpinskiNumber.html, https://www.rieselprime.de/ziki/Sierpi%C5%84ski_problem, https://www.rieselprime.de/ziki/Proth_2_Sierpinski, https://mathworld.wolfram.com/SierpinskiNumberoftheSecondKind.html, https://en.wikipedia.org/wiki/Seventeen_or_Bust, https://www.rieselprime.de/ziki/Seventeen_or_Bust, https://web.archive.org/web/20190929190947/https://primes.utm.edu/glossary/xpage/ColbertNumber.html, https://mathworld.wolfram.com/ColbertNumber.html, http://www.numericana.com/answer/primes.htm#sierpinski, http://www.bitman.name/math/article/204 (in Italian), https://oeis.org/A076336) and whether 509203 is the smallest Riesel number (i.e. odd numbers k such that k×2n−1 is composite for all n ≥ 1) (http://www.prothsearch.com/rieselprob.html, http://www.primegrid.com/forum_thread.php?id=1731, http://www.primegrid.com/stats_trp_llr.php, https://web.archive.org/web/20061021153313/http://stats.rieselsieve.com//queue.php, https://en.wikipedia.org/wiki/Riesel_number, https://primes.utm.edu/glossary/xpage/RieselNumber.html, https://www.rieselprime.de/ziki/Riesel_problem, https://www.rieselprime.de/ziki/Riesel_2_Riesel, https://mathworld.wolfram.com/RieselNumber.html, http://www.bitman.name/math/article/203 (in Italian), https://oeis.org/A076337, https://oeis.org/A101036), etc.
Also, there are some examples in decimal (i.e. base b = 10): (references: https://stdkmd.net/nrr/prime/primecount.htm, https://stdkmd.net/nrr/prime/primecount.txt, https://stdkmd.net/nrr/prime/primedifficulty.htm, https://stdkmd.net/nrr/prime/primedifficulty.txt)
x | y | z | answer |
---|---|---|---|
7 | 1 | 7 | Yes! But the smallest such prime is very large, it is 71109057, its algebraic form is (64×1010906+53)/9, its factordb entry is http://factordb.com/index.php?id=1000000000008860930, its primality certificate is http://factordb.com/cert.php?id=1000000000008860930 and https://stdkmd.net/nrr/cert/7/71117_10906.zip |
9 | 4 | 9 | No! All numbers of this form is divisible by some element of {3,7,11,13}, since its algebraic form is (85×10n+1+41)/9, it is divisible by 3 if n == 0 mod 3, divisible by 7 if n == 5 mod 6, divisible by 11 if n == 0 mod 2, divisible by 13 if n == 1 mod 6 |
56 | 1 | 𝜆 (the empty string (https://en.wikipedia.org/wiki/Empty_string)) | Yes! But the smallest such prime is very large, it is 56118470, its algebraic form is (505×1018470−1)/9, its factordb entry is http://factordb.com/index.php?id=1100000000301454592, its primality certificate is http://factordb.com/cert.php?id=1100000000301454592 and https://stdkmd.net/nrr/cert/5/56111_18470.zip |
38 | 1 | 𝜆 (the empty string (https://en.wikipedia.org/wiki/Empty_string)) | No! All numbers of this form is either divisible by some element of {3,37} or has a difference-of-two-cubes factorization, since its algebraic form is (343×10n−1)/9, it is divisible by 3 if n == 1 mod 3, divisible by 37 if n == 2 mod 3, and can be factored to (343×10n−1)/9 = (7×10n/3−1) × (49×102×n/3+7×10n/3+1) / 9 if n == 0 mod 3 |
𝜆 (the empty string (https://en.wikipedia.org/wiki/Empty_string)) | 2 | 99 | Yes! But the smallest such prime is very large, it is 21915199, its algebraic form is (2×1019153+691)/9, its factordb entry is http://factordb.com/index.php?id=1100000000301493137, its primality certificate is http://factordb.com/cert.php?id=1100000000301493137 and https://stdkmd.net/nrr/cert/2/2w99_19153.zip |
𝜆 (the empty string (https://en.wikipedia.org/wiki/Empty_string)) | 5 (at least one 5) | 37 | No! All numbers of this form is divisible by some element of {3,7,13,37}, since its algebraic form is (5×10n+2−167)/9, it is divisible by 3 if n == 1 mod 3, divisible by 7 if n == 2 mod 6, divisible by 13 if n == 5 mod 6, divisible by 37 if n == 0 mod 3 |
44 | 9 (at least two 9) | 𝜆 (the empty string (https://en.wikipedia.org/wiki/Empty_string)) | Yes! But the smallest such prime is very large, it is 44911959, its algebraic form is 45×1011959−1, its factordb entry is http://factordb.com/index.php?id=1100000000291927010, it can be proven prime by the N+1 primality proving (https://primes.utm.edu/prove/prove3_2.html, http://bln.curtisbright.com/2013/10/09/the-n-1-and-n1-primality-tests/, http://factordb.com/nmoverview.php?method=2) |
My conjecture: If family xynz (with fixed strings x, z (may be empty), fixed digit y, and variable n) in base b (with fixed b ≥ 2) cannot be proven to only contain composites or only contain finitely many primes (by covering congruence, algebraic factorization, or combine of them), then family xynz in base b contains infinitely many primes (this is equivalent to: If form (a×bn+c)/gcd(a+c,b−1) (with fixed integers a ≥ 1, b ≥ 2, c ≠ 0 (with gcd(a,c) = 1 and gcd(b,c) = 1), and variable n) cannot be proven to only contain composites or only contain finitely many primes (by covering congruence, algebraic factorization, or combine of them), then form (a×bn+c)/gcd(a+c,b−1) contains infinitely many primes)
(this conjecture (https://en.wikipedia.org/wiki/Conjecture, https://primes.utm.edu/glossary/xpage/Conjecture.html, https://mathworld.wolfram.com/Conjecture.html) is very important for the problem in this article, since if this conjecture is in fact false, then there will may be some unsolved families which in fact contain no primes, thus the problem in this article in corresponding bases b will may be unsolvable (at least in current technology, unless someone find a new theorem (i.e. other than covering congruence, algebraic factorization, or combine of them) to prove that some families contain no primes, but I do not think that this is possible), however, this conjecture is currently to far to prove, much far than the Bunyakovsky conjecture (https://en.wikipedia.org/wiki/Bunyakovsky_conjecture, https://mathworld.wolfram.com/BouniakowskyConjecture.html) and even the Schinzel's hypothesis H (https://en.wikipedia.org/wiki/Schinzel%27s_hypothesis_H, https://mathworld.wolfram.com/SchinzelsHypothesis.html, http://www.numericana.com/answer/open.htm#h), besides, this conjecture is reasonable, since there is a heuristic argument (https://en.wikipedia.org/wiki/Heuristic_argument, https://primes.utm.edu/glossary/xpage/Heuristic.html, https://mathworld.wolfram.com/Heuristic.html, http://www.utm.edu/~caldwell/preprints/Heuristics.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_112.pdf)) that all families which cannot be ruled out as only containing composites or only containing finitely many primes (by covering congruence, algebraic factorization, or combine of them) contain infinitely many primes (references: https://primes.utm.edu/mersenne/heuristic.html, https://primes.utm.edu/notes/faq/NextMersenne.html, https://web.archive.org/web/20100628035147/http://www.math.niu.edu/~rusin/known-math/98/exp_primes, https://mersenneforum.org/showpost.php?p=564786&postcount=3, https://mersenneforum.org/showpost.php?p=461665&postcount=7), since by the prime number theorem (https://en.wikipedia.org/wiki/Prime_number_theorem, https://primes.utm.edu/glossary/xpage/PrimeNumberThm.html, https://mathworld.wolfram.com/PrimeNumberTheorem.html, https://primes.utm.edu/howmany.html, http://www.numericana.com/answer/primes.htm#pnt, https://oeis.org/wiki/User:Charles_R_Greathouse_IV/Tables_of_special_primes) the chance (https://en.wikipedia.org/wiki/Probability, https://mathworld.wolfram.com/Probability.html) that a random (https://en.wikipedia.org/wiki/Random_number, https://mathworld.wolfram.com/RandomNumber.html) n-digit base b number is prime is approximately (https://en.wikipedia.org/wiki/Asymptotic_analysis, https://primes.utm.edu/glossary/xpage/AsymptoticallyEqual.html, https://mathworld.wolfram.com/Asymptotic.html) 1/n (more accurately, the chance is approximately 1/(n×ln(b)), where ln is the natural logarithm (https://en.wikipedia.org/wiki/Natural_logarithm, https://primes.utm.edu/glossary/xpage/Log.html, https://mathworld.wolfram.com/NaturalLogarithm.html), i.e. the logarithm with base e = 2.718281828459... (https://en.wikipedia.org/wiki/E_(mathematical_constant), https://mathworld.wolfram.com/e.html)). If one conjectures the numbers xynz behave similarly you would expect 1/1 + 1/2 + 1/3 + 1/4 + ... = ∞ (https://en.wikipedia.org/wiki/Harmonic_series_(mathematics), https://mathworld.wolfram.com/HarmonicSeries.html) primes of the form xynz)
(this conjecture is for exponential sequences (https://en.wikipedia.org/wiki/Exponential_growth, https://mathworld.wolfram.com/ExponentialGrowth.html) (a×bn+c)/gcd(a+c,b−1) (with fixed integers a ≥ 1, b ≥ 2, c ≠ 0, gcd(a, c) = 1, gcd(b, c) = 1, and variable n), there is also a similar conjecture for polynomial sequences (https://en.wikipedia.org/wiki/Polynomial, https://mathworld.wolfram.com/Polynomial.html) a0+a1x+a2x2+a3x3+...+an−1xn−1+anxn (with fixed n, a0, a1, a2, ..., an and variable x): the Bunyakovsky conjecture (https://en.wikipedia.org/wiki/Bunyakovsky_conjecture, https://mathworld.wolfram.com/BouniakowskyConjecture.html), the condition is similar to this conjecture (divisible by small primes and algebraic factorizations), the main difference is that polynomial sequence cannot have a covering congruence with > 1 primes, nor have a combine of covering congruence and algebraic factorization)
This conjecture will imply:
- There are infinitely many Mersenne primes (i.e. primes of the form 2p−1 with prime p) (https://en.wikipedia.org/wiki/Mersenne_prime, https://primes.utm.edu/glossary/xpage/MersenneNumber.html, https://primes.utm.edu/glossary/xpage/Mersennes.html, https://www.rieselprime.de/ziki/Mersenne_number, https://www.rieselprime.de/ziki/Mersenne_prime, https://mathworld.wolfram.com/MersenneNumber.html, https://mathworld.wolfram.com/MersennePrime.html, https://pzktupel.de/Primetables/TableMe1.php, https://primes.utm.edu/top20/page.php?id=4, https://www.mersenne.org/, https://www.mersenne.org/primes/, https://www.mersenne.ca/, https://primes.utm.edu/mersenne/) (https://oeis.org/A001348, https://oeis.org/A000668, https://oeis.org/A000043)
- There are infinitely many Fermat primes (i.e. primes of the form 22n+1) (https://en.wikipedia.org/wiki/Fermat_number, https://primes.utm.edu/glossary/xpage/FermatNumber.html, https://www.rieselprime.de/ziki/Fermat_number, https://mathworld.wolfram.com/FermatNumber.html, https://mathworld.wolfram.com/FermatPrime.html, https://pzktupel.de/Primetables/TableFe1.php, http://www.prothsearch.com/fermat.html, http://www.fermatsearch.org/) (https://oeis.org/A000215, https://oeis.org/A019434)
- There are infinitely many generalized repunit primes (i.e. primes of the form (bp−1)/(b−1) with prime p) (https://en.wikipedia.org/wiki/Repunit, https://primes.utm.edu/glossary/xpage/Repunit.html, https://primes.utm.edu/glossary/xpage/GeneralizedRepunitPrime.html, https://www.rieselprime.de/ziki/Repunit, https://mathworld.wolfram.com/Repunit.html, https://mathworld.wolfram.com/RepunitPrime.html, https://pzktupel.de/Primetables/TableRp1.php, https://www.numbersaplenty.com/set/repunit/, https://stdkmd.net/nrr/repunit/repunitnote.htm#repunit, https://web.archive.org/web/20021001222643/http://www.users.globalnet.co.uk/~aads/index.html, https://web.archive.org/web/20021111141203/http://www.users.globalnet.co.uk/~aads/primes.html, https://web.archive.org/web/20021114005730/http://www.users.globalnet.co.uk/~aads/titans.html, https://web.archive.org/web/20021015210104/http://www.users.globalnet.co.uk/~aads/faclist.html, http://www.elektrosoft.it/matematica/repunit/repunit.htm, http://www.fermatquotient.com/PrimSerien/GenRepu.txt (in German), http://www.primenumbers.net/Henri/us/MersFermus.htm, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;417ab0d6.0906, http://www.bitman.name/math/article/380/231/, http://www.bitman.name/math/table/379, https://www.ams.org/journals/mcom/1993-61-204/S0025-5718-1993-1185243-9/S0025-5718-1993-1185243-9.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_4.pdf), https://www.ams.org/journals/mcom/1979-33-148/S0025-5718-1979-0537980-7/S0025-5718-1979-0537980-7.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_119.pdf), https://primes.utm.edu/top20/page.php?id=57, https://primes.utm.edu/top20/page.php?id=16, https://oeis.org/A002275) to every base b ≥ 2 which is not a perfect power (i.e. of the form mr with r > 1) (https://oeis.org/A001597, https://en.wikipedia.org/wiki/Perfect_power, https://mathworld.wolfram.com/PerfectPower.html, https://www.numbersaplenty.com/set/perfect_power/) (https://oeis.org/A084740, https://oeis.org/A084738, https://oeis.org/A246005, https://oeis.org/A065854, https://oeis.org/A279068, https://oeis.org/A065813, https://oeis.org/A128164, https://oeis.org/A285642)
- There are infinitely many generalized Wagstaff primes (i.e. primes of the form (bp+1)/(b+1) with odd prime p) (https://en.wikipedia.org/wiki/Wagstaff_prime, https://primes.utm.edu/glossary/xpage/WagstaffPrime.html, https://mathworld.wolfram.com/WagstaffPrime.html, https://pzktupel.de/Primetables/TableWa1.php, https://web.archive.org/web/20211031110623/http://mprime.s3-website.us-west-1.amazonaws.com/wagstaff/, http://www.fermatquotient.com/PrimSerien/GenRepuP.txt (in German), http://www.primenumbers.net/Henri/us/MersFermus.htm, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;417ab0d6.0906, http://www.bitman.name/math/table/488, https://cs.uwaterloo.ca/journals/JIS/VOL3/DUBNER/dubner.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_5.pdf), https://primes.utm.edu/top20/page.php?id=67, https://oeis.org/A000979, https://oeis.org/A000978) to every base b ≥ 2 which is neither a perfect odd power (i.e. of the form mr with odd r > 1) (http://mathworld.wolfram.com/OddPower.html, https://oeis.org/A070265) nor of the form 4×m4 (https://oeis.org/A141046) (https://oeis.org/A084742, https://oeis.org/A084741, https://oeis.org/A126659, https://oeis.org/A065507)
- There are infinitely many generalized Fermat primes (i.e. primes of the form b2n+1 with even b) (https://primes.utm.edu/glossary/xpage/GeneralizedFermatNumber.html, https://primes.utm.edu/glossary/xpage/GeneralizedFermatPrime.html, https://www.rieselprime.de/ziki/Generalized_Fermat_number, https://mathworld.wolfram.com/GeneralizedFermatNumber.html, http://jeppesn.dk/generalized-fermat.html, http://www.noprimeleftbehind.net/crus/GFN-primes.htm, http://yves.gallot.pagesperso-orange.fr/primes/index.html, http://yves.gallot.pagesperso-orange.fr/primes/results.html, http://yves.gallot.pagesperso-orange.fr/primes/stat.html, http://www.primegrid.com/forum_thread.php?id=3980, http://www.primegrid.com/stats_genefer.php, https://primes.utm.edu/top20/page.php?id=12, http://www.prothsearch.com/fermat.html, http://www.prothsearch.com/GFN06.html, http://www.prothsearch.com/GFN10.html, http://www.prothsearch.com/GFN12.html, http://www.prothsearch.com/GFNfacs.html, http://www.prothsearch.com/GFNsmall.html) to every even base b ≥ 2 which is not a perfect odd power (i.e. of the form mr with odd r > 1) (http://mathworld.wolfram.com/OddPower.html, https://oeis.org/A070265) (https://oeis.org/A228101, https://oeis.org/A079706, https://oeis.org/A084712, https://oeis.org/A123669)
- There are infinitely many generalized half-Fermat primes (i.e. primes of the form (b2n+1)/2 with odd b) (http://www.fermatquotient.com/PrimSerien/GenFermOdd.txt (in German), http://www.prothsearch.com/GFN03.html, http://www.prothsearch.com/GFN05.html, http://www.prothsearch.com/GFN07.html, http://www.prothsearch.com/GFN11.html, http://www.prothsearch.com/GFNfacs.html, http://www.prothsearch.com/GFNsmall.html) to every odd base b ≥ 2 which is not a perfect odd power (i.e. of the form mr with odd r > 1) (http://mathworld.wolfram.com/OddPower.html, https://oeis.org/A070265)
- There are infinitely many Williams primes of the first kind (i.e. primes of the form (b−1)×bn−1) (https://harvey563.tripod.com/wills.txt, https://www.rieselprime.de/ziki/Williams_prime_MM_least, https://www.rieselprime.de/ziki/Williams_prime_MM_table, https://sites.google.com/view/williams-primes, http://matwbn.icm.edu.pl/ksiazki/aa/aa39/aa3912.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_9.pdf), https://www.ams.org/journals/mcom/2000-69-232/S0025-5718-00-01212-6/S0025-5718-00-01212-6.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_10.pdf), http://www.bitman.name/math/table/484 (in Italian)) to every base b ≥ 2 (https://oeis.org/A122396)
- There are infinitely many Williams primes of the second kind (i.e. primes of the form (b−1)×bn+1) (https://www.rieselprime.de/ziki/Williams_prime_MP_least, https://www.rieselprime.de/ziki/Williams_prime_MP_table, https://sites.google.com/view/williams-primes, http://www.bitman.name/math/table/477 (in Italian)) to every base b ≥ 2 (https://oeis.org/A305531, https://oeis.org/A087139) (warning: this may be false, (b−1)×bn+1 may be able to be proven to only contain composites by combine of covering congruence and algebraic factorization when b−1 is either a perfect odd power (i.e. of the form mr with odd r > 1) (http://mathworld.wolfram.com/OddPower.html, https://oeis.org/A070265) or of the form 4×m4 (https://oeis.org/A141046), but the smallest such base b will be very large, however, this is at least true for bases b such that b−1 is neither a perfect odd power (i.e. of the form mr with odd r > 1) (http://mathworld.wolfram.com/OddPower.html, https://oeis.org/A070265) nor of the form 4×m4 (https://oeis.org/A141046), also at least true for bases b ≤ 106)
- There are infinitely many dual Williams primes of the first kind (i.e. primes of the form bn−(b−1)) (https://sites.google.com/view/williams-primes, https://cs.uwaterloo.ca/journals/JIS/VOL3/mccranie.html, http://www.bitman.name/math/table/435 (in Italian)) to every base b ≥ 2 (https://oeis.org/A113516, https://oeis.org/A343589)
- There are infinitely many dual Williams primes of the second kind (i.e. primes of the form bn+(b−1)) (https://sites.google.com/view/williams-primes) to every base b ≥ 2 (https://oeis.org/A076845, https://oeis.org/A076846, https://oeis.org/A078178, https://oeis.org/A078179) (warning: this may be false, bn+(b−1) may be able to be proven to only contain composites by combine of covering congruence and algebraic factorization when b−1 is either a perfect odd power (i.e. of the form mr with odd r > 1) (http://mathworld.wolfram.com/OddPower.html, https://oeis.org/A070265) or of the form 4×m4 (https://oeis.org/A141046), but the smallest such base b will be very large, however, this is at least true for bases b such that b−1 is neither a perfect odd power (i.e. of the form mr with odd r > 1) (http://mathworld.wolfram.com/OddPower.html, https://oeis.org/A070265) nor of the form 4×m4 (https://oeis.org/A141046), also at least true for bases b ≤ 106)
- 78557 is the smallest Sierpinski number (i.e. odd numbers k such that k×2n+1 is composite for all n ≥ 1) (http://www.prothsearch.com/sierp.html, http://www.primegrid.com/forum_thread.php?id=1647, http://www.primegrid.com/forum_thread.php?id=972, http://www.primegrid.com/forum_thread.php?id=1750, http://www.primegrid.com/forum_thread.php?id=5758, http://www.primegrid.com/stats_sob_llr.php, http://www.primegrid.com/stats_psp_llr.php, http://www.primegrid.com/stats_esp_llr.php, https://web.archive.org/web/20160405211049/http://www.seventeenorbust.com/, https://en.wikipedia.org/wiki/Sierpi%C5%84ski_number, https://primes.utm.edu/glossary/xpage/SierpinskiNumber.html, https://www.rieselprime.de/ziki/Sierpi%C5%84ski_problem, https://www.rieselprime.de/ziki/Proth_2_Sierpinski, https://mathworld.wolfram.com/SierpinskiNumberoftheSecondKind.html, https://en.wikipedia.org/wiki/Seventeen_or_Bust, https://www.rieselprime.de/ziki/Seventeen_or_Bust, https://web.archive.org/web/20190929190947/https://primes.utm.edu/glossary/xpage/ColbertNumber.html, https://mathworld.wolfram.com/ColbertNumber.html, http://www.numericana.com/answer/primes.htm#sierpinski, http://www.bitman.name/math/article/204 (in Italian), https://oeis.org/A076336, https://oeis.org/A078680, https://oeis.org/A078683, https://oeis.org/A033809, https://oeis.org/A040076, https://oeis.org/A225721, https://oeis.org/A050921, https://oeis.org/A046067, https://oeis.org/A057025, https://oeis.org/A057192, https://oeis.org/A057247)
- 509203 is the smallest Riesel number (i.e. odd numbers k such that k×2n−1 is composite for all n ≥ 1) (http://www.prothsearch.com/rieselprob.html, http://www.primegrid.com/forum_thread.php?id=1731, http://www.primegrid.com/stats_trp_llr.php, https://web.archive.org/web/20061021153313/http://stats.rieselsieve.com//queue.php, https://en.wikipedia.org/wiki/Riesel_number, https://primes.utm.edu/glossary/xpage/RieselNumber.html, https://www.rieselprime.de/ziki/Riesel_problem, https://www.rieselprime.de/ziki/Riesel_2_Riesel, https://mathworld.wolfram.com/RieselNumber.html, http://www.bitman.name/math/article/203 (in Italian), https://oeis.org/A076337, https://oeis.org/A101036, https://oeis.org/A050412, https://oeis.org/A052333, https://oeis.org/A108129, https://oeis.org/A040081, https://oeis.org/A038699, https://oeis.org/A046069, https://oeis.org/A057026, https://oeis.org/A128979, https://oeis.org/A101050)
- 125050976086 is the smallest generalized Sierpinski number to base 3 (i.e. numbers k such that gcd(k+1, 3−1) = 1 and k×3n+1 is composite for all n ≥ 1) (http://www.noprimeleftbehind.net/crus/Sierp-conjectures.htm, http://www.noprimeleftbehind.net/crus/Sierp-conjectures-powers2.htm, http://www.noprimeleftbehind.net/crus/Sierp-conjecture-reserves.htm, http://www.noprimeleftbehind.net/crus/vstats_new/all_ck_sierpinski.txt, https://www.utm.edu/staff/caldwell/preprints/2to100.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_3.pdf), http://www.bitman.name/math/article/1259 (in Italian), https://oeis.org/A123159, https://oeis.org/A291437, https://oeis.org/A291438)
- 63064644938 is the smallest generalized Riesel number to base 3 (i.e. numbers k such that gcd(k−1, 3−1) = 1 and k×3n−1 is composite for all n ≥ 1) (http://www.noprimeleftbehind.net/crus/Riesel-conjectures.htm, http://www.noprimeleftbehind.net/crus/Riesel-conjectures-powers2.htm, http://www.noprimeleftbehind.net/crus/Riesel-conjecture-reserves.htm, http://www.noprimeleftbehind.net/crus/vstats_new/all_ck_riesel.txt, https://oeis.org/A273987)
- 66741 is the smallest generalized Sierpinski number to base 4 (i.e. numbers k such that gcd(k+1, 4−1) = 1 and k×4n+1 is composite for all n ≥ 1) (http://www.noprimeleftbehind.net/crus/Sierp-conjectures.htm, http://www.noprimeleftbehind.net/crus/Sierp-conjectures-powers2.htm, http://www.noprimeleftbehind.net/crus/Sierp-conjecture-reserves.htm, http://www.noprimeleftbehind.net/crus/vstats_new/all_ck_sierpinski.txt, https://www.utm.edu/staff/caldwell/preprints/2to100.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_3.pdf), http://www.bitman.name/math/article/1259 (in Italian), https://oeis.org/A123159, https://oeis.org/A251057, https://oeis.org/A256002, http://www.rieselprime.de/Related/LiskovetsGallot.htm, https://primepuzzles.net/problems/prob_036.htm)
- 39939 is the smallest non-square generalized Riesel number to base 4 (i.e. numbers k such that gcd(k−1, 4−1) = 1 and k×4n−1 is composite for all n ≥ 1) (http://www.noprimeleftbehind.net/crus/Riesel-conjectures.htm, http://www.noprimeleftbehind.net/crus/Riesel-conjectures-powers2.htm, http://www.noprimeleftbehind.net/crus/Riesel-conjecture-reserves.htm, http://www.noprimeleftbehind.net/crus/vstats_new/all_ck_riesel.txt, https://oeis.org/A273987, https://oeis.org/A251757, http://www.rieselprime.de/Related/LiskovetsGallot.htm, https://primepuzzles.net/problems/prob_036.htm)
- 159986 is the smallest generalized Sierpinski number to base 5 (i.e. numbers k such that gcd(k+1, 5−1) = 1 and k×5n+1 is composite for all n ≥ 1) (http://www.noprimeleftbehind.net/crus/Sierp-conjectures.htm, http://www.noprimeleftbehind.net/crus/Sierp-conjectures-powers2.htm, http://www.noprimeleftbehind.net/crus/Sierp-conjecture-reserves.htm, http://www.noprimeleftbehind.net/crus/vstats_new/all_ck_sierpinski.txt, https://www.utm.edu/staff/caldwell/preprints/2to100.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_3.pdf), http://www.bitman.name/math/article/1259 (in Italian), https://oeis.org/A123159, http://www.primegrid.com/forum_thread.php?id=5087, http://www.primegrid.com/stats_sr5_llr.php, https://web.archive.org/web/20131016004333/http://www.sr5.psp-project.de/, https://oeis.org/A345698)
- 346802 is the smallest generalized Riesel number to base 5 (i.e. numbers k such that gcd(k−1, 5−1) = 1 and k×5n−1 is composite for all n ≥ 1) (http://www.noprimeleftbehind.net/crus/Riesel-conjectures.htm, http://www.noprimeleftbehind.net/crus/Riesel-conjectures-powers2.htm, http://www.noprimeleftbehind.net/crus/Riesel-conjecture-reserves.htm, http://www.noprimeleftbehind.net/crus/vstats_new/all_ck_riesel.txt, https://oeis.org/A273987, http://www.primegrid.com/forum_thread.php?id=5087, http://www.primegrid.com/stats_sr5_llr.php, https://web.archive.org/web/20131016004333/http://www.sr5.psp-project.de/, https://oeis.org/A345403)
- 174308 is the smallest generalized Sierpinski number to base 6 (i.e. numbers k such that gcd(k+1, 6−1) = 1 and k×6n+1 is composite for all n ≥ 1) (http://www.noprimeleftbehind.net/crus/Sierp-conjectures.htm, http://www.noprimeleftbehind.net/crus/Sierp-conjectures-powers2.htm, http://www.noprimeleftbehind.net/crus/Sierp-conjecture-reserves.htm, http://www.noprimeleftbehind.net/crus/vstats_new/all_ck_sierpinski.txt, https://www.utm.edu/staff/caldwell/preprints/2to100.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_3.pdf), http://www.bitman.name/math/article/1259 (in Italian), https://oeis.org/A123159, https://oeis.org/A244549, https://oeis.org/A250204)
- 84687 is the smallest generalized Riesel number to base 6 (i.e. numbers k such that gcd(k−1, 6−1) = 1 and k×6n−1 is composite for all n ≥ 1) (http://www.noprimeleftbehind.net/crus/Riesel-conjectures.htm, http://www.noprimeleftbehind.net/crus/Riesel-conjectures-powers2.htm, http://www.noprimeleftbehind.net/crus/Riesel-conjecture-reserves.htm, http://www.noprimeleftbehind.net/crus/vstats_new/all_ck_riesel.txt, https://oeis.org/A273987, https://oeis.org/A244351, https://oeis.org/A250205)
- 1112646039348 is the smallest generalized Sierpinski number to base 7 (i.e. numbers k such that gcd(k+1, 7−1) = 1 and k×7n+1 is composite for all n ≥ 1) (http://www.noprimeleftbehind.net/crus/Sierp-conjectures.htm, http://www.noprimeleftbehind.net/crus/Sierp-conjectures-powers2.htm, http://www.noprimeleftbehind.net/crus/Sierp-conjecture-reserves.htm, http://www.noprimeleftbehind.net/crus/vstats_new/all_ck_sierpinski.txt, https://www.utm.edu/staff/caldwell/preprints/2to100.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_3.pdf), http://www.bitman.name/math/article/1259 (in Italian), https://oeis.org/A123159)
- 408034255082 is the smallest generalized Riesel number to base 7 (i.e. numbers k such that gcd(k−1, 7−1) = 1 and k×7n−1 is composite for all n ≥ 1) (http://www.noprimeleftbehind.net/crus/Riesel-conjectures.htm, http://www.noprimeleftbehind.net/crus/Riesel-conjectures-powers2.htm, http://www.noprimeleftbehind.net/crus/Riesel-conjecture-reserves.htm, http://www.noprimeleftbehind.net/crus/vstats_new/all_ck_riesel.txt, https://oeis.org/A273987)
- 2344 is the smallest generalized Sierpinski number to base 9 (i.e. numbers k such that gcd(k+1, 9−1) = 1 and k×9n+1 is composite for all n ≥ 1) (http://www.noprimeleftbehind.net/crus/Sierp-conjectures.htm, http://www.noprimeleftbehind.net/crus/Sierp-conjectures-powers2.htm, http://www.noprimeleftbehind.net/crus/Sierp-conjecture-reserves.htm, http://www.noprimeleftbehind.net/crus/vstats_new/all_ck_sierpinski.txt, https://www.utm.edu/staff/caldwell/preprints/2to100.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_3.pdf), http://www.bitman.name/math/article/1259 (in Italian), https://oeis.org/A123159)
- 9175 is the smallest generalized Sierpinski number to base 10 (i.e. numbers k such that gcd(k+1, 10−1) = 1 and k×10n+1 is composite for all n ≥ 1) (http://www.noprimeleftbehind.net/crus/Sierp-conjectures.htm, http://www.noprimeleftbehind.net/crus/Sierp-conjectures-powers2.htm, http://www.noprimeleftbehind.net/crus/Sierp-conjecture-reserves.htm, http://www.noprimeleftbehind.net/crus/vstats_new/all_ck_sierpinski.txt, https://www.utm.edu/staff/caldwell/preprints/2to100.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_3.pdf), http://www.bitman.name/math/article/1259 (in Italian), https://oeis.org/A123159, https://oeis.org/A243969)
- 10176 is the smallest generalized Riesel number to base 10 (i.e. numbers k such that gcd(k−1, 10−1) = 1 and k×10n−1 is composite for all n ≥ 1) (http://www.noprimeleftbehind.net/crus/Riesel-conjectures.htm, http://www.noprimeleftbehind.net/crus/Riesel-conjectures-powers2.htm, http://www.noprimeleftbehind.net/crus/Riesel-conjecture-reserves.htm, http://www.noprimeleftbehind.net/crus/vstats_new/all_ck_riesel.txt, https://oeis.org/A273987, https://oeis.org/A243974)
- 78557 is the smallest dual Sierpinski number (i.e. odd numbers k such that 2n+k is composite for all n ≥ 1) (http://www.kurims.kyoto-u.ac.jp/EMIS/journals/INTEGERS/papers/i61/i61.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_1.pdf), https://www.rechenkraft.net/wiki/Five_or_Bust, https://oeis.org/A076336/a076336c.html, http://www.mit.edu/~kenta/three/prime/dual-sierpinski/ezgxggdm/dualsierp-excerpt.txt, http://mit.edu/kenta/www/three/prime/dual-sierpinski/ezgxggdm/dualsierp.txt.gz, https://mersenneforum.org/showthread.php?t=10761, https://oeis.org/A067760, https://oeis.org/A123252, https://oeis.org/A094076, https://oeis.org/A139758)
- 509203 is the smallest dual Riesel number (i.e. odd numbers k such that 2n−k is composite for all n ≥ 1 such that 2n > k) (https://mersenneforum.org/showthread.php?t=6545, https://oeis.org/A096502, https://oeis.org/A096822, https://oeis.org/A101462)
- 125050976086 is the smallest generalized dual Sierpinski number to base 3 (i.e. numbers k such that gcd(k, 3) = 1 and gcd(k+1, 3−1) = 1 and 3n+k is composite for all n ≥ 1)
- 63064644938 is the smallest generalized dual Riesel number to base 3 (i.e. numbers k such that gcd(k, 3) = 1 and gcd(k−1, 3−1) = 1 and 3n−k is composite for all n ≥ 1 such that 3n > k)
- 159986 is the smallest generalized dual Sierpinski number to base 5 (i.e. numbers k such that gcd(k, 5) = 1 and gcd(k+1, 5−1) = 1 and 5n+k is composite for all n ≥ 1)
- 346802 is the smallest generalized dual Riesel number to base 5 (i.e. numbers k such that gcd(k, 5) = 1 and gcd(k−1, 5−1) = 1 and 5n−k is composite for all n ≥ 1 such that 5n > k)
- 1112646039348 is the smallest generalized dual Sierpinski number to base 7 (i.e. numbers k such that gcd(k, 7) = 1 and gcd(k+1, 7−1) = 1 and 7n+k is composite for all n ≥ 1)
- 408034255082 is the smallest generalized dual Riesel number to base 7 (i.e. numbers k such that gcd(k, 7) = 1 and gcd(k−1, 7−1) = 1 and 7n−k is composite for all n ≥ 1 such that 7n > k)
- 201446503145165177 is the smallest reverse Sierpinski base to k = 2 (i.e. bases b such that gcd(2+1, b−1) = 1 and 2×bn+1 is composite for all n ≥ 1) (https://scholar.rose-hulman.edu/cgi/viewcontent.cgi?article=1165&context=rhumj (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_2.pdf), https://mersenneforum.org/showthread.php?t=6918, https://mersenneforum.org/showthread.php?t=19725, https://www.rieselprime.de/ziki/Proth_prime_small_bases_least_n, https://mersenneforum.org/showthread.php?t=10354, https://oeis.org/A119624, https://oeis.org/A253178, https://oeis.org/A098872)
- There are no reverse Riesel bases to k = 2 (i.e. bases b such that gcd(2−1, b−1) = 1 and 2×bn−1 is composite for all n ≥ 1) (https://mersenneforum.org/showthread.php?t=24576, https://www.mersenneforum.org/attachment.php?attachmentid=20976&d=1567314217, https://oeis.org/A119591, https://oeis.org/A098873, https://www.rieselprime.de/ziki/Riesel_prime_small_bases_least_n, https://mersenneforum.org/showthread.php?t=10354)
- There are no reverse Sierpinski bases to k = 3 (i.e. bases b such that gcd(3+1, b−1) = 1 and 3×bn+1 is composite for all n ≥ 1) (https://scholar.rose-hulman.edu/cgi/viewcontent.cgi?article=1165&context=rhumj (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_2.pdf), https://www.rieselprime.de/ziki/Proth_prime_small_bases_least_n, https://mersenneforum.org/showthread.php?t=10354, https://oeis.org/A098877)
- There are no reverse Riesel bases to k = 3 (i.e. bases b such that gcd(3−1, b−1) = 1 and 3×bn−1 is composite for all n ≥ 1) (https://www.rieselprime.de/ziki/Riesel_prime_small_bases_least_n, https://mersenneforum.org/showthread.php?t=10354, https://oeis.org/A098876)
- 140324348 is the smallest reverse Sierpinski base to k = 5 (i.e. bases b such that gcd(5+1, b−1) = 1 and 5×bn+1 is composite for all n ≥ 1) (https://scholar.rose-hulman.edu/cgi/viewcontent.cgi?article=1165&context=rhumj (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_2.pdf), https://www.rieselprime.de/ziki/Proth_prime_small_bases_least_n, https://mersenneforum.org/showthread.php?t=10354)
- There are no reverse Riesel bases to k = 5 (i.e. bases b such that gcd(5−1, b−1) = 1 and 5×bn−1 is composite for all n ≥ 1) (https://www.rieselprime.de/ziki/Riesel_prime_small_bases_least_n, https://mersenneforum.org/showthread.php?t=10354)
- There are no reverse Sierpinski bases to k = 7 (i.e. bases b such that gcd(7+1, b−1) = 1 and 7×bn+1 is composite for all n ≥ 1) (https://scholar.rose-hulman.edu/cgi/viewcontent.cgi?article=1165&context=rhumj (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_2.pdf), https://www.rieselprime.de/ziki/Proth_prime_small_bases_least_n, https://mersenneforum.org/showthread.php?t=10354)
- 9162668342 is the smallest reverse Riesel base to k = 7 (i.e. bases b such that gcd(7−1, b−1) = 1 and 7×bn−1 is composite for all n ≥ 1) (https://www.rieselprime.de/ziki/Riesel_prime_small_bases_least_n, https://mersenneforum.org/showthread.php?t=10354)
- 177744 is the smallest reverse Sierpinski base to k = 9 (i.e. bases b such that gcd(9+1, b−1) = 1 and 9×bn+1 is composite for all n ≥ 1) (https://scholar.rose-hulman.edu/cgi/viewcontent.cgi?article=1165&context=rhumj (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_2.pdf), https://www.rieselprime.de/ziki/Proth_prime_small_bases_least_n, https://mersenneforum.org/showthread.php?t=10354)
- There are no reverse Riesel bases to k = 9 (i.e. bases b such that gcd(9−1, b−1) = 1 and 9×bn−1 is composite for all n ≥ 1) (https://www.rieselprime.de/ziki/Riesel_prime_small_bases_least_n, https://mersenneforum.org/showthread.php?t=10354) except the even square bases b and the bases b == 4 mod 10
- 201446503145165177 is the smallest dual reverse Sierpinski base to k = 2 (i.e. bases b such that gcd(2, b) = 1 and gcd(2+1, b−1) = 1 and bn+2 is composite for all n ≥ 1) (https://oeis.org/A138066, https://oeis.org/A084713, https://oeis.org/A138067)
- There are no dual reverse Riesel bases to k = 2 (i.e. bases b such that gcd(2, b) = 1 and gcd(2−1, b−1) = 1 and bn−2 is composite for all n ≥ 1) (https://www.primepuzzles.net/puzzles/puzz_887.htm, https://oeis.org/A255707, https://oeis.org/A084714, https://oeis.org/A250200, https://oeis.org/A292201)
- There are no dual reverse Sierpinski bases to k = 3 (i.e. bases b such that gcd(3, b) = 1 and gcd(3+1, b−1) = 1 and bn+3 is composite for all n ≥ 1)
- There are no dual reverse Riesel bases to k = 3 (i.e. bases b such that gcd(3, b) = 1 and gcd(3−1, b−1) = 1 and bn−3 is composite for all n ≥ 1)
- 140324348 is the smallest dual reverse Sierpinski base to k = 5 (i.e. bases b such that gcd(5, b) = 1 and gcd(5+1, b−1) = 1 and bn+5 is composite for all n ≥ 1)
- There are no dual reverse Riesel bases to k = 5 (i.e. bases b such that gcd(5, b) = 1 and gcd(5−1, b−1) = 1 and bn−5 is composite for all n ≥ 1)
- There are no dual reverse Sierpinski bases to k = 7 (i.e. bases b such that gcd(7, b) = 1 and gcd(7+1, b−1) = 1 and bn+7 is composite for all n ≥ 1)
- 9162668342 is the smallest dual reverse Riesel base to k = 7 (i.e. bases b such that gcd(7, b) = 1 and gcd(7−1, b−1) = 1 and bn−7 is composite for all n ≥ 1)
We call families of the form x{y}z (where x and z are strings (may be empty) of digits in base b, y is a digit in base b) "linear" families. Our algorithm then proceeds as follows:
- M := {minimal primes in base b of length 2 or 3}, L := union of all x{Y}z such that x ≠ 0 and gcd(z, b) = 1 and Y is the set of digits y such that xyz has no subsequence in M
- While L contains non-simple families: Explore each family of L, and update L. Examine each family of L by: 2.1. Let w be the shortest string in the family. If w has a subsequence in M, then remove the family from L. If w represents a prime, then add w to M and remove the family from L. 2.2. If possible, simplify the family. 2.3. Using the techniques below (covering congruence, algebraic factorization, or combine of them), check if the family can be proven to only contain composites, and if so then remove the family from L.
- Update L, after each split examine the new families as in step 2.
The process of exploring/examining/splitting a family can be concisely expressed in a tree of decompositions.
Some x{y}z (where x and z are strings (may be empty) of digits in base b, y is a digit in base b) families can be proven to contain no primes > b, by covering congruence (http://irvinemclean.com/maths/siercvr.htm, http://web.archive.org/web/20060925100410/http://www.glasgowg43.freeserve.co.uk/siernums.htm, https://web.archive.org/web/20061116164533/http://www.glasgowg43.freeserve.co.uk/brier2.htm, https://sites.google.com/site/robertgerbicz/coveringsets, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/coveringsets, http://www.numericana.com/answer/primes.htm#sierpinski, http://www.iakovlev.org/zip/riesel2.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_8.pdf), https://www.ams.org/journals/mcom/1975-29-129/S0025-5718-1975-0376583-0/S0025-5718-1975-0376583-0.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_27.pdf), https://www.ams.org/journals/mcom/1983-40-161/S0025-5718-1983-0679453-8/S0025-5718-1983-0679453-8.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_40.pdf), http://yves.gallot.pagesperso-orange.fr/papers/smallbrier.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_48.pdf), https://cs.uwaterloo.ca/journals/JIS/VOL16/Ismailescu/ismailescu3.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_51.pdf), https://arxiv.org/pdf/2209.10646.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_52.pdf), https://cs.uwaterloo.ca/journals/JIS/VOL18/Baczkowski/bacz2.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_61.pdf), https://arxiv.org/pdf/1110.4671.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_62.pdf), https://cs.uwaterloo.ca/journals/JIS/VOL14/Jones/jones12.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_80.pdf), https://web.archive.org/web/20081119135435/http://math.crg4.com/a094076.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_102.pdf), http://www.renyi.hu/~p_erdos/1950-07.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_103.pdf), http://www.kurims.kyoto-u.ac.jp/EMIS/journals/INTEGERS/papers/i61/i61.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_1.pdf), https://scholar.rose-hulman.edu/cgi/viewcontent.cgi?article=1165&context=rhumj (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_2.pdf), https://www.primepuzzles.net/puzzles/puzz_614.htm, http://www.primepuzzles.net/problems/prob_029.htm, http://www.primepuzzles.net/problems/prob_030.htm, http://www.primepuzzles.net/problems/prob_036.htm, http://www.primepuzzles.net/problems/prob_049.htm, https://www.rieselprime.de/Related/LiskovetsGallot.htm, https://www.rieselprime.de/Related/RieselTwinSG.htm, https://stdkmd.net/nrr/coveringset.htm, https://stdkmd.net/nrr/9/91113.htm#prime_period, https://stdkmd.net/nrr/9/94449.htm#prime_period, https://stdkmd.net/nrr/9/95559.htm#prime_period, https://web.archive.org/web/20070220134129/http://www.users.globalnet.co.uk/~perry/maths/wildeprimes/wildeprimes.htm, https://www.rose-hulman.edu/~rickert/Compositeseq/, https://oeis.org/A244561, https://oeis.org/A244562, https://oeis.org/A244563, https://oeis.org/A244564, https://oeis.org/A244070, https://oeis.org/A244071, https://oeis.org/A244072, https://oeis.org/A244073, https://en.wikipedia.org/wiki/Covering_set, https://www.rieselprime.de/ziki/Covering_set, https://mathworld.wolfram.com/SierpinskisCompositeNumberTheorem.html) (i.e. finding a finite set (https://en.wikipedia.org/wiki/Finite_set, https://mathworld.wolfram.com/FiniteSet.html) S of primes p such that all numbers in a given family are divisible (https://en.wikipedia.org/wiki/Divides, https://primes.utm.edu/glossary/xpage/Divides.html, https://primes.utm.edu/glossary/xpage/Divisor.html, https://www.rieselprime.de/ziki/Factor, https://mathworld.wolfram.com/Divides.html, https://mathworld.wolfram.com/Divisor.html, https://mathworld.wolfram.com/Divisible.html, http://www.numericana.com/answer/primes.htm#divisor) by some element of S (this is equivalent to finding a positive integer N such that all numbers in a given family are not coprime (https://en.wikipedia.org/wiki/Coprime_integers, https://primes.utm.edu/glossary/xpage/RelativelyPrime.html, https://www.rieselprime.de/ziki/Coprime, https://mathworld.wolfram.com/RelativelyPrime.html, http://www.numericana.com/answer/primes.htm#coprime) to N, e.g. all numbers in the family 2{5} in base 11 are not coprime to 6, gcd((5×11n−1)/2, 6) can only be 2 or 3, and cannot be 1), by modular arithmetic (https://en.wikipedia.org/wiki/Modular_arithmetic, https://en.wikipedia.org/wiki/Congruence_relation, https://en.wikipedia.org/wiki/Modulo, https://primes.utm.edu/glossary/xpage/Congruence.html, https://primes.utm.edu/glossary/xpage/CongruenceClass.html, https://primes.utm.edu/glossary/xpage/Residue.html, https://mathworld.wolfram.com/Congruence.html, https://mathworld.wolfram.com/Congruent.html, https://mathworld.wolfram.com/Residue.html, https://mathworld.wolfram.com/MinimalResidue.html, https://mathworld.wolfram.com/Mod.html)), algebraic factorization (https://en.wikipedia.org/w/index.php?title=Factorization&oldid=1143370673#Factoring_other_polynomials, https://mathworld.wolfram.com/PolynomialFactorization.html, http://www.numericana.com/answer/factoring.htm#special, https://stdkmd.net/nrr/repunit/repunitnote.htm, https://stdkmd.net/nrr/1/10004.htm#about_algebraic, https://stdkmd.net/nrr/1/10008.htm#about_algebraic, https://stdkmd.net/nrr/1/13333.htm#about_algebraic, https://stdkmd.net/nrr/4/40001.htm#about_algebraic, https://stdkmd.net/nrr/5/53333.htm#about_algebraic, https://stdkmd.net/nrr/5/54444.htm#about_algebraic, https://stdkmd.net/nrr/5/55552.htm#about_algebraic, https://stdkmd.net/nrr/7/79999.htm#about_algebraic, https://stdkmd.net/nrr/8/83333.htm#about_algebraic, https://stdkmd.net/nrr/8/88889.htm#about_algebraic, https://stdkmd.net/nrr/8/89999.htm#about_algebraic, https://stdkmd.net/nrr/9/99991.htm#about_algebraic, https://stdkmd.net/nrr/9/99992.htm#about_algebraic, https://brnikat.com/nums/cullen_woodall/algebraic.txt, https://www.numberempire.com/factoringcalculator.php (e.g. for the family 3{8} in base 9, type "4*9^n-1", and it will tell you that this form can be factored to (2×3n−1) × (2×3n+1)), https://www.emathhelp.net/calculators/algebra-2/factoring-calculator/) (which includes difference-of-two-squares factorization (https://en.wikipedia.org/wiki/Difference_of_two_squares) and sum/difference-of-two-cubes factorization (https://en.wikipedia.org/wiki/Sum_of_two_cubes) and difference-of-two-nth-powers factorization with n > 1 (https://en.wikipedia.org/wiki/Binomial_number, https://mathworld.wolfram.com/BinomialNumber.html) and sum/difference-of-two-nth-powers factorization with odd n > 1 (https://en.wikipedia.org/wiki/Binomial_number, https://mathworld.wolfram.com/BinomialNumber.html) and Aurifeuillean factorization (https://en.wikipedia.org/wiki/Aurifeuillean_factorization, https://www.rieselprime.de/ziki/Aurifeuillian_factor, https://mathworld.wolfram.com/AurifeuilleanFactorization.html, http://www.numericana.com/answer/numbers.htm#aurifeuille, http://pagesperso-orange.fr/colin.barker/lpa/cycl_fac.htm, http://list.seqfan.eu/oldermail/seqfan/2017-March/017363.html, http://myfactorcollection.mooo.com:8090/source/cyclo.cpp, http://myfactorcollection.mooo.com:8090/LCD_2_199, http://myfactorcollection.mooo.com:8090/LCD_2_998, https://stdkmd.net/nrr/repunit/repunitnote.htm#aurifeuillean, https://www.unshlump.com/hcn/aurif.html) of x4+4×y4 or x6+27×y6), or combine of them (https://mersenneforum.org/showthread.php?t=11143, https://mersenneforum.org/showthread.php?t=10279, https://www.fq.math.ca/Scanned/33-3/izotov.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_46.pdf), https://doi.org/10.1016/j.jnt.2008.02.004 (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_47.pdf)), e.g. (only list the families which all numbers do not contain "prime > b" subsequence) (see post https://mersenneforum.org/showpost.php?p=594923&postcount=231 for the factor pattern for some of these families) (for the case of covering congruence, we can show that the corresponding numbers are > all elements in the sets if the corresponding numbers are > b, thus these factorizations are nontrivial; and for the case of algebraic factorization, we can show that both factors are > 1 if the corresponding numbers are > b, thus these factorizations are nontrivial; for the case of combine of them, we can show that for the part of covering congruence, the corresponding numbers are > all elements in the sets if the corresponding numbers are > b, and for the part of algebraic factorization, both factors are > 1 if the corresponding numbers are > b, thus these factorizations are nontrivial)
The multiplicative order (https://en.wikipedia.org/wiki/Multiplicative_order, https://primes.utm.edu/glossary/xpage/Order.html, https://mathworld.wolfram.com/MultiplicativeOrder.html, https://oeis.org/A250211, https://oeis.org/A139366, https://oeis.org/A086145) is very important in this problem, since if a prime p divides the number with n digits in family x{y}z in base b, then p also divides the number with k×ordp(b)+n digits in family x{y}z in base b for all nonnegative integer k (unless ordp(b) = 1, i.e. p divides b−1, in this case p also divides the number with k×p+n digits in family x{y}z in base b for all nonnegative integer k), the period of "divisible by p" for a prime p in family x{y}z in base b (if only some and not all numbers in family x{y}z in base b are divisible by p, of course, if all numbers in family x{y}z in base b are divisible by p, then the period of "divisible by p" for a prime p in family x{y}z in base b is 1) is ordp(b) (ordp(b) must divide p−1, if and only if ordp(b) is exactly p−1, then b is a primitive root (https://en.wikipedia.org/wiki/Primitive_root_modulo_n, https://mathworld.wolfram.com/PrimitiveRoot.html, https://oeis.org/A060749, https://oeis.org/A001918, https://oeis.org/A071894, https://oeis.org/A008330, https://oeis.org/A046147, https://oeis.org/A046145, https://oeis.org/A046146, https://oeis.org/A046144, https://oeis.org/A033948, https://oeis.org/A033949, http://www.bluetulip.org/2014/programs/primitive.html, http://www.numbertheory.org/php/lprimroot.html) mod p, and this is studying in Artin's conjecture on primitive roots (https://en.wikipedia.org/wiki/Artin%27s_conjecture_on_primitive_roots, https://mathworld.wolfram.com/ArtinsConjecture.html, http://www.numericana.com/answer/constants.htm#artin), which is an unsolved problem in mathematics) unless p divides b−1, in this case the period of "divisible by p" for such prime p in family x{y}z in base b is simply p, the primes p such that ordp(b) = n are exactly the prime factors of the Zsigmondy number (https://en.wikipedia.org/wiki/Zsigmondy%27s_theorem, https://mathworld.wolfram.com/ZsigmondyTheorem.html) Zs(n, b, 1), Zs(n, b, 1) = Φn(b)/gcd(Φn(b), n) (where Φ is the cyclotomic polynomial (https://en.wikipedia.org/wiki/Cyclotomic_polynomial, https://mathworld.wolfram.com/CyclotomicPolynomial.html, http://www.numericana.com/answer/polynomial.htm#cyclotomic, https://stdkmd.net/nrr/repunit/repunitnote.htm#cyclotomic) if n ≠ 2, Zs(n, 2, 1) = odd part (http://mathworld.wolfram.com/OddPart.html, https://oeis.org/A000265) of n+1, the prime factors of Zs(n, b, 1) for odd n are exactly the primitive prime factors of bn−1, the prime factors of Zs(n, b, 1) for even n are exactly the primitive prime factors of bn/2+1, references: https://en.wikipedia.org/w/index.php?title=Wikipedia:Sandbox&oldid=1039706119 (list of the ordp(b) for 2 ≤ b ≤ 128 and primes p ≤ 4096), https://en.wikipedia.org/w/index.php?title=Wikipedia:Sandbox&oldid=1040004339 (list of primes p such that ordp(b) = n for 2 ≤ b ≤ 64 and 1 ≤ n ≤ 64), also factorization of bn±1: https://homes.cerias.purdue.edu/~ssw/cun/index.html (2 ≤ b ≤ 12), https://homes.cerias.purdue.edu/~ssw/cun/pmain22.txt (2 ≤ b ≤ 12), https://doi.org/10.1090/conm/022 (2 ≤ b ≤ 12), https://www.mersenneforum.org/attachment.php?attachmentid=7727&d=1330555980 (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_7.pdf) (2 ≤ b ≤ 12), https://web.archive.org/web/20190315214330/http://cage.ugent.be/~jdemeyer/cunningham/ (2 ≤ b ≤ 12), https://maths-people.anu.edu.au/~brent/factors.html (13 ≤ b ≤ 99), https://stdkmd.net/nrr/repunit/ (b = 10), https://stdkmd.net/nrr/repunit/10001.htm (b = 10), https://stdkmd.net/nrr/repunit/phin10.htm (b = 10, only primitive factors), https://stdkmd.net/nrr/repunit/Phin10.txt (b = 10, only primitive factors), https://stdkmd.net/nrr/repunit/Phin10.txt.lz (b = 10, only primitive factors), https://stdkmd.net/nrr/repunit/Phin10.txt.gz (b = 10, only primitive factors), https://kurtbeschorner.de/ (b = 10), https://kurtbeschorner.de/fact-2500.htm (b = 10), https://repunit-koide.jimdofree.com/ (b = 10), https://repunit-koide.jimdofree.com/app/download/10034950550/Repunit100-20221222.pdf?t=1671715731 (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_26.pdf) (b = 10), https://gmplib.org/~tege/repunit.html (b = 10), https://gmplib.org/~tege/fac10m.txt (b = 10), https://gmplib.org/~tege/fac10p.txt (b = 10), https://web.archive.org/web/20120426061657/http://oddperfect.org/ (prime b), http://myfactors.mooo.com/ (any b), http://myfactorcollection.mooo.com:8090/dbio.html (any b), http://www.asahi-net.or.jp/~KC2H-MSM/cn/old/index.htm (any b, only primitive factors), http://www.asahi-net.or.jp/~KC2H-MSM/cn/index.htm (any b, only primitive factors), https://web.archive.org/web/20050922233702/http://user.ecc.u-tokyo.ac.jp/~g440622/cn/index.html (any b, only primitive factors), also for the factors of bn±1 with 2 ≤ b ≤ 100 and 1 ≤ n ≤ 100 see http://myfactorcollection.mooo.com:8090/cgi-bin/showFullRep?FBase=2&TBase=100&FExp=1&TExp=100&c0=&EN=&LM= (all factors) and http://myfactorcollection.mooo.com:8090/cgi-bin/showPrimFactors?FBase=2&TBase=100&FExp=1&TExp=100&c0=&LM= (only primitive factors); also, the period of "difference-of-two-squares factorization" in any base b is 2 if b is not square, 1 if b is square; the period of "sum/difference-of-two-pth-powers factorization with odd prime p" is p if b is not p-th power, 1 if b is p-th power; the period of "Aurifeuillean factorization of x4+4×y4" is 4 if b is not square, 2 if b is square but not 4-th power, 1 if b is 4-th power, (for more information, see https://stdkmd.net/nrr/1/10003.htm#prime_period, https://stdkmd.net/nrr/3/30001.htm#prime_period, https://stdkmd.net/nrr/1/13333.htm#prime_period, https://stdkmd.net/nrr/3/33331.htm#prime_period, https://stdkmd.net/nrr/1/11113.htm#prime_period, https://stdkmd.net/nrr/3/31111.htm#prime_period, https://oeis.org/A014664, https://oeis.org/A062117, https://oeis.org/A002371, http://www.noprimeleftbehind.net/crus/Sierp-conjectures.htm, http://www.noprimeleftbehind.net/crus/Riesel-conjectures.htm, http://www.noprimeleftbehind.net/crus/Sierp-conjectures-powers2.htm, http://www.noprimeleftbehind.net/crus/Riesel-conjectures-powers2.htm) the family x{y}z in base b can be proven to contain no primes > b (or only contain finitely many primes > b) if and only if these residue classes with these periods gives a complete residue system (https://en.wikipedia.org/wiki/Covering_system, https://mathworld.wolfram.com/CompleteResidueSystem.html).
We can show that: For the case of covering congruence, the numbers in the family are not equal to any element in S, if n makes the numbers > b, thus these factorizations are nontrivial; for the case of algebraic factorization (if the numbers are factored as F × G / d), both F and G are > d, if n makes the numbers > b, thus these factorizations are nontrivial (the exceptions are the base 9 family {1} and the base 25 family {1} and the base 32 family {1}. For the base 9 family {1}, the algebraic form is (9n−1)/8 with n ≥ 2, and can be factored to (3n−1) × (3n+1) / 8, if n ≥ 3, then both 3n−1 and 3n+1 are > 8, thus these factorizations are nontrivial, it only remains to check the case n = 2, but the number with n = 2 is 10 = 2 × 5 is not prime; for the base 25 family {1}, the algebraic form is (25n−1)/24 with n ≥ 2, and can be factored to (5n−1) × (5n+1) / 24, if n ≥ 3, then both 5n−1 and 5n+1 are > 24, thus these factorizations are nontrivial, it only remains to check the case n = 2, but the number with n = 2 is 26 = 2 × 13 is not prime; for the base 32 family {1}, the algebraic form is (32n−1)/31 with n ≥ 2, and can be factored to (2n−1) × (16n+8n+4n+2n+1) / 31, if n ≥ 6, then both 2n−1 and 16n+8n+4n+2n+1 are > 31, thus these factorizations are nontrivial, it only remains to check the cases n = 2, 3, 4, 5, but the numbers with n = 2, 3, 4, 5 are 33 = 3 × 11, 1057 = 7 × 151, 33825 = 3 × 52 × 11 × 41, 1082401 = 601 × 1801 are not primes); for the case of combine of covering congruence and algebraic factorization (if the numbers are factored as F × G / d), the numbers in the family are not equal to any element in S and both F and G are > d, if n makes the numbers > b, thus these factorizations are nontrivial.
type for proving the | possible bases b | such bases 2 ≤ b ≤ 36 |
---|---|---|
covering congruence with 1 prime | any base b (however, all such families in base b = 2 end with 0 and thus have trailing zeros (https://en.wikipedia.org/wiki/Trailing_zero) and thus not counted) |
(2), 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36 |
covering congruence with 2 primes | b such that b+1 is not a prime power (https://en.wikipedia.org/wiki/Prime_power, https://mathworld.wolfram.com/PrimePower.html) (however, the case b = 5 has only four such families: {1}3, {1}4, 3{1}, 4{1}, all of them are covered by the prime 111 (31 in decimal), thus the smallest base b with families which have covering congruence with 2 primes is b = 9) |
(5), 9, 11, 13, 14, 17, 19, 20, 21, 23, 25, 27, 29, 32, 33, 34, 35 |
covering congruence with 3 primes and period 3 | b such that omega(b2+b+1) ≥ 3 (where omega is the omega function (https://en.wikipedia.org/wiki/Prime_omega_function, https://oeis.org/A001221), the number of distinct primes dividing n) | 16, 25 |
covering congruence with 3 primes and period 4 | b such that b+1 is not a power of 2 (https://en.wikipedia.org/wiki/Power_of_two) and b2+1 is not a prime power (https://en.wikipedia.org/wiki/Prime_power, https://mathworld.wolfram.com/PrimePower.html) (however, bases b = 5, 8, 9, 11, 12, 18 has no such families, base 8 family 6{4}7 is covered by the prime 42207) |
(5), (8), (9), (11), (12), 13, 17, (18), 19, 21, 22, 23, 25, 27, 28, 29, 30, 32, 33, 34, 35 |
algebraic factorization with difference of two squares | b such that b is square (https://en.wikipedia.org/wiki/Square_number, https://www.rieselprime.de/ziki/Square_number, https://mathworld.wolfram.com/SquareNumber.html) (however, base b = 4 has no such families, the family {1} has the prime 11 (5 in decimal)) |
(4), 9, 16, 25, 36 |
algebraic factorization with difference of two cubes | b such that b is cube (https://en.wikipedia.org/wiki/Cube_(algebra), https://mathworld.wolfram.com/CubicNumber.html) | 8, 27 |
algebraic factorization with difference of two 5-th powers | b such that b is 5-th power (https://en.wikipedia.org/wiki/Fifth_power_(algebra)) | 32 |
algebraic factorization with x4+4y4 | b such that b is 4-th power (https://en.wikipedia.org/wiki/Fourth_power, https://mathworld.wolfram.com/BiquadraticNumber.html) | 16 |
combine of covering congruence with 1 prime and algebraic factorization with difference of two squares | b such that b is not square (https://en.wikipedia.org/wiki/Square_number, https://www.rieselprime.de/ziki/Square_number, https://mathworld.wolfram.com/SquareNumber.html) and b+1 has a prime factor p == 1 mod 4 | 12, 14, 19, 24, 28, 29, 33, 34 |
(You can see the factorization (https://en.wikipedia.org/wiki/Integer_factorization, https://www.rieselprime.de/ziki/Factorization, https://mathworld.wolfram.com/PrimeFactorization.html, https://mathworld.wolfram.com/PrimeFactorizationAlgorithms.html, http://www.numericana.com/answer/factoring.htm) of the numbers in these families in factordb (http://factordb.com/, https://www.rieselprime.de/ziki/Factoring_Database), you have to convert them to algebraic ((a×bn+c)/gcd(a+c,b−1)) form, and you will find that all numbers in these families have status (http://factordb.com/status.html, http://factordb.com/distribution.php) either "FF" or "CF", and no numbers in these families have status (http://factordb.com/status.html, http://factordb.com/distribution.php) "C" (i.e. in http://factordb.com/listtype.php?t=3) (of course, also no numbers in these families have status (http://factordb.com/status.html, http://factordb.com/distribution.php) "U", "P", "PRP" (i.e. in http://factordb.com/listtype.php?t=2, http://factordb.com/listtype.php?t=4, http://factordb.com/listtype.php?t=1), since all numbers in these families are known to be composite), and the sieve file for these families will be empty after sieving (https://www.rieselprime.de/ziki/Sieving, https://www.rieselprime.de/ziki/Sieving_a_range_of_sequences, https://mathworld.wolfram.com/Sieve.html, http://www.rechenkraft.net/yoyo/y_status_sieve.php) with SRSIEVE (https://www.bc-team.org/app.php/dlext/?cat=3, http://web.archive.org/web/20160922072340/https://sites.google.com/site/geoffreywalterreynolds/programs/, http://www.rieselprime.de/dl/CRUS_pack.zip, https://primes.utm.edu/bios/page.php?id=905, https://www.rieselprime.de/ziki/Srsieve, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/srsieve_1.1.4, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/sr1sieve_1.4.6, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/sr2sieve_2.0.0, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/srbsieve, https://github.com/xayahrainie4793/prime-programs-cached-copy/blob/main/mtsieve_2.4.1/srsieve2.exe, https://github.com/xayahrainie4793/prime-programs-cached-copy/blob/main/mtsieve_2.4.1/srsieve2cl.exe) if the sieving program (i.e. SRSIEVE) was updated so that it also removes the n such that a×bn+c has algebraic factors, and their Nash weight (https://www.rieselprime.de/ziki/Nash_weight, http://irvinemclean.com/maths/nash.htm, http://www.brennen.net/primes/ProthWeight.html, https://www.mersenneforum.org/showthread.php?t=11844, https://www.mersenneforum.org/showthread.php?t=2645, https://www.mersenneforum.org/showthread.php?t=7213, https://www.mersenneforum.org/showthread.php?t=18818, https://www.mersenneforum.org/showpost.php?p=421186&postcount=19, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/allnash, https://www.rieselprime.de/ziki/Riesel_2_Low-weight, https://www.rieselprime.de/ziki/Proth_2_Low-weight, https://www.rieselprime.de/ziki/Category:Riesel_2_Low-weight, https://www.rieselprime.de/ziki/Category:Proth_2_Low-weight, https://www.rieselprime.de/ziki/Category:Riesel_5_Low-weight, https://www.rieselprime.de/ziki/Category:Proth_5_Low-weight, http://www.noprimeleftbehind.net/crus/vstats_new/riesel_weights.txt, http://www.noprimeleftbehind.net/crus/vstats_new/sierpinski_weights.txt) (or difficulty (https://stdkmd.net/nrr/prime/primedifficulty.htm, https://stdkmd.net/nrr/prime/primedifficulty.txt, http://www.noprimeleftbehind.net/crus/vstats_new/crus-unproven.htm, http://www.noprimeleftbehind.net/crus/vstats_new/riesel_difficulty.txt, http://www.noprimeleftbehind.net/crus/vstats_new/sierpinski_difficulty.txt)) is zero, e.g. for the family 3{0}95 in base 13, its algebraic ((a×bn+c)/gcd(a+c,b−1)) form is 3×13n+2+122, and in factordb you will find that all numbers in this family are divisible by some element of {5,7,17}, see http://factordb.com/index.php?query=3*13%5E%28n%2B2%29%2B122&use=n&n=0&VP=on&VC=on&EV=on&OD=on&PR=on&FF=on&PRP=on&CF=on&U=on&C=on&perpage=200&format=1&sent=Show; for the family {7}D in base 21, its algebraic ((a×bn+c)/gcd(a+c,b−1)) form is (7×21n+1+113)/20, and in factordb you will find that all numbers in this family are divisible by some element of {2,13,17}, see http://factordb.com/index.php?query=%287*21%5E%28n%2B1%29%2B113%29%2F20&use=n&n=1&VP=on&VC=on&EV=on&OD=on&PR=on&FF=on&PRP=on&CF=on&U=on&C=on&perpage=200&format=1&sent=Show (note: for this family n = 0 is not allowed, since we only consider the numbers > base); for the family 30{F}A0F in base 16, its algebraic ((a×bn+c)/gcd(a+c,b−1)) form is 49×16n+3−1521, and in factordb you will find that no numbers in this family have a prime factor with decimal length > ((the decimal length of the number + 1)/2), and all numbers in this family have two nearly equal (prime or composite) factors, see http://factordb.com/index.php?query=49*16%5E%28n%2B3%29-1521&use=n&n=0&VP=on&VC=on&EV=on&OD=on&PR=on&FF=on&PRP=on&CF=on&U=on&C=on&perpage=200&format=1&sent=Show; for the family 5{1} in base 25, its algebraic ((a×bn+c)/gcd(a+c,b−1)) form is (121×25n−1)/24, and in factordb you will find that no numbers in this family have a prime factor with decimal length > ((the decimal length of the number + 1)/2), and all numbers in this family have two nearly equal (prime or composite) factors, see http://factordb.com/index.php?query=%28121*25%5En-1%29%2F24&use=n&n=1&VP=on&VC=on&EV=on&OD=on&PR=on&FF=on&PRP=on&CF=on&U=on&C=on&perpage=200&format=1&sent=Show (note: for this family n = 0 is not allowed, since we only consider the numbers > base); for the family {D}5 in base 14, its algebraic ((a×bn+c)/gcd(a+c,b−1)) form is 14n+1−9, and in factordb you will find that all numbers with even n in this family are divisible by 5, and you will find that no numbers with odd n in this family have a prime factor with decimal length > ((the decimal length of the number + 1)/2), and all numbers with odd n in this family have two nearly equal (prime or composite) factors, see http://factordb.com/index.php?query=14%5E%28n%2B1%29-9&use=n&n=1&VP=on&VC=on&EV=on&OD=on&PR=on&FF=on&PRP=on&CF=on&U=on&C=on&perpage=200&format=1&sent=Show (note: for this family n = 0 is not allowed, since we only consider the numbers > base); for the family 7{9} in base 17, its algebraic ((a×bn+c)/gcd(a+c,b−1)) form is (121×17n−9)/16, and in factordb you will find that all numbers with odd n in this family are divisible by 2, and you will find that no numbers with even n in this family have a prime factor with decimal length > ((the decimal length of the number + 1)/2), and all numbers with even n in this family have two nearly equal (prime or composite) factors, see http://factordb.com/index.php?query=%28121*17%5En-9%29%2F16&use=n&n=1&VP=on&VC=on&EV=on&OD=on&PR=on&FF=on&PRP=on&CF=on&U=on&C=on&perpage=200&format=1&sent=Show (note: for this family n = 0 is not allowed, since we only consider the numbers > base). In contrast, you can see the factorization of the numbers in unsolved families in base b (which are listed in the "left b" file) in factordb, you will find some numbers in these families which have neither small prime factors (say < 1016) nor two nearly equal (prime or composite) factors, also you will find some numbers in these families which have no known proper factor (https://en.wikipedia.org/wiki/Proper_factor, https://mathworld.wolfram.com/ProperFactor.html, https://mathworld.wolfram.com/ProperDivisor.html) > 1 (i.e. you will find some numbers in these families with status (http://factordb.com/status.html, http://factordb.com/distribution.php) "C" (instead of "CF" or "FF") (i.e. in http://factordb.com/listtype.php?t=3) (and maybe some large numbers in these families with status (http://factordb.com/status.html, http://factordb.com/distribution.php) "U", i.e. in http://factordb.com/listtype.php?t=2) in factordb (http://factordb.com/)), and the sieve file for these families will be empty after sieving (https://www.rieselprime.de/ziki/Sieving, https://www.rieselprime.de/ziki/Sieving_a_range_of_sequences, https://mathworld.wolfram.com/Sieve.html, http://www.rechenkraft.net/yoyo/y_status_sieve.php) with SRSIEVE (https://www.bc-team.org/app.php/dlext/?cat=3, http://web.archive.org/web/20160922072340/https://sites.google.com/site/geoffreywalterreynolds/programs/, http://www.rieselprime.de/dl/CRUS_pack.zip, https://primes.utm.edu/bios/page.php?id=905, https://www.rieselprime.de/ziki/Srsieve, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/srsieve_1.1.4, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/sr1sieve_1.4.6, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/sr2sieve_2.0.0, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/srbsieve, https://github.com/xayahrainie4793/prime-programs-cached-copy/blob/main/mtsieve_2.4.1/srsieve2.exe, https://github.com/xayahrainie4793/prime-programs-cached-copy/blob/main/mtsieve_2.4.1/srsieve2cl.exe) even if the sieving program (i.e. SRSIEVE) was updated so that it also removes the n such that a×bn+c has algebraic factors, and they have positive Nash weight (https://www.rieselprime.de/ziki/Nash_weight, http://irvinemclean.com/maths/nash.htm, http://www.brennen.net/primes/ProthWeight.html, https://www.mersenneforum.org/showthread.php?t=11844, https://www.mersenneforum.org/showthread.php?t=2645, https://www.mersenneforum.org/showthread.php?t=7213, https://www.mersenneforum.org/showthread.php?t=18818, https://www.mersenneforum.org/showpost.php?p=421186&postcount=19, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/allnash, https://www.rieselprime.de/ziki/Riesel_2_Low-weight, https://www.rieselprime.de/ziki/Proth_2_Low-weight, https://www.rieselprime.de/ziki/Category:Riesel_2_Low-weight, https://www.rieselprime.de/ziki/Category:Proth_2_Low-weight, https://www.rieselprime.de/ziki/Category:Riesel_5_Low-weight, https://www.rieselprime.de/ziki/Category:Proth_5_Low-weight, http://www.noprimeleftbehind.net/crus/vstats_new/riesel_weights.txt, http://www.noprimeleftbehind.net/crus/vstats_new/sierpinski_weights.txt) (or difficulty (https://stdkmd.net/nrr/prime/primedifficulty.htm, https://stdkmd.net/nrr/prime/primedifficulty.txt, http://www.noprimeleftbehind.net/crus/vstats_new/crus-unproven.htm, http://www.noprimeleftbehind.net/crus/vstats_new/riesel_difficulty.txt, http://www.noprimeleftbehind.net/crus/vstats_new/sierpinski_difficulty.txt)), and they have prime candidates, we can use the sense of http://www.iakovlev.org/zip/riesel2.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_8.pdf), https://stdkmd.net/nrr/1/10003.htm#prime_period, https://stdkmd.net/nrr/3/30001.htm#prime_period, https://stdkmd.net/nrr/1/13333.htm#prime_period, https://stdkmd.net/nrr/3/33331.htm#prime_period, https://stdkmd.net/nrr/1/11113.htm#prime_period, https://stdkmd.net/nrr/3/31111.htm#prime_period, https://mersenneforum.org/showpost.php?p=138737&postcount=24, https://mersenneforum.org/showpost.php?p=153508&postcount=147, to show this)
(for the examples of non-simple families, see https://stdkmd.net/nrr/prime/primecount3.htm and https://stdkmd.net/nrr/prime/primecount3.txt (only base 10 families), non-simple families usually have small primes if they cannot be ruled out as only containing composites by covering congruence, see the section above)
(for the factorization of the numbers in these families, the special number field sieve (https://en.wikipedia.org/wiki/Special_number_field_sieve, https://www.rieselprime.de/ziki/Special_number_field_sieve, https://mathworld.wolfram.com/NumberFieldSieve.html, https://stdkmd.net/nrr/records.htm#BIGSNFS, https://stdkmd.net/nrr/wanted.htm#smallpolynomial) or the general number field sieve (https://en.wikipedia.org/wiki/General_number_field_sieve, https://www.rieselprime.de/ziki/General_number_field_sieve, https://mathworld.wolfram.com/NumberFieldSieve.html, https://stdkmd.net/nrr/records.htm#BIGGNFS, https://stdkmd.net/nrr/wanted.htm#suitableforgnfs) may be used, they have SNFS polynomials (https://www.rieselprime.de/ziki/SNFS_polynomial_selection), just like factorization of the numbers in https://stdkmd.net/nrr/aaaab.htm and https://stdkmd.net/nrr/abbbb.htm and https://stdkmd.net/nrr/aaaba.htm and https://stdkmd.net/nrr/abaaa.htm and https://stdkmd.net/nrr/abbba.htm and https://stdkmd.net/nrr/abbbc.htm and http://mklasson.com/factors/index.php and https://cs.stanford.edu/people/rpropper/math/factors/3n-2.txt, see https://stdkmd.net/nrr/records.htm and https://stdkmd.net/nrr/wanted.htm)
(only list the families which can be proven to be not covered by any prime > b (this would include all such families of the form x{0}y and all such families of the form x{y} (unless y = 1) and all such families of the form {x}y (unless x = 1)), the only exceptions are the base 21 family B0{H}6H (which is covered by the smallest prime in the family B{H}6H in base 21 (if such prime exists)) and the base 8 family 6{4}7 (which is covered by the prime 42207 in base 8))
(this table is sorted by: single trivial prime factor (2{0}1 in base b = 10 through D{6}R in base b = 28) → covering congruence with 2 primes ({1}5 in base b = 9 through {X}5 in base b = 34) → covering congruence with ≥ 3 primes (6{4}7 in base b = 8 through {G}L in base b = 32) → algebraic factorization ({1} in base b = 9 through 9{S}IJ in base b = 36) → combine of covering congruence and algebraic factorization (8{D} in base b = 14 through {X}P in base b = 34))
Also families which contain only one very small prime > b: (this is because: for the case of covering congruence, an element in S is indeed in the family and > b, to make the factorizations be trivial; for the case of algebraic factorization (if the numbers are factored as F × G / d), F (or G) is equal to d and G (or F) is prime > b, to make the factorizations be trivial; for the case of combine of covering congruence and algebraic factorization (if the numbers are factored as F × G / d), an element in S is indeed in the family and > b or/and F (or G) is equal to d and G (or F) is prime > b, to make the factorizations be trivial)
b | family | algebraic ((a×bn+c)/d) form of this family (n is the number of digits in the "{}", also the lower bound of n to make the numbers > b) (note: d divides gcd(a+c,b−1), but d need not be gcd(a+c,b−1), d = gcd(a+c,b−1) if and only if the numbers in the family are not divisible by some prime factor of b−1, i.e. the numbers in the family are coprime to b−1) |
the only prime > b in this family | this prime > b written in decimal | why this family contains only this prime > b | factorization of the numbers in this family (n is the number of digits in the "{}", start with the smallest n making the number > b (if n = 0 already makes the number > b, then start with n = 0)) |
---|---|---|---|---|---|---|
9 | 2{7}5 | (23×9n+1−23)/8 (n ≥ 0) | 25 | 23 | always divisible by 23 | http://factordb.com/index.php?query=%2823*9%5E%28n%2B1%29-23%29%2F8&use=n&n=0&VP=on&VC=on&EV=on&OD=on&PR=on&FF=on&PRP=on&CF=on&U=on&C=on&perpage=200&format=1&sent=Show |
9 | 5{7}2 | (47×9n+1−47)/8 (n ≥ 0) | 52 | 47 | always divisible by 47 | http://factordb.com/index.php?query=%2847*9%5E%28n%2B1%29-47%29%2F8&use=n&n=0&VP=on&VC=on&EV=on&OD=on&PR=on&FF=on&PRP=on&CF=on&U=on&C=on&perpage=200&format=1&sent=Show |
11 | 3{7}4 | (37×11n+1−37)/10 (n ≥ 0) | 34 | 37 | always divisible by 37 | http://factordb.com/index.php?query=%2837*11%5E%28n%2B1%29-37%29%2F10&use=n&n=0&VP=on&VC=on&EV=on&OD=on&PR=on&FF=on&PRP=on&CF=on&U=on&C=on&perpage=200&format=1&sent=Show |
11 | 4{7}3 | (47×11n+1−47)/10 (n ≥ 0) | 43 | 47 | always divisible by 47 | http://factordb.com/index.php?query=%2847*11%5E%28n%2B1%29-47%29%2F10&use=n&n=0&VP=on&VC=on&EV=on&OD=on&PR=on&FF=on&PRP=on&CF=on&U=on&C=on&perpage=200&format=1&sent=Show |
27 | 2{0}J | 2×27n+1+19 (n ≥ 0) | 2J | 73 | always divisible by some element of {5,7,73} divisible by 7 if n is odd, divisible by 5 if n == 2 mod 4, divisible by 73 if n == 0 mod 4 |
http://factordb.com/index.php?query=2*27%5E%28n%2B1%29%2B19&use=n&n=0&VP=on&VC=on&EV=on&OD=on&PR=on&FF=on&PRP=on&CF=on&U=on&C=on&perpage=200&format=1&sent=Show |
4 | {1} | (4n−1)/3 (n ≥ 2) | 11 | 5 | difference-of-two-squares factorization but 11 is prime, and 11 is the only prime > b in this family (4n−1)/3 = (2n−1) × (2n+1) / 3 |
http://factordb.com/index.php?query=%284%5En-1%29%2F3&use=n&n=2&VP=on&VC=on&EV=on&OD=on&PR=on&FF=on&PRP=on&CF=on&U=on&C=on&perpage=200&format=1&sent=Show |
8 | {1} | (8n−1)/7 (n ≥ 2) | 111 | 73 | difference-of-two-cubes factorization but 111 is prime, and 111 is the only prime > b in this family (8n−1)/7 = (2n−1) × (4n+2n+1) / 7 |
http://factordb.com/index.php?query=%288%5En-1%29%2F7&use=n&n=2&VP=on&VC=on&EV=on&OD=on&PR=on&FF=on&PRP=on&CF=on&U=on&C=on&perpage=200&format=1&sent=Show |
16 | {1} | (16n−1)/15 (n ≥ 2) | 11 | 17 | difference-of-two-squares factorization but 11 is prime, and 11 is the only prime > b in this family (16n−1)/15 = (4n−1) × (4n+1) / 15 (in fact, difference-of-4th-powers factorization) (16n−1)/15 = (2n−1) × (2n+1) × (4n+1) / 15 |
http://factordb.com/index.php?query=%2816%5En-1%29%2F15&use=n&n=2&VP=on&VC=on&EV=on&OD=on&PR=on&FF=on&PRP=on&CF=on&U=on&C=on&perpage=200&format=1&sent=Show |
27 | {1} | (27n−1)/26 (n ≥ 2) | 111 | 757 | difference-of-two-cubes factorization but 111 is prime, and 111 is the only prime > b in this family (27n−1)/26 = (3n−1) × (9n+3n+1) / 26 |
http://factordb.com/index.php?query=%2827%5En-1%29%2F26&use=n&n=2&VP=on&VC=on&EV=on&OD=on&PR=on&FF=on&PRP=on&CF=on&U=on&C=on&perpage=200&format=1&sent=Show |
27 | {G}7 | (8×27n+1−125)/13 (n ≥ 1) | G7 | 439 | difference-of-two-cubes factorization but G7 is prime, and G7 is the only prime > b in this family (8×27n+1−125)/13 = (2×3n+1−5) × (4×9n+1+10×3n+1+25) / 13 |
http://factordb.com/index.php?query=%288*27%5E%28n%2B1%29-125%29%2F13&use=n&n=1&VP=on&VC=on&EV=on&OD=on&PR=on&FF=on&PRP=on&CF=on&U=on&C=on&perpage=200&format=1&sent=Show |
36 | {1} | (36n−1)/35 (n ≥ 2) | 11 | 37 | difference-of-two-squares factorization but 11 is prime, and 11 is the only prime > b in this family (36n−1)/35 = (6n−1) × (6n+1) / 35 |
http://factordb.com/index.php?query=%2836%5En-1%29%2F35&use=n&n=2&VP=on&VC=on&EV=on&OD=on&PR=on&FF=on&PRP=on&CF=on&U=on&C=on&perpage=200&format=1&sent=Show |
Some x{y}z (where x and z are strings (may be empty) of digits in base b, y is a digit in base b) families could not be proven to contain no primes > b (by covering congruence, algebraic factorization, or combine of them) but no primes > b could be found in the family, even after searching through numbers with over 100000 digits. In such a case, the only way to proceed is to test the primality of larger and larger numbers of such form and hope a prime is eventually discovered.
Many x{y}z (where x and z are strings (may be empty) of digits in base b, y is a digit in base b) families contain no small primes > b even though they do contain very large primes. e.g. the smallest prime in base 13 family 9{5} is 95197420 (http://www.primenumbers.net/prptop/searchform.php?form=%28113*13%5E197420-5%29%2F12&action=Search, http://factordb.com/index.php?id=1100000003943359311, for this prime written in base b = 13 see http://factordb.com/index.php?showid=1100000003943359311&base=13, and for the factorization of the numbers in the family (n is the number of digits in the "{}", start with the smallest n making the number > b) see http://factordb.com/index.php?query=%28113*13%5En-5%29%2F12&use=n&n=1&VP=on&VC=on&EV=on&OD=on&PR=on&FF=on&PRP=on&CF=on&U=on&C=on&perpage=200&format=1&sent=Show), its algebraic form is (113×13197420−5)/12, when written in decimal it contains 219916 digits; and the smallest prime in base 16 family {3}AF is 3116137AF (http://www.primenumbers.net/prptop/searchform.php?form=%2816%5E116139%2B619%29%2F5&action=Search, http://factordb.com/index.php?id=1100000003851731988, for this prime written in base b = 16 see http://factordb.com/index.php?showid=1100000003851731988&base=16, and for the factorization of the numbers in the family (n is the number of digits in the "{}", start with the smallest n making the number > b) see http://factordb.com/index.php?query=%2816%5E%28n%2B2%29%2B619%29%2F5&use=n&n=0&VP=on&VC=on&EV=on&OD=on&PR=on&FF=on&PRP=on&CF=on&U=on&C=on&perpage=200&format=1&sent=Show), its algebraic form is (16116139+619)/5, when written in decimal it contains 139845 digits; and the smallest prime in base 23 family 9{E} is 9E800873 (http://www.primenumbers.net/prptop/searchform.php?form=%28106*23%5E800873-7%29%2F11&action=Search, http://factordb.com/index.php?id=1100000000782858648, for this prime written in base b = 23 see http://factordb.com/index.php?showid=1100000000782858648&base=23, and for the factorization of the numbers in the family (n is the number of digits in the "{}", start with the smallest n making the number > b) see http://factordb.com/index.php?query=%28106*23%5En-7%29%2F11&use=n&n=1&VP=on&VC=on&EV=on&OD=on&PR=on&FF=on&PRP=on&CF=on&U=on&C=on&perpage=200&format=1&sent=Show), its algebraic form is (106×23800873−7)/11, when written in decimal it contains 1090573 digits; and the smallest prime in base 25 family 71JD{0}1 is 71JD04585491 (http://primes.utm.edu/primes/page.php?id=111834, http://factordb.com/index.php?id=1100000002341496334, for this prime written in base b = 25 see http://factordb.com/index.php?showid=1100000002341496334&base=25, and for the factorization of the numbers in the family (n is the number of digits in the "{}", start with the smallest n making the number > b) see http://factordb.com/index.php?query=110488*25%5E%28n%2B1%29%2B1&use=n&n=0&VP=on&VC=on&EV=on&OD=on&PR=on&FF=on&PRP=on&CF=on&U=on&C=on&perpage=200&format=1&sent=Show), its algebraic form is 110488×25458550+1, when written in decimal it contains 641031 digits (this number can be proven prime by N−1 test (https://primes.utm.edu/prove/prove3_1.html, http://bln.curtisbright.com/2013/10/09/the-n-1-and-n1-primality-tests/, http://factordb.com/nmoverview.php?method=1), since N−1 is trivially fully factored); and the smallest prime in base 32 family NU{0}1 is NU06618631 (https://primes.utm.edu/primes/page.php?id=134216, http://factordb.com/index.php?id=1100000003813355148, for this prime written in base b = 32 see http://factordb.com/index.php?showid=1100000003813355148&base=32, and for the factorization of the numbers in the family (n is the number of digits in the "{}", start with the smallest n making the number > b) see http://factordb.com/index.php?query=766*32%5E%28n%2B1%29%2B1&use=n&n=0&VP=on&VC=on&EV=on&OD=on&PR=on&FF=on&PRP=on&CF=on&U=on&C=on&perpage=200&format=1&sent=Show), its algebraic form is 766×32661864+1, when written in decimal it contains 996208 digits (this number can be proven prime by N−1 test (https://primes.utm.edu/prove/prove3_1.html, http://bln.curtisbright.com/2013/10/09/the-n-1-and-n1-primality-tests/, http://factordb.com/nmoverview.php?method=1), since N−1 is trivially fully factored); and the smallest prime in base 36 family {P}SZ is P81993SZ (http://www.primenumbers.net/prptop/searchform.php?form=%285*36%5E81995%2B821%29%2F7&action=Search, http://factordb.com/index.php?id=1100000002394962083, for this prime written in base b = 36 see http://factordb.com/index.php?showid=1100000002394962083&base=36, and for the factorization of the numbers in the family (n is the number of digits in the "{}", start with the smallest n making the number > b) see http://factordb.com/index.php?query=%285*36%5E%28n%2B2%29%2B821%29%2F7&use=n&n=0&VP=on&VC=on&EV=on&OD=on&PR=on&FF=on&PRP=on&CF=on&U=on&C=on&perpage=200&format=1&sent=Show), its algebraic form is (5×3681995+821)/7, when written in decimal it contains 127609 digits. (technically, probable (https://en.wikipedia.org/wiki/Probabilistic_algorithm) primality tests (https://primes.utm.edu/prove/prove2.html) were used to show these for the numbers which cannot be proven prime by N−1 test (https://primes.utm.edu/prove/prove3_1.html, http://bln.curtisbright.com/2013/10/09/the-n-1-and-n1-primality-tests/, http://factordb.com/nmoverview.php?method=1) or N+1 test (https://primes.utm.edu/prove/prove3_2.html, http://bln.curtisbright.com/2013/10/09/the-n-1-and-n1-primality-tests/, http://factordb.com/nmoverview.php?method=2), i.e. for the ordinary primes (https://primes.utm.edu/glossary/xpage/OrdinaryPrime.html) (which have a very small chance of making an error (https://primes.utm.edu/notes/prp_prob.html, https://www.ams.org/journals/mcom/1989-53-188/S0025-5718-1989-0982368-4/S0025-5718-1989-0982368-4.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_22.pdf))) because all known primality tests (https://en.wikipedia.org/wiki/Primality_test, https://www.rieselprime.de/ziki/Primality_test, https://mathworld.wolfram.com/PrimalityTest.html, https://primes.utm.edu/prove/prove3.html, https://primes.utm.edu/prove/prove4.html) run far too slowly (the CPU time (https://en.wikipedia.org/wiki/CPU_time) is longer than the life expectancy of human (https://en.wikipedia.org/wiki/Life_expectancy) for numbers > 10100000, and longer than the age of the universe (https://en.wikipedia.org/wiki/Age_of_the_universe) for numbers > 10500000, and longer than one quettasecond (https://en.wikipedia.org/wiki/Quetta-) for numbers > 103000000, even if we can do 109 bitwise operations (https://en.wikipedia.org/wiki/Bitwise_operation) per second (https://en.wikipedia.org/wiki/Second) to run on these numbers) to run on numbers of these sizes unless either N−1 (https://primes.utm.edu/prove/prove3_1.html, http://bln.curtisbright.com/2013/10/09/the-n-1-and-n1-primality-tests/, http://factordb.com/nmoverview.php?method=1) or N+1 (https://primes.utm.edu/prove/prove3_2.html, http://bln.curtisbright.com/2013/10/09/the-n-1-and-n1-primality-tests/, http://factordb.com/nmoverview.php?method=2) (or both) (unfortunely, none of Wikipedia, Prime Wiki, Mathworld has article for N−1 primality test or N+1 primality test, but a similar article for Pocklington primality test: https://en.wikipedia.org/wiki/Pocklington_primality_test, https://www.rieselprime.de/ziki/Pocklington%27s_theorem, https://mathworld.wolfram.com/PocklingtonsTheorem.html, also see the article for the cyclotomy primality test: https://primes.utm.edu/glossary/xpage/Cyclotomy.html) can be ≥ 1/3 factored (https://en.wikipedia.org/wiki/Integer_factorization, https://www.rieselprime.de/ziki/Factorization, https://mathworld.wolfram.com/PrimeFactorization.html, https://mathworld.wolfram.com/PrimeFactorizationAlgorithms.html, http://www.numericana.com/answer/factoring.htm) or can be ≥ 1/4 factored and the number is not very large (say not > 10100000), or Nn−1 can be ≥ 1/3 factored for a small n. If either N−1 or N+1 (or both) can be ≥ 1/2 factored, then we can use the Pocklington N−1 primality test (https://primes.utm.edu/prove/prove3_1.html, http://bln.curtisbright.com/2013/10/09/the-n-1-and-n1-primality-tests/, https://en.wikipedia.org/wiki/Pocklington_primality_test, https://www.rieselprime.de/ziki/Pocklington%27s_theorem, https://mathworld.wolfram.com/PocklingtonsTheorem.html, https://stdkmd.net/nrr/pock/, http://factordb.com/nmoverview.php?method=1) (the N−1 case) or the Morrison N+1 primality test (https://primes.utm.edu/prove/prove3_2.html, http://bln.curtisbright.com/2013/10/09/the-n-1-and-n1-primality-tests/, http://factordb.com/nmoverview.php?method=2) (the N+1 case); if either N−1 or N+1 (or both) can be ≥ 1/3 factored, then we can use the Brillhart-Lehmer-Selfridge primality test (https://www.ams.org/journals/mcom/1975-29-130/S0025-5718-1975-0384673-1/S0025-5718-1975-0384673-1.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_23.pdf), https://en.wikipedia.org/wiki/Pocklington_primality_test#Extensions_and_variants); if either N−1 or N+1 (or both) can be ≥ 1/4 factored but neither can be ≥ 1/3 factored, then we need to use CHG (https://mersenneforum.org/attachment.php?attachmentid=21133&d=1571237465, https://primes.utm.edu/bios/page.php?id=797, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/CHG) to prove its primality (see https://mersenneforum.org/showpost.php?p=528149&postcount=3 and https://mersenneforum.org/showpost.php?p=603181&postcount=438), however, unlike Brillhart-Lehmer-Selfridge primality test for the numbers N such that N−1 or N+1 (or both) can be ≥ 1/3 factored can run for arbitrarily large numbers N (thus, there are no unproven probable primes N such that N−1 or N+1 (or both) can be ≥ 1/3 factored), CHG for the numbers N such that either N−1 or N+1 (or both) can be ≥ 1/4 factored but neither can be ≥ 1/3 factored cannot run for very large N (say > 10100000), for the examples of the numbers which are proven prime by CHG, see https://primes.utm.edu/primes/page.php?id=126454, https://primes.utm.edu/primes/page.php?id=131964, https://primes.utm.edu/primes/page.php?id=123456, https://primes.utm.edu/primes/page.php?id=130933, https://stdkmd.net/nrr/cert/1/ (search for "CHG"), https://stdkmd.net/nrr/cert/2/ (search for "CHG"), https://stdkmd.net/nrr/cert/3/ (search for "CHG"), https://stdkmd.net/nrr/cert/4/ (search for "CHG"), https://stdkmd.net/nrr/cert/5/ (search for "CHG"), https://stdkmd.net/nrr/cert/6/ (search for "CHG"), https://stdkmd.net/nrr/cert/7/ (search for "CHG"), https://stdkmd.net/nrr/cert/8/ (search for "CHG"), https://stdkmd.net/nrr/cert/9/ (search for "CHG"), however, factordb (http://factordb.com/, https://www.rieselprime.de/ziki/Factoring_Database) lacks the ability to verify CHG proofs, see https://mersenneforum.org/showpost.php?p=608362&postcount=165; if neither N−1 nor N+1 can be ≥ 1/4 factored but Nn−1 can be ≥ 1/3 factored for a small n, then we can use the cyclotomy primality test (https://primes.utm.edu/glossary/xpage/Cyclotomy.html, https://primes.utm.edu/prove/prove3_3.html, http://factordb.com/nmoverview.php?method=3)), i.e. it is too hard to prove primes for general numbers (https://primes.utm.edu/glossary/xpage/OrdinaryPrime.html) of this size, but they are expected to be primes, since they are > 1025000 and the probability that they are in fact composite is < 10−2000, see https://primes.utm.edu/notes/prp_prob.html and https://www.ams.org/journals/mcom/1989-53-188/S0025-5718-1989-0982368-4/S0025-5718-1989-0982368-4.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_22.pdf).
The numbers in x{y}z (where x and z are strings (may be empty) of digits in base b, y is a digit in base b) families are of the form (a×bn+c)/gcd(a+c,b−1) for some fixed a, b, c such that a ≥ 1, b ≥ 2 (b is the base), c ≠ 0, gcd(a,c) = 1, gcd(b,c) = 1. Except in the special case c = ±1 and gcd(a+c,b−1) = 1 (since this special case c = ±1 and gcd(a+c,b−1) = 1 is the only case which N−1 and/or N+1 is smooth (https://en.wikipedia.org/wiki/Smooth_number, https://mathworld.wolfram.com/SmoothNumber.html), i.e. the case c = 1 and gcd(a+c,b−1) = 1 (corresponding to generalized Proth prime (https://en.wikipedia.org/wiki/Proth_prime, https://primes.utm.edu/glossary/xpage/ProthPrime.html, https://www.rieselprime.de/ziki/Proth_prime, https://mathworld.wolfram.com/ProthNumber.html, https://www.numbersaplenty.com/set/Proth_number/, https://primes.utm.edu/top20/page.php?id=66, https://www.primegrid.com/forum_thread.php?id=2665, https://www.primegrid.com/stats_pps_llr.php, https://www.primegrid.com/stats_ppse_llr.php, https://www.primegrid.com/stats_mega_llr.php) base b: a×bn+1, they are related to generalized Sierpinski conjecture base b (http://www.noprimeleftbehind.net/crus/Sierp-conjectures.htm, http://www.noprimeleftbehind.net/crus/Sierp-conjectures-powers2.htm, http://www.noprimeleftbehind.net/crus/Sierp-conjecture-reserves.htm, http://www.noprimeleftbehind.net/crus/vstats_new/all_ck_sierpinski.txt, https://www.utm.edu/staff/caldwell/preprints/2to100.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_3.pdf), http://www.bitman.name/math/article/1259 (in Italian))) can be easily proven prime using Pocklington N−1 method (https://primes.utm.edu/prove/prove3_1.html, http://bln.curtisbright.com/2013/10/09/the-n-1-and-n1-primality-tests/, https://en.wikipedia.org/wiki/Pocklington_primality_test, https://www.rieselprime.de/ziki/Pocklington%27s_theorem, https://mathworld.wolfram.com/PocklingtonsTheorem.html, https://stdkmd.net/nrr/pock/, http://factordb.com/nmoverview.php?method=1), and the case c = −1 and gcd(a+c,b−1) = 1 (corresponding to generalized Riesel prime (https://www.rieselprime.de/ziki/Riesel_prime) base b: a×bn−1, they are related to generalized Riesel conjecture base b (http://www.noprimeleftbehind.net/crus/Riesel-conjectures.htm, http://www.noprimeleftbehind.net/crus/Riesel-conjectures-powers2.htm, http://www.noprimeleftbehind.net/crus/Riesel-conjecture-reserves.htm, http://www.noprimeleftbehind.net/crus/vstats_new/all_ck_riesel.txt)) can be easily proven prime using Morrison N+1 method (https://primes.utm.edu/prove/prove3_2.html, http://bln.curtisbright.com/2013/10/09/the-n-1-and-n1-primality-tests/, http://factordb.com/nmoverview.php?method=2), these primes can be proven prime using Yves Gallot's Proth.exe (https://primes.utm.edu/programs/gallot/, https://primes.utm.edu/bios/page.php?id=411, https://www.rieselprime.de/ziki/Proth.exe, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/proth), these primes can also be proven prime using Jean Penné's LLR (http://jpenne.free.fr/index2.html, https://primes.utm.edu/bios/page.php?id=431, https://www.rieselprime.de/ziki/LLR, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/llr403win64, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/llr403linux64), see https://mersenneforum.org/showpost.php?p=611607&postcount=10 and https://mersenneforum.org/showpost.php?p=235113&postcount=8 and https://mersenneforum.org/showpost.php?p=541285&postcount=4 and https://mersenneforum.org/showpost.php?p=586913&postcount=429 and https://mersenneforum.org/showpost.php?p=605958&postcount=441, also see https://web.archive.org/web/20020809212051/http://www.users.globalnet.co.uk/~aads/C0034177.html and https://web.archive.org/web/20020701171455/http://www.users.globalnet.co.uk/~aads/C0066883.html and https://web.archive.org/web/20020809122706/http://www.users.globalnet.co.uk/~aads/C0071699.html and https://web.archive.org/web/20020809122635/http://www.users.globalnet.co.uk/~aads/C0101031.html and https://web.archive.org/web/20020809122237/http://www.users.globalnet.co.uk/~aads/C0114801.html and https://web.archive.org/web/20020809122947/http://www.users.globalnet.co.uk/~aads/C0130991.html and https://web.archive.org/web/20020809124216/http://www.users.globalnet.co.uk/~aads/C0131021.html and https://web.archive.org/web/20020809125049/http://www.users.globalnet.co.uk/~aads/C0131193.html and https://web.archive.org/web/20020809124458/http://www.users.globalnet.co.uk/~aads/C0152579.html and https://web.archive.org/web/20020809124537/http://www.users.globalnet.co.uk/~aads/C0220857.html and https://web.archive.org/web/20020809152611/http://www.users.globalnet.co.uk/~aads/C0315581.html and https://web.archive.org/web/20020809124929/http://www.users.globalnet.co.uk/~aads/C0351297.html and http://www.fermatquotient.com/PrimSerien/GenFermOdd.txt (the bottom of the page, about the factorization of (7116384+1)/2−1 and (7116384+1)/2+1) and https://web.archive.org/web/20170515153924/http://bitc.bme.emory.edu/~lzhou/blogs/?p=263, also see the README file for LLR (https://github.com/xayahrainie4793/prime-programs-cached-copy/blob/main/llr403win64/Readme.txt, https://github.com/xayahrainie4793/prime-programs-cached-copy/blob/main/llr403linux64/Readme.txt, http://jpenne.free.fr/index2.html), also see the (generalized) Proth/Riesel prime search page (https://primes.utm.edu/primes/search_proth.php), also you can compare the top definitely primes page (https://primes.utm.edu/primes/lists/all.txt) and the top probable primes page (http://www.primenumbers.net/prptop/prptop.php), also see https://stdkmd.net/nrr/records.htm (compare the sections "Prime numbers" and "Probable prime numbers")), when n is large the known primality tests (https://en.wikipedia.org/wiki/Primality_test, https://www.rieselprime.de/ziki/Primality_test, https://mathworld.wolfram.com/PrimalityTest.html, https://primes.utm.edu/prove/prove3.html, https://primes.utm.edu/prove/prove4.html) for such a number are too inefficient to run. In this case one must resort to a probable (https://en.wikipedia.org/wiki/Probabilistic_algorithm) primality test (https://primes.utm.edu/prove/prove2.html) such as a Miller–Rabin primality test (https://primes.utm.edu/prove/prove2_3.html, https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test, https://en.wikipedia.org/wiki/Strong_pseudoprime, https://primes.utm.edu/glossary/xpage/StrongPRP.html, https://www.rieselprime.de/ziki/Miller-Rabin_pseudoprimality_test, https://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html, https://mathworld.wolfram.com/StrongPseudoprime.html, http://www.numericana.com/answer/pseudo.htm#rabin, http://www.numericana.com/answer/pseudo.htm#strong, http://www.javascripter.net/math/primes/millerrabinprimalitytest.htm, http://ntheory.org/data/spsps.txt, https://sites.google.com/view/strong-pseudoprime, https://sites.google.com/view/bases-strong-pseudoprime, https://oeis.org/A001262, https://oeis.org/A020229, https://oeis.org/A072276, https://oeis.org/A014233, https://oeis.org/A181782, https://oeis.org/A071294, https://oeis.org/A141768, https://oeis.org/A195328, https://oeis.org/A329759, https://oeis.org/A298756) or a Baillie–PSW primality test (https://en.wikipedia.org/wiki/Baillie%E2%80%93PSW_primality_test, https://mathworld.wolfram.com/Baillie-PSWPrimalityTest.html), unless a divisor of the number can be found. Since we are testing many numbers in an exponential sequence (https://en.wikipedia.org/wiki/Exponential_growth, https://mathworld.wolfram.com/ExponentialGrowth.html), it is possible to use a sieving process (https://www.rieselprime.de/ziki/Sieving, https://www.rieselprime.de/ziki/Sieving_a_range_of_sequences, https://mathworld.wolfram.com/Sieve.html, http://www.rechenkraft.net/yoyo/y_status_sieve.php) to find divisors rather than using trial division (https://en.wikipedia.org/wiki/Trial_division, https://primes.utm.edu/glossary/xpage/TrialDivision.html, https://www.rieselprime.de/ziki/Trial_factoring, https://mathworld.wolfram.com/TrialDivision.html, http://www.numericana.com/answer/factoring.htm#trial).
To do this, we made use of Geoffrey Reynolds' SRSIEVE software (https://www.bc-team.org/app.php/dlext/?cat=3, http://web.archive.org/web/20160922072340/https://sites.google.com/site/geoffreywalterreynolds/programs/, http://www.rieselprime.de/dl/CRUS_pack.zip, https://primes.utm.edu/bios/page.php?id=905, https://www.rieselprime.de/ziki/Srsieve, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/srsieve_1.1.4, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/sr1sieve_1.4.6, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/sr2sieve_2.0.0, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/srbsieve, https://github.com/xayahrainie4793/prime-programs-cached-copy/blob/main/mtsieve_2.4.1/srsieve2.exe, https://github.com/xayahrainie4793/prime-programs-cached-copy/blob/main/mtsieve_2.4.1/srsieve2cl.exe). This program uses the baby-step giant-step (https://en.wikipedia.org/wiki/Baby-step_giant-step) algorithm (https://en.wikipedia.org/wiki/Algorithm, https://www.rieselprime.de/ziki/Algorithm, https://mathworld.wolfram.com/Algorithm.html) to find all primes p which divide a×bn+c where p and n lie in a specified range (https://en.wikipedia.org/wiki/Interval_(mathematics), https://mathworld.wolfram.com/Interval.html), by using discrete logarithm (https://en.wikipedia.org/wiki/Discrete_logarithm, https://mathworld.wolfram.com/DiscreteLogarithm.html) to solve the equation (https://en.wikipedia.org/wiki/Equation, https://mathworld.wolfram.com/Equation.html) a×bn+c == 0 mod p (i.e. solve the equation (https://en.wikipedia.org/wiki/Equation, https://mathworld.wolfram.com/Equation.html) a×bn+c = 0 in the finite field (https://en.wikipedia.org/wiki/Finite_field, https://mathworld.wolfram.com/FiniteField.html) Zp) (also, this program was updated so that it also removes the n such that a×bn+c has algebraic factors (e.g. difference-of-two-squares factorization (https://en.wikipedia.org/wiki/Difference_of_two_squares) and sum/difference-of-two-cubes factorization (https://en.wikipedia.org/wiki/Sum_of_two_cubes) and difference-of-two-nth-powers factorization with n > 1 (https://en.wikipedia.org/wiki/Binomial_number, https://mathworld.wolfram.com/BinomialNumber.html) and sum/difference-of-two-nth-powers factorization with odd n > 1 (https://en.wikipedia.org/wiki/Binomial_number, https://mathworld.wolfram.com/BinomialNumber.html) and Aurifeuillean factorization (https://en.wikipedia.org/wiki/Aurifeuillean_factorization, https://www.rieselprime.de/ziki/Aurifeuillian_factor, https://mathworld.wolfram.com/AurifeuilleanFactorization.html, http://www.numericana.com/answer/numbers.htm#aurifeuille, http://pagesperso-orange.fr/colin.barker/lpa/cycl_fac.htm, http://list.seqfan.eu/oldermail/seqfan/2017-March/017363.html, http://myfactorcollection.mooo.com:8090/source/cyclo.cpp, http://myfactorcollection.mooo.com:8090/LCD_2_199, http://myfactorcollection.mooo.com:8090/LCD_2_998, https://stdkmd.net/nrr/repunit/repunitnote.htm#aurifeuillean, https://www.unshlump.com/hcn/aurif.html) of x4+4×y4 or x6+27×y6), see https://mersenneforum.org/showpost.php?p=452132&postcount=66 and https://mersenneforum.org/showthread.php?t=21916 and https://github.com/xayahrainie4793/prime-programs-cached-copy/blob/main/srsieve_1.1.4/algebraic.c (note: for the sequence (a×bn+c)/gcd(a+c,b−1), the case of "Mersenne number" in https://github.com/xayahrainie4793/prime-programs-cached-copy/blob/main/srsieve_1.1.4/algebraic.c is the case which a is rational power of b, c = −1 and the case which a is rational power of b, c = 1, gcd(a+c,b−1) ≥ 3, and the case of "GFN" in https://github.com/xayahrainie4793/prime-programs-cached-copy/blob/main/srsieve_1.1.4/algebraic.c is the case which a is rational power of b, c = 1, gcd(a+c,b−1) is either 1 or 2)). Since this program cannot handle the general case (a×bn+c)/gcd(a+c,b−1) when gcd(a+c,b−1) > 1 we only used it to sieve the sequence a×bn+c for primes p not dividing gcd(a+c,b−1), and initialized the list of candidates to not include n for which there is some prime p dividing gcd(a+c,b−1) for which p dividing (a×bn+c)/gcd(a+c,b−1). The program had to be modified slightly to remove a check which would prevent it from running in the case when a, b, and c were all odd (since then 2 divides a×bn+c, but 2 may not divide (a×bn+c)/gcd(a+c,b−1)) (see https://github.com/curtisbright/mepn-data/commit/1b55b353f46c707bbe52897573914128b3303960).
Once the numbers with small divisors had been removed, it remained to test the remaining numbers using a probable primality test. For this we used the software LLR by Jean Penné (http://jpenne.free.fr/index2.html, https://primes.utm.edu/bios/page.php?id=431, https://www.rieselprime.de/ziki/LLR, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/llr403win64, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/llr403linux64) or PFGW (https://sourceforge.net/projects/openpfgw/, https://primes.utm.edu/bios/page.php?id=175, https://www.rieselprime.de/ziki/PFGW, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/pfgw_win_4.0.3). Although undocumented, it is possible to run these two programs on numbers of the form (a×bn+c)/d when d > 1 (however, of course, the numbers (a×bn+c)/d with |c| ≠ 1 and/or d <> 1 and/or a > bn can only be PRP (https://en.wikipedia.org/wiki/Probable_prime, https://primes.utm.edu/glossary/xpage/PRP.html, https://www.rieselprime.de/ziki/Probable_prime, https://mathworld.wolfram.com/ProbablePrime.html, https://stdkmd.net/nrr/records.htm#probableprimenumbers, https://stdkmd.net/nrr/repunit/prpfactors.htm, http://factordb.com/listtype.php?t=1) tested; the numbers a×2n±1 (with a < 2n) are the fastest to test, a×2n+1 numbers are tested using the Proth algorithm (https://en.wikipedia.org/wiki/Proth%27s_theorem, https://www.rieselprime.de/ziki/Proth%27s_theorem, https://mathworld.wolfram.com/ProthsTheorem.html, http://www.numericana.com/answer/primes.htm#proth), a×2n−1 numbers are tested using the Lucas-Lehmer-Riesel algorithm (https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer%E2%80%93Riesel_test); the numbers a×bn±1 (with b > 2, a < bn) can also be definitely prime (https://en.wikipedia.org/wiki/Provable_prime, https://stdkmd.net/nrr/records.htm#primenumbers, http://factordb.com/listtype.php?t=4) tested, a×bn+1 numbers are tested using the N−1 Pocklington algorithm (https://primes.utm.edu/prove/prove3_1.html, http://bln.curtisbright.com/2013/10/09/the-n-1-and-n1-primality-tests/, https://en.wikipedia.org/wiki/Pocklington_primality_test, https://www.rieselprime.de/ziki/Pocklington%27s_theorem, https://mathworld.wolfram.com/PocklingtonsTheorem.html, https://stdkmd.net/nrr/pock/, http://factordb.com/nmoverview.php?method=1), a×bn−1 numbers are tested using the N+1 Morrison algorithm (https://primes.utm.edu/prove/prove3_2.html, http://bln.curtisbright.com/2013/10/09/the-n-1-and-n1-primality-tests/, http://factordb.com/nmoverview.php?method=2)), so this program required no modifications. A script was also written which allowed one to run srsieve while LLR or PFGW was testing the remaining candidates, so that when a divisor was found by srsieve on a number which had not yet been tested by LLR or PFGW it would be removed from the list of candidates.
For the primes < 1025000 for the solved or near-solved bases (bases b with ≤ 6 unsolved families, i.e. bases b = 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 22, 24, 26, 28, 30, 36), we employed PRIMO by Marcel Martin (http://www.ellipsa.eu/public/primo/primo.html, http://www.rieselprime.de/dl/Primo309.zip, https://primes.utm.edu/bios/page.php?id=46, https://www.rieselprime.de/ziki/Primo, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/primo-433-lx64, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/Primo309), an elliptic curve primality proving (https://primes.utm.edu/prove/prove4_2.html, https://en.wikipedia.org/wiki/Elliptic_curve_primality, https://primes.utm.edu/glossary/xpage/ECPP.html, https://mathworld.wolfram.com/EllipticCurvePrimalityProving.html, https://primes.utm.edu/top20/page.php?id=27) implementation, to compute primality certificates (https://en.wikipedia.org/wiki/Primality_certificate, https://primes.utm.edu/glossary/xpage/Certificate.html, https://mathworld.wolfram.com/PrimalityCertificate.html, http://www.lix.polytechnique.fr/Labo/Francois.Morain/Primes/myprimes.html, https://stdkmd.net/nrr/cert/, http://factordb.com/certoverview.php) for the candidates for minimal prime base b which are > 10299 and neither N−1 nor N+1 can be ≥ 1/3 factored (need CHG proof if either N−1 or N+1 (or both) can be ≥ 1/4 factored but neither can be ≥ 1/3 factored, but factordb (http://factordb.com/, https://www.rieselprime.de/ziki/Factoring_Database) lacks the ability to verify CHG proofs, see https://mersenneforum.org/showpost.php?p=608362&postcount=165).
We have completely solved this problem for bases b = 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 18, 20, 24 (i.e. we have found all minimal primes in these bases and proved that they are all such primes and proved that they are definitely primes (https://en.wikipedia.org/wiki/Provable_prime, http://factordb.com/listtype.php?t=4) (i.e. not merely probable primes)) (thus, currently we can complete the classification of the minimal primes in these bases, and the "minimal prime problem" for these bases are theorems (https://en.wikipedia.org/wiki/Theorem, https://mathworld.wolfram.com/Theorem.html, https://primes.utm.edu/notes/proofs/)), also we have completely solved this problem for bases b = 11, 16, 22, 30 if we allow probable primes (https://en.wikipedia.org/wiki/Probable_prime, https://primes.utm.edu/glossary/xpage/PRP.html, https://www.rieselprime.de/ziki/Probable_prime, https://mathworld.wolfram.com/ProbablePrime.html, https://stdkmd.net/nrr/records.htm#probableprimenumbers, https://stdkmd.net/nrr/repunit/prpfactors.htm, http://factordb.com/listtype.php?t=1) > 1025000 in place of proven primes, besides, we have completely solved this problem for bases b = 13, 17, 19, 21, 23, 25, 26, 27, 28, 32, 34, 36 (if we allow strong probable primes in place of proven primes) except the families x{y}z (where x and z are strings (may be empty) of digits in base b, y is a digit in base b) listed in the "left b" files (see the condensed table below for the searching limit of these families) (thus, currently the "minimal prime problem" for these bases are still unsolved problems (https://en.wikipedia.org/wiki/Open_problem, https://en.wikipedia.org/wiki/List_of_unsolved_problems_in_mathematics, https://primes.utm.edu/glossary/xpage/OpenQuestion.html, https://mathworld.wolfram.com/UnsolvedProblems.html, https://primes.utm.edu/notes/conjectures/)).
These sets of minimal primes are computed (https://en.wikipedia.org/wiki/Computing) by: make data up to linear families (i.e. only linear families left) (https://github.com/xayahrainie4793/minimal-elements-of-the-prime-numbers/blob/main/code/kGMP.cc, https://github.com/xayahrainie4793/minimal-elements-of-the-prime-numbers/blob/main/code/searchpp.cc) (see https://github.com/curtisbright/mepn-data/commit/7acfa0656d3c6b759f95a031f475a30f7664a122) → search the left linear families to length 1000 (https://github.com/xayahrainie4793/minimal-elements-of-the-prime-numbers/blob/main/code/searchpm.cc) → use a program like SRSIEVE (https://www.bc-team.org/app.php/dlext/?cat=3, http://web.archive.org/web/20160922072340/https://sites.google.com/site/geoffreywalterreynolds/programs/, http://www.rieselprime.de/dl/CRUS_pack.zip, https://primes.utm.edu/bios/page.php?id=905, https://www.rieselprime.de/ziki/Srsieve, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/srsieve_1.1.4, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/sr1sieve_1.4.6, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/sr2sieve_2.0.0, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/srbsieve, https://github.com/xayahrainie4793/prime-programs-cached-copy/blob/main/mtsieve_2.4.1/srsieve2.exe, https://github.com/xayahrainie4793/prime-programs-cached-copy/blob/main/mtsieve_2.4.1/srsieve2cl.exe) to sieve (https://www.rieselprime.de/ziki/Sieving, https://www.rieselprime.de/ziki/Sieving_a_range_of_sequences, https://mathworld.wolfram.com/Sieve.html, http://www.rechenkraft.net/yoyo/y_status_sieve.php) the left linear families with primes p < 109 (https://github.com/xayahrainie4793/minimal-elements-of-the-prime-numbers/blob/main/code/searchLLR.cc) → use LLR (http://jpenne.free.fr/index2.html, https://primes.utm.edu/bios/page.php?id=431, https://www.rieselprime.de/ziki/LLR, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/llr403win64, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/llr403linux64) to primality test (or probable-primality test) the numbers in the sieve files (LLR will do the Miller–Rabin primality test (https://primes.utm.edu/prove/prove2_3.html, https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test, https://en.wikipedia.org/wiki/Strong_pseudoprime, https://primes.utm.edu/glossary/xpage/StrongPRP.html, https://www.rieselprime.de/ziki/Miller-Rabin_pseudoprimality_test, https://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html, https://mathworld.wolfram.com/StrongPseudoprime.html, http://www.numericana.com/answer/pseudo.htm#rabin, http://www.numericana.com/answer/pseudo.htm#strong, http://www.javascripter.net/math/primes/millerrabinprimalitytest.htm, http://ntheory.org/data/spsps.txt, https://sites.google.com/view/strong-pseudoprime, https://sites.google.com/view/bases-strong-pseudoprime, https://oeis.org/A001262, https://oeis.org/A020229, https://oeis.org/A072276, https://oeis.org/A014233, https://oeis.org/A181782, https://oeis.org/A071294, https://oeis.org/A141768, https://oeis.org/A195328, https://oeis.org/A329759, https://oeis.org/A298756) with first 50 prime bases, the strong Lucas primality test (https://en.wikipedia.org/wiki/Lucas_pseudoprime#Strong_Lucas_pseudoprimes, https://mathworld.wolfram.com/StrongLucasPseudoprime.html), and the strong Frobenius primality test (https://en.wikipedia.org/wiki/Frobenius_pseudoprime#Strong_Frobenius_pseudoprimes, https://primes.utm.edu/glossary/xpage/FrobeniusPseudoprime.html, https://mathworld.wolfram.com/StrongFrobeniusPseudoprime.html), also for a×bn+1 numbers with a < bn, LLR will do the N−1 Pocklington primality test (https://primes.utm.edu/prove/prove3_1.html, http://bln.curtisbright.com/2013/10/09/the-n-1-and-n1-primality-tests/, https://en.wikipedia.org/wiki/Pocklington_primality_test, https://www.rieselprime.de/ziki/Pocklington%27s_theorem, https://mathworld.wolfram.com/PocklingtonsTheorem.html, https://stdkmd.net/nrr/pock/, http://factordb.com/nmoverview.php?method=1) and can prove that these numbers are primes, also for a×bn−1 numbers a < bn, LLR will do the N+1 Morrison algorithm (https://primes.utm.edu/prove/prove3_2.html, http://bln.curtisbright.com/2013/10/09/the-n-1-and-n1-primality-tests/, http://factordb.com/nmoverview.php?method=2) and can prove that these numbers are primes) → trial factor (https://en.wikipedia.org/wiki/Trial_division, https://primes.utm.edu/glossary/xpage/TrialDivision.html, https://www.rieselprime.de/ziki/Trial_factoring, https://mathworld.wolfram.com/TrialDivision.html, http://www.numericana.com/answer/factoring.htm#trial) from 109 to 1016 → use PRIMO (http://www.ellipsa.eu/public/primo/primo.html, http://www.rieselprime.de/dl/Primo309.zip, https://primes.utm.edu/bios/page.php?id=46, https://www.rieselprime.de/ziki/Primo, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/primo-433-lx64, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/Primo309) to elliptic curve primality prove (https://primes.utm.edu/prove/prove4_2.html, https://en.wikipedia.org/wiki/Elliptic_curve_primality, https://primes.utm.edu/glossary/xpage/ECPP.html, https://mathworld.wolfram.com/EllipticCurvePrimalityProving.html, https://primes.utm.edu/top20/page.php?id=27) the numbers < 1025000.
We are unable to determine if the families x{y}z (where x and z are strings (may be empty) of digits in base b, y is a digit in base b) listed in the "left b" files (see the condensed table below for the searching limit of these families) contain a prime (only count the numbers > b) or not (even if we allow strong probable primes), i.e. these families have no known prime (or strong probable prime) members > b, nor can they be ruled out as only containing composites (only count the numbers > b) (by covering congruence, algebraic factorization, or combine of them), i.e. whether these families contain a prime or a strong probable prime (only count the numbers > b) are open problems (https://en.wikipedia.org/wiki/Open_problem, https://en.wikipedia.org/wiki/List_of_unsolved_problems_in_mathematics, https://primes.utm.edu/glossary/xpage/OpenQuestion.html, https://mathworld.wolfram.com/UnsolvedProblems.html, http://www.numericana.com/answer/open.htm, https://primes.utm.edu/notes/conjectures/), and all of these families are expected to contain a prime > b (in fact, expected to contain infinitely many primes), since there is a heuristic argument (https://en.wikipedia.org/wiki/Heuristic_argument, https://primes.utm.edu/glossary/xpage/Heuristic.html, https://mathworld.wolfram.com/Heuristic.html, http://www.utm.edu/~caldwell/preprints/Heuristics.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_112.pdf)) that all families which cannot be ruled out as only containing composites or only containing finitely many primes (by covering congruence, algebraic factorization, or combine of them) contain infinitely many primes (references: https://primes.utm.edu/mersenne/heuristic.html, https://primes.utm.edu/notes/faq/NextMersenne.html, https://web.archive.org/web/20100628035147/http://www.math.niu.edu/~rusin/known-math/98/exp_primes, https://mersenneforum.org/showpost.php?p=564786&postcount=3, https://mersenneforum.org/showpost.php?p=461665&postcount=7), since by the prime number theorem (https://en.wikipedia.org/wiki/Prime_number_theorem, https://primes.utm.edu/glossary/xpage/PrimeNumberThm.html, https://mathworld.wolfram.com/PrimeNumberTheorem.html, https://primes.utm.edu/howmany.html, http://www.numericana.com/answer/primes.htm#pnt, https://oeis.org/wiki/User:Charles_R_Greathouse_IV/Tables_of_special_primes) the chance (https://en.wikipedia.org/wiki/Probability, https://mathworld.wolfram.com/Probability.html) that a random (https://en.wikipedia.org/wiki/Random_number, https://mathworld.wolfram.com/RandomNumber.html) n-digit base b number is prime is approximately (https://en.wikipedia.org/wiki/Asymptotic_analysis, https://primes.utm.edu/glossary/xpage/AsymptoticallyEqual.html, https://mathworld.wolfram.com/Asymptotic.html) 1/n (more accurately, the chance is approximately 1/(n×ln(b)), where ln is the natural logarithm (https://en.wikipedia.org/wiki/Natural_logarithm, https://primes.utm.edu/glossary/xpage/Log.html, https://mathworld.wolfram.com/NaturalLogarithm.html), i.e. the logarithm with base e = 2.718281828459... (https://en.wikipedia.org/wiki/E_(mathematical_constant), https://mathworld.wolfram.com/e.html, https://oeis.org/A001113)). If one conjectures the numbers x{y}z behave similarly you would expect 1/1 + 1/2 + 1/3 + 1/4 + ... = ∞ (https://en.wikipedia.org/wiki/Harmonic_series_(mathematics), https://mathworld.wolfram.com/HarmonicSeries.html) primes of the form x{y}z (of course, this does not always happen, since some x{y}z families can be ruled out as only containing composites (only count the numbers > b) (by covering congruence, algebraic factorization, or combine of them), and every family has its own Nash weight (https://www.rieselprime.de/ziki/Nash_weight, http://irvinemclean.com/maths/nash.htm, http://www.brennen.net/primes/ProthWeight.html, https://www.mersenneforum.org/showthread.php?t=11844, https://www.mersenneforum.org/showthread.php?t=2645, https://www.mersenneforum.org/showthread.php?t=7213, https://www.mersenneforum.org/showthread.php?t=18818, https://www.mersenneforum.org/showpost.php?p=421186&postcount=19, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/allnash, https://www.rieselprime.de/ziki/Riesel_2_Low-weight, https://www.rieselprime.de/ziki/Proth_2_Low-weight, https://www.rieselprime.de/ziki/Category:Riesel_2_Low-weight, https://www.rieselprime.de/ziki/Category:Proth_2_Low-weight, https://www.rieselprime.de/ziki/Category:Riesel_5_Low-weight, https://www.rieselprime.de/ziki/Category:Proth_5_Low-weight, http://www.noprimeleftbehind.net/crus/vstats_new/riesel_weights.txt, http://www.noprimeleftbehind.net/crus/vstats_new/sierpinski_weights.txt) (or difficulty (https://stdkmd.net/nrr/prime/primedifficulty.htm, https://stdkmd.net/nrr/prime/primedifficulty.txt, http://www.noprimeleftbehind.net/crus/vstats_new/crus-unproven.htm, http://www.noprimeleftbehind.net/crus/vstats_new/riesel_difficulty.txt, http://www.noprimeleftbehind.net/crus/vstats_new/sierpinski_difficulty.txt)), see https://mersenneforum.org/showpost.php?p=564786&postcount=3, families which can be proven to only contain composites or only contain finitely many primes (by covering congruence, algebraic factorization, or combine of them) have Nash weight (or difficulty) 0, and families which cannot be proven to only contain composites or only contain finitely many primes (by covering congruence, algebraic factorization, or combine of them) have positive Nash weight (or difficulty), but it is at least a reasonable conjecture in the absence of evidence to the contrary).
Some of the left families may cover another left family, e.g. the base 19 left family 5{H}5 covers another base 19 left family 5{H}05, and if the smallest prime in family 5{H}5 in base 19 has length n, and the family 5{H}05 in base 19 has no prime with length ≤ n, then family 5{H}05 in base 19 can be removed from the unsolved families for base 19, however, if the smallest prime in family 5{H}5 in base 19 has length n, but the family 5{H}05 in base 19 is not tested to length n or more, then family 5{H}05 in base 19 should not be removed from the unsolved families for base 19, since a number in family 5{H}05 covers the prime in family 5{H}5 with length n if and only if the length of this number is ≥ n+1; besides, the base 19 left family FH0{H} covers another base 19 left family FHHH0{H}, and if the smallest prime in family FH0{H} in base 19 has length n, and the family FHHH0{H} in base 19 has no prime with length ≤ n+1, then family FHHH0{H} in base 19 can be removed from the unsolved families for base 19, however, if the smallest prime in family FH0{H} in base 19 has length n, but the family FHHH0{H} in base 19 is not tested to length n+1 or more, then family FHHH0{H} in base 19 should not be removed from the unsolved families for base 19, since a number in family FHHH0{H} covers the prime in family FH0{H} with length n if and only if the length of this number is ≥ n+2; besides, the base 21 left family {9}D covers another base 21 left family F{9}D, and if the smallest prime in family {9}D in base 21 has length n, and the family F{9}D in base 21 has no prime with length ≤ n, then family F{9}D in base 21 can be removed from the unsolved families for base 21, however, if the smallest prime in family {9}D in base 21 has length n, but the family F{9}D in base 21 is not tested to length n or more, then family F{9}D in base 21 should not be removed from the unsolved families for base 21, since a number in family F{9}D covers the prime in family {9}D with length n if and only if the length of this number is ≥ n+1 (if a family has no primes, then we say "the smallest prime in this family has length ∞ (https://en.wikipedia.org/wiki/Infinity, https://primes.utm.edu/glossary/xpage/Infinite.html, https://mathworld.wolfram.com/Infinity.html) (instead of 0 or −1)", see http://gladhoboexpress.blogspot.com/2019/05/prime-sandwiches-made-with-one-derbread.html and http://chesswanks.com/seq/a306861.txt (for the OEIS sequence https://oeis.org/A306861) and http://chesswanks.com/seq/a269254.txt (for the OEIS sequence https://oeis.org/A269254) (since this is more convenient, e.g. the n of the smallest prime in the base 13 family A3nA, this family has been searched to n = 358000 with no prime or probable prime found, we can use ">358000" for the n of the smallest prime in the base 13 family A3nA (while for the n of the smallest prime in the base 13 family 95n, it is 197420), ">358000" includes infinity (since infinity is > 358000) but does not includes 0 or −1, it is still possible that there is no prime in the base 13 family A3nA, although by the heuristic argument (https://en.wikipedia.org/wiki/Heuristic_argument, https://primes.utm.edu/glossary/xpage/Heuristic.html, https://mathworld.wolfram.com/Heuristic.html, http://www.utm.edu/~caldwell/preprints/Heuristics.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_112.pdf)) above, this is very impossible, also "the smallest n ≥ 1 such that (a×bn+c)/gcd(a+c,b−1) is prime" should be the infimum (https://en.wikipedia.org/wiki/Infimum, https://mathworld.wolfram.com/Infimum.html) of the set S of the numbers n ≥ 1 such that (a×bn+c)/gcd(a+c,b−1) is prime, and if there is no n ≥ 1 such that (a×bn+c)/gcd(a+c,b−1) is prime, then this set S is the empty set (https://en.wikipedia.org/wiki/Empty_set, https://mathworld.wolfram.com/EmptySet.html), and by the definition of "inf", the infimum of the empty set is ∞), ∞ is > any finite number, e.g. "the smallest n ≥ 1 such that k×2n+1 is prime" is ∞ for k = 78557, 157114, 271129, 271577, 314228, 322523, 327739, 482719, ..., while it is 31172165 for k = 10223 and 13018586 for k = 19249, another example is "the smallest n such that (bn−1)/(b−1) is prime" is ∞ for b = 9, 25, 32, 49, 64, 81, 121, 125, 144, 169, 216, 225, 243, 289, 324, 343, 361, 441, 484, 529, 625, 729, 784, 841, 900, 961, 1000, ..., while it is 62903 for b = 691 and 41189 for b = 693).
There are also unproven probable primes (however, in this project our results assume that they are in fact primes, since they are > 1025000 and the probability that they are in fact composite is < 10−2000, see https://primes.utm.edu/notes/prp_prob.html and https://www.ams.org/journals/mcom/1989-53-188/S0025-5718-1989-0982368-4/S0025-5718-1989-0982368-4.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_22.pdf)), the unproven probable primes for bases b = 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 22, 24, 26, 28, 30, 36 (the solved or near-solved bases, i.e. the bases b with ≤ 6 unsolved families) are (together with the factorization of the numbers in their corresponding families): (you can click the "show" in the factordb page to see these unproven probable primes written in base 10 and base b as well as the length of these unproven probable primes in base 10 and base b (for base b, change the "10" in "Digits (Base 10)" box to "b", support bases 2 ≤ b ≤ 36), also you can click the "N−1" or the "N+1" (open the "Primality proving" box) to see the factorization of N−1 and N+1)
(for the factorization of the numbers in these families, the special number field sieve (https://en.wikipedia.org/wiki/Special_number_field_sieve, https://www.rieselprime.de/ziki/Special_number_field_sieve, https://mathworld.wolfram.com/NumberFieldSieve.html) or the general number field sieve (https://en.wikipedia.org/wiki/General_number_field_sieve, https://www.rieselprime.de/ziki/General_number_field_sieve, https://mathworld.wolfram.com/NumberFieldSieve.html) may be used, they have SNFS polynomials (https://www.rieselprime.de/ziki/SNFS_polynomial_selection), just like factorization of the numbers in https://stdkmd.net/nrr/aaaab.htm and https://stdkmd.net/nrr/abbbb.htm and https://stdkmd.net/nrr/aaaba.htm and https://stdkmd.net/nrr/abaaa.htm and https://stdkmd.net/nrr/abbba.htm and https://stdkmd.net/nrr/abbbc.htm and http://mklasson.com/factors/index.php and https://cs.stanford.edu/people/rpropper/math/factors/3n-2.txt, see https://stdkmd.net/nrr/records.htm and https://stdkmd.net/nrr/wanted.htm)
All these numbers are strong probable primes (https://en.wikipedia.org/wiki/Strong_pseudoprime, https://primes.utm.edu/glossary/xpage/StrongPRP.html, https://mathworld.wolfram.com/StrongPseudoprime.html) to bases 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61 (see https://oeis.org/A014233 and https://oeis.org/A141768 and https://oeis.org/A001262 and https://oeis.org/A074773 and http://ntheory.org/data/spsps.txt), and strong Lucas probable primes (https://en.wikipedia.org/wiki/Lucas_pseudoprime#Strong_Lucas_pseudoprimes, https://mathworld.wolfram.com/StrongLucasPseudoprime.html) with parameters (P, Q) defined by Selfridge's Method A (see https://oeis.org/A217255 and http://ntheory.org/data/slpsps-baillie.txt), and trial factored (https://en.wikipedia.org/wiki/Trial_division, https://primes.utm.edu/glossary/xpage/TrialDivision.html, https://www.rieselprime.de/ziki/Trial_factoring, https://mathworld.wolfram.com/TrialDivision.html, http://www.numericana.com/answer/factoring.htm#trial) to 1016 (i.e. all these numbers are 1016-rough numbers (https://en.wikipedia.org/wiki/Rough_number, https://mathworld.wolfram.com/RoughNumber.html)), thus, all these numbers are Baillie–PSW probable primes (https://en.wikipedia.org/wiki/Baillie%E2%80%93PSW_primality_test, https://mathworld.wolfram.com/Baillie-PSWPrimalityTest.html), and no composites < 264 pass the Baillie–PSW probable prime test (see http://ntheory.org/pseudoprimes.html and https://faculty.lynchburg.edu/~nicely/misc/bpsw.html), thus if one of these numbers is in fact composite, it will be a pseudoprime to the Baillie–PSW probable prime test, which currently no single example is known!
The unsolved families for bases b = 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 22, 24, 26, 28, 30, 36 (the solved or near-solved bases, i.e. the bases b with ≤ 6 unsolved families) and the factorization of the numbers in these families:
(you can calculate "equivalent searching limit of length in decimal" by: "current searching limit of length of this family" × log(b), where log is the common logarithm (https://en.wikipedia.org/wiki/Common_logarithm, https://mathworld.wolfram.com/CommonLogarithm.html), i.e. the logarithm with base 10)
(for the factorization of the numbers in these families, the special number field sieve (https://en.wikipedia.org/wiki/Special_number_field_sieve, https://www.rieselprime.de/ziki/Special_number_field_sieve, https://mathworld.wolfram.com/NumberFieldSieve.html, https://stdkmd.net/nrr/records.htm#BIGSNFS, https://stdkmd.net/nrr/wanted.htm#smallpolynomial) or the general number field sieve (https://en.wikipedia.org/wiki/General_number_field_sieve, https://www.rieselprime.de/ziki/General_number_field_sieve, https://mathworld.wolfram.com/NumberFieldSieve.html, https://stdkmd.net/nrr/records.htm#BIGGNFS, https://stdkmd.net/nrr/wanted.htm#suitableforgnfs) may be used, they have SNFS polynomials (https://www.rieselprime.de/ziki/SNFS_polynomial_selection), just like factorization of the numbers in https://stdkmd.net/nrr/aaaab.htm and https://stdkmd.net/nrr/abbbb.htm and https://stdkmd.net/nrr/aaaba.htm and https://stdkmd.net/nrr/abaaa.htm and https://stdkmd.net/nrr/abbba.htm and https://stdkmd.net/nrr/abbbc.htm and http://mklasson.com/factors/index.php and https://cs.stanford.edu/people/rpropper/math/factors/3n-2.txt, see https://stdkmd.net/nrr/records.htm and https://stdkmd.net/nrr/wanted.htm)
The large proven primes (> 10299) for bases b = 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 22, 24, 26, 28, 30, 36 (the solved or near-solved bases, i.e. the bases b with ≤ 6 unsolved families) and their primality certificates (https://en.wikipedia.org/wiki/Primality_certificate, https://primes.utm.edu/glossary/xpage/Certificate.html, https://mathworld.wolfram.com/PrimalityCertificate.html, http://www.lix.polytechnique.fr/Labo/Francois.Morain/Primes/myprimes.html, https://stdkmd.net/nrr/cert/, http://factordb.com/certoverview.php) and the factorization of the numbers in their corresponding families: (you can click the "show" in the factordb page to see these primes written in base 10 and base b as well as the length of these primes in base 10 and base b (for base b, change the "10" in "Digits (Base 10)" box to "b", support bases 2 ≤ b ≤ 36), also you can click the "N−1" or the "N+1" (open the "Primality proving" box) to see the factorization of N−1 and N+1)
(for the factorization of the numbers in these families, the special number field sieve (https://en.wikipedia.org/wiki/Special_number_field_sieve, https://www.rieselprime.de/ziki/Special_number_field_sieve, https://mathworld.wolfram.com/NumberFieldSieve.html, https://stdkmd.net/nrr/records.htm#BIGSNFS, https://stdkmd.net/nrr/wanted.htm#smallpolynomial) or the general number field sieve (https://en.wikipedia.org/wiki/General_number_field_sieve, https://www.rieselprime.de/ziki/General_number_field_sieve, https://mathworld.wolfram.com/NumberFieldSieve.html, https://stdkmd.net/nrr/records.htm#BIGGNFS, https://stdkmd.net/nrr/wanted.htm#suitableforgnfs) may be used, they have SNFS polynomials (https://www.rieselprime.de/ziki/SNFS_polynomial_selection), just like factorization of the numbers in https://stdkmd.net/nrr/aaaab.htm and https://stdkmd.net/nrr/abbbb.htm and https://stdkmd.net/nrr/aaaba.htm and https://stdkmd.net/nrr/abaaa.htm and https://stdkmd.net/nrr/abbba.htm and https://stdkmd.net/nrr/abbbc.htm and http://mklasson.com/factors/index.php and https://cs.stanford.edu/people/rpropper/math/factors/3n-2.txt, see https://stdkmd.net/nrr/records.htm and https://stdkmd.net/nrr/wanted.htm)
Condensed table for bases 2 ≤ b ≤ 36: (the bases b = 11, 13, 16, 17, 19, 21~23, 25~36 data assumes the primality of the probable primes) (This data assumes that a number > 1025000 which has passed the Miller–Rabin primality tests (https://primes.utm.edu/prove/prove2_3.html, https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test, https://en.wikipedia.org/wiki/Strong_pseudoprime, https://primes.utm.edu/glossary/xpage/StrongPRP.html, https://www.rieselprime.de/ziki/Miller-Rabin_pseudoprimality_test, https://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html, https://mathworld.wolfram.com/StrongPseudoprime.html, http://www.numericana.com/answer/pseudo.htm#rabin, http://www.numericana.com/answer/pseudo.htm#strong, http://www.javascripter.net/math/primes/millerrabinprimalitytest.htm, http://ntheory.org/data/spsps.txt, https://sites.google.com/view/strong-pseudoprime, https://sites.google.com/view/bases-strong-pseudoprime, https://oeis.org/A001262, https://oeis.org/A020229, https://oeis.org/A072276, https://oeis.org/A014233, https://oeis.org/A181782, https://oeis.org/A071294, https://oeis.org/A141768, https://oeis.org/A195328, https://oeis.org/A329759, https://oeis.org/A298756) to all prime bases p < 64 and has passed the Baillie–PSW primality test (https://en.wikipedia.org/wiki/Baillie%E2%80%93PSW_primality_test, https://mathworld.wolfram.com/Baillie-PSWPrimalityTest.html) and has trial factored (https://en.wikipedia.org/wiki/Trial_division, https://primes.utm.edu/glossary/xpage/TrialDivision.html, https://www.rieselprime.de/ziki/Trial_factoring, https://mathworld.wolfram.com/TrialDivision.html, http://www.numericana.com/answer/factoring.htm#trial) to 1016 is in fact prime, since in some cases (e.g. b = 11) a candidate for minimal prime base b is too large to be proven prime rigorously, this candidate for minimal prime base 11 has 65263 decimal digits, while the top record ordinary prime (https://primes.utm.edu/glossary/xpage/OrdinaryPrime.html) (i.e. neither N−1 (https://primes.utm.edu/prove/prove3_1.html, http://bln.curtisbright.com/2013/10/09/the-n-1-and-n1-primality-tests/, https://en.wikipedia.org/wiki/Pocklington_primality_test, https://www.rieselprime.de/ziki/Pocklington%27s_theorem, https://mathworld.wolfram.com/PocklingtonsTheorem.html, https://stdkmd.net/nrr/pock/, http://factordb.com/nmoverview.php?method=1) nor N+1 (https://primes.utm.edu/prove/prove3_2.html, http://bln.curtisbright.com/2013/10/09/the-n-1-and-n1-primality-tests/, http://factordb.com/nmoverview.php?method=2) can be ≥ 1/4 factored (https://en.wikipedia.org/wiki/Integer_factorization, https://www.rieselprime.de/ziki/Factorization, https://mathworld.wolfram.com/PrimeFactorization.html, https://mathworld.wolfram.com/PrimeFactorizationAlgorithms.html, http://www.numericana.com/answer/factoring.htm)) has 57125 decimal digits (the entry of this prime in top definitely primes is https://primes.utm.edu/primes/page.php?id=134371), see https://primes.utm.edu/top20/page.php?id=27, and 65263 > 57125) (you can click the "show" in the factordb page to see these primes (or probable primes) written in base 10 and base b as well as the length of these primes (or probable primes) in base 10 and base b (for base b, change the "10" in "Digits (Base 10)" box to "b", support bases 2 ≤ b ≤ 36), also you can click the "N−1" or the "N+1" (open the "Primality proving" box) to see the factorization of N−1 and N+1 for the primes > 10299 (for the factorization of N−1 and N+1 for the primes < 10299, you can just enter "-1" or "+1" after the prime in the searching box, then click "Factorize!"))
Links for top (probable) primes: (also pages for the largest known prime: https://en.wikipedia.org/wiki/Largest_known_prime_number, https://en.wikipedia.org/wiki/List_of_largest_known_primes_and_probable_primes, http://www.numericana.com/answer/primes.htm#history, and related pages: https://en.wikipedia.org/wiki/Megaprime, https://primes.utm.edu/glossary/xpage/TitanicPrime.html, https://primes.utm.edu/glossary/xpage/GiganticPrime.html, https://primes.utm.edu/glossary/xpage/Megaprime.html, https://www.rieselprime.de/ziki/Titanic_prime, https://www.rieselprime.de/ziki/Gigantic_prime, https://www.rieselprime.de/ziki/Megaprime, https://www.rieselprime.de/ziki/Gigaprime, https://mathworld.wolfram.com/TitanicPrime.html, https://mathworld.wolfram.com/GiganticPrime.html)
- https://primes.utm.edu/primes/lists/all.txt (top definitely primes)
- https://primes.utm.edu/primes/lists/all.zip (top definitely primes, zipped file)
- https://primes.utm.edu/primes/lists/all.pdf (top definitely primes, pdf version)
- https://primes.utm.edu/primes/lists/all_pdf.zip (top definitely primes, pdf version, zipped file)
- https://primes.utm.edu/primes/lists/short.txt (definitely primes with ≥ 800000 decimal digits)
- https://primes.utm.edu/primes/lists/short.pdf (definitely primes with ≥ 800000 decimal digits, pdf version)
- https://primes.utm.edu/primes/lists/short_pdf.zip (definitely primes with ≥ 800000 decimal digits, pdf version, zipped file)
- https://primes.utm.edu/primes/search.php?OnList=all&Number=1000000&Style=HTML (all numbers in the list of top definitely primes, html version)
- https://primes.utm.edu/primes/search.php?OnList=all&Number=1000000 (all numbers in the list of top definitely primes, text version)
- https://primes.utm.edu/primes/ (index page of top definitely primes)
- https://primes.utm.edu/primes/download.php (download page of top definitely primes)
- https://primes.utm.edu/primes/status.php?hours=72 (recently 3 days found top definitely primes)
- https://primes.utm.edu/primes/status.php?hours=1000 (recently found top definitely primes)
- https://primes.utm.edu/primes/status.php?hours=0 (top definitely primes which are in process or awaiting verification)
- https://primes.utm.edu/largest.html (the information page of top definitely primes)
- https://primes.utm.edu/notes/by_year.html (the information page of the largest known prime by year)
- https://primes.utm.edu/notes/faq/why.html (the information page of why do people find these large primes)
- https://primes.utm.edu/primes/search.php (search page of top definitely primes)
- https://primes.utm.edu/primes/search.php?Advanced=1 (advanced search page of top definitely primes)
- https://primes.utm.edu/primes/search_proth.php (search page of top definitely primes of the form k×bn±1)
- https://primes.utm.edu/primes/status.php (verification status page of top definitely primes)
- https://primes.utm.edu/top20/index.php (the top 20 definitely primes of certain selected forms)
- https://primes.utm.edu/bios/submission.php (submit page of top definitely primes)
- https://primes.utm.edu/bios/newprover.php (submit page of top definitely primes, create a new prover account)
- https://primes.utm.edu/bios/newcode.php (submit page of top definitely primes, create a new prover code)
- https://primes.utm.edu/bios/index.php (index of the provers and programs and projects of top definitely primes)
- http://www.primenumbers.net/prptop/prptop.php (top probable primes)
- http://www.primenumbers.net/prptop/latest.php (recently found top probable primes)
- http://www.primenumbers.net/prptop/searchform.php (search page of top probable primes)
- http://www.primenumbers.net/prptop/searchform.php?form=%3F&action=Search (all numbers in the list of top probable primes)
- http://www.primenumbers.net/prptop/submit.php (submit page of top probable primes)
- http://www.primenumbers.net/prptop/topdisc.php (index of the provers of top probable primes)
and the search result page for the (probable) primes of special forms: (note: a large prime of the form (a×bn+c)/d with small a, b, c, d and large n can be easily proven prime if and only if c = ±1 and d = 1)
Definitely primes (i.e. c = ±1 and d = 1):
- bn+1: https://primes.utm.edu/primes/search.php?Description=%5E[[:digit:]]%7B1,%7D%5E[[:digit:]]%7B1,%7D%2B1&OnList=all&Number=1000000&Style=HTML
- bn−1: https://primes.utm.edu/primes/search.php?Description=%5E[[:digit:]]%7B1,%7D%5E[[:digit:]]%7B1,%7D-1&OnList=all&Number=1000000&Style=HTML
- a×bn+1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*[[:digit:]]%7B1,%7D%5E[[:digit:]]%7B1,%7D%2B1&OnList=all&Number=1000000&Style=HTML
- a×bn−1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*[[:digit:]]%7B1,%7D%5E[[:digit:]]%7B1,%7D-1&OnList=all&Number=1000000&Style=HTML
- a×2n+1 (which includes a×4n+1, a×8n+1, a×16n+1, a×32n+1): https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*2%5E[[:digit:]]%7B1,%7D%2B1&OnList=all&Number=1000000&Style=HTML
- a×2n−1 (which includes a×4n−1, a×8n−1, a×16n−1, a×32n−1): https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*2%5E[[:digit:]]%7B1,%7D-1&OnList=all&Number=1000000&Style=HTML
- a×3n+1 (which includes a×9n+1, a×27n+1): https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*3%5E[[:digit:]]%7B1,%7D%2B1&OnList=all&Number=1000000&Style=HTML
- a×3n−1 (which includes a×9n−1, a×27n−1): https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*3%5E[[:digit:]]%7B1,%7D-1&OnList=all&Number=1000000&Style=HTML
- a×5n+1 (which includes a×25n+1): https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*5%5E[[:digit:]]%7B1,%7D%2B1&OnList=all&Number=1000000&Style=HTML
- a×5n−1 (which includes a×25n−1): https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*5%5E[[:digit:]]%7B1,%7D-1&OnList=all&Number=1000000&Style=HTML
- a×6n+1 (which includes a×36n+1): https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*6%5E[[:digit:]]%7B1,%7D%2B1&OnList=all&Number=1000000&Style=HTML
- a×6n−1 (which includes a×36n−1): https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*6%5E[[:digit:]]%7B1,%7D-1&OnList=all&Number=1000000&Style=HTML
- a×7n+1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*7%5E[[:digit:]]%7B1,%7D%2B1&OnList=all&Number=1000000&Style=HTML
- a×7n−1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*7%5E[[:digit:]]%7B1,%7D-1&OnList=all&Number=1000000&Style=HTML
- a×10n+1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*10%5E[[:digit:]]%7B1,%7D%2B1&OnList=all&Number=1000000&Style=HTML
- a×10n−1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*10%5E[[:digit:]]%7B1,%7D-1&OnList=all&Number=1000000&Style=HTML
- a×11n+1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*11%5E[[:digit:]]%7B1,%7D%2B1&OnList=all&Number=1000000&Style=HTML
- a×11n−1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*11%5E[[:digit:]]%7B1,%7D-1&OnList=all&Number=1000000&Style=HTML
- a×12n+1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*12%5E[[:digit:]]%7B1,%7D%2B1&OnList=all&Number=1000000&Style=HTML
- a×12n−1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*12%5E[[:digit:]]%7B1,%7D-1&OnList=all&Number=1000000&Style=HTML
- a×13n+1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*13%5E[[:digit:]]%7B1,%7D%2B1&OnList=all&Number=1000000&Style=HTML
- a×13n−1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*13%5E[[:digit:]]%7B1,%7D-1&OnList=all&Number=1000000&Style=HTML
- a×14n+1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*14%5E[[:digit:]]%7B1,%7D%2B1&OnList=all&Number=1000000&Style=HTML
- a×14n−1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*14%5E[[:digit:]]%7B1,%7D-1&OnList=all&Number=1000000&Style=HTML
- a×15n+1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*15%5E[[:digit:]]%7B1,%7D%2B1&OnList=all&Number=1000000&Style=HTML
- a×15n−1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*15%5E[[:digit:]]%7B1,%7D-1&OnList=all&Number=1000000&Style=HTML
- a×17n+1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*17%5E[[:digit:]]%7B1,%7D%2B1&OnList=all&Number=1000000&Style=HTML
- a×17n−1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*17%5E[[:digit:]]%7B1,%7D-1&OnList=all&Number=1000000&Style=HTML
- a×18n+1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*18%5E[[:digit:]]%7B1,%7D%2B1&OnList=all&Number=1000000&Style=HTML
- a×18n−1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*18%5E[[:digit:]]%7B1,%7D-1&OnList=all&Number=1000000&Style=HTML
- a×19n+1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*19%5E[[:digit:]]%7B1,%7D%2B1&OnList=all&Number=1000000&Style=HTML
- a×19n−1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*19%5E[[:digit:]]%7B1,%7D-1&OnList=all&Number=1000000&Style=HTML
- a×20n+1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*20%5E[[:digit:]]%7B1,%7D%2B1&OnList=all&Number=1000000&Style=HTML
- a×20n−1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*20%5E[[:digit:]]%7B1,%7D-1&OnList=all&Number=1000000&Style=HTML
- a×21n+1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*21%5E[[:digit:]]%7B1,%7D%2B1&OnList=all&Number=1000000&Style=HTML
- a×21n−1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*21%5E[[:digit:]]%7B1,%7D-1&OnList=all&Number=1000000&Style=HTML
- a×22n+1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*22%5E[[:digit:]]%7B1,%7D%2B1&OnList=all&Number=1000000&Style=HTML
- a×22n−1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*22%5E[[:digit:]]%7B1,%7D-1&OnList=all&Number=1000000&Style=HTML
- a×23n+1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*23%5E[[:digit:]]%7B1,%7D%2B1&OnList=all&Number=1000000&Style=HTML
- a×23n−1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*23%5E[[:digit:]]%7B1,%7D-1&OnList=all&Number=1000000&Style=HTML
- a×24n+1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*24%5E[[:digit:]]%7B1,%7D%2B1&OnList=all&Number=1000000&Style=HTML
- a×24n−1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*24%5E[[:digit:]]%7B1,%7D-1&OnList=all&Number=1000000&Style=HTML
- a×26n+1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*26%5E[[:digit:]]%7B1,%7D%2B1&OnList=all&Number=1000000&Style=HTML
- a×26n−1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*26%5E[[:digit:]]%7B1,%7D-1&OnList=all&Number=1000000&Style=HTML
- a×28n+1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*28%5E[[:digit:]]%7B1,%7D%2B1&OnList=all&Number=1000000&Style=HTML
- a×28n−1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*28%5E[[:digit:]]%7B1,%7D-1&OnList=all&Number=1000000&Style=HTML
- a×29n+1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*29%5E[[:digit:]]%7B1,%7D%2B1&OnList=all&Number=1000000&Style=HTML
- a×29n−1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*29%5E[[:digit:]]%7B1,%7D-1&OnList=all&Number=1000000&Style=HTML
- a×30n+1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*30%5E[[:digit:]]%7B1,%7D%2B1&OnList=all&Number=1000000&Style=HTML
- a×30n−1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*30%5E[[:digit:]]%7B1,%7D-1&OnList=all&Number=1000000&Style=HTML
- a×31n+1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*31%5E[[:digit:]]%7B1,%7D%2B1&OnList=all&Number=1000000&Style=HTML
- a×31n−1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*31%5E[[:digit:]]%7B1,%7D-1&OnList=all&Number=1000000&Style=HTML
- a×33n+1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*33%5E[[:digit:]]%7B1,%7D%2B1&OnList=all&Number=1000000&Style=HTML
- a×33n−1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*33%5E[[:digit:]]%7B1,%7D-1&OnList=all&Number=1000000&Style=HTML
- a×34n+1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*34%5E[[:digit:]]%7B1,%7D%2B1&OnList=all&Number=1000000&Style=HTML
- a×34n−1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*34%5E[[:digit:]]%7B1,%7D-1&OnList=all&Number=1000000&Style=HTML
- a×35n+1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*35%5E[[:digit:]]%7B1,%7D%2B1&OnList=all&Number=1000000&Style=HTML
- a×35n−1: https://primes.utm.edu/primes/search.php?Description=[[:digit:]]%7B1,%7D*35%5E[[:digit:]]%7B1,%7D-1&OnList=all&Number=1000000&Style=HTML
- a×2n±1 (which includes a×4n±1, a×8n±1, a×16n±1, a×32n±1): https://primes.utm.edu/primes/search_proth.php?base=2&min_k=&max_k=&min_n=&max_n=&plus=on&minus=on&number=1000000&search=Start+Search
- a×3n±1 (which includes a×9n±1, a×27n±1): https://primes.utm.edu/primes/search_proth.php?base=3&min_k=&max_k=&min_n=&max_n=&plus=on&minus=on&number=1000000&search=Start+Search
- a×5n±1 (which includes a×25n±1): https://primes.utm.edu/primes/search_proth.php?base=5&min_k=&max_k=&min_n=&max_n=&plus=on&minus=on&number=1000000&search=Start+Search
- a×6n±1 (which includes a×36n±1): https://primes.utm.edu/primes/search_proth.php?base=6&min_k=&max_k=&min_n=&max_n=&plus=on&minus=on&number=1000000&search=Start+Search
- a×7n±1: https://primes.utm.edu/primes/search_proth.php?base=7&min_k=&max_k=&min_n=&max_n=&plus=on&minus=on&number=1000000&search=Start+Search
- a×10n±1: https://primes.utm.edu/primes/search_proth.php?base=10&min_k=&max_k=&min_n=&max_n=&plus=on&minus=on&number=1000000&search=Start+Search
- a×11n±1: https://primes.utm.edu/primes/search_proth.php?base=11&min_k=&max_k=&min_n=&max_n=&plus=on&minus=on&number=1000000&search=Start+Search
- a×12n±1: https://primes.utm.edu/primes/search_proth.php?base=12&min_k=&max_k=&min_n=&max_n=&plus=on&minus=on&number=1000000&search=Start+Search
- a×13n±1: https://primes.utm.edu/primes/search_proth.php?base=13&min_k=&max_k=&min_n=&max_n=&plus=on&minus=on&number=1000000&search=Start+Search
- a×14n±1: https://primes.utm.edu/primes/search_proth.php?base=14&min_k=&max_k=&min_n=&max_n=&plus=on&minus=on&number=1000000&search=Start+Search
- a×15n±1: https://primes.utm.edu/primes/search_proth.php?base=15&min_k=&max_k=&min_n=&max_n=&plus=on&minus=on&number=1000000&search=Start+Search
- a×17n±1: https://primes.utm.edu/primes/search_proth.php?base=17&min_k=&max_k=&min_n=&max_n=&plus=on&minus=on&number=1000000&search=Start+Search
- a×18n±1: https://primes.utm.edu/primes/search_proth.php?base=18&min_k=&max_k=&min_n=&max_n=&plus=on&minus=on&number=1000000&search=Start+Search
- a×19n±1: https://primes.utm.edu/primes/search_proth.php?base=19&min_k=&max_k=&min_n=&max_n=&plus=on&minus=on&number=1000000&search=Start+Search
- a×20n±1: https://primes.utm.edu/primes/search_proth.php?base=20&min_k=&max_k=&min_n=&max_n=&plus=on&minus=on&number=1000000&search=Start+Search
- a×21n±1: https://primes.utm.edu/primes/search_proth.php?base=21&min_k=&max_k=&min_n=&max_n=&plus=on&minus=on&number=1000000&search=Start+Search
- a×22n±1: https://primes.utm.edu/primes/search_proth.php?base=22&min_k=&max_k=&min_n=&max_n=&plus=on&minus=on&number=1000000&search=Start+Search
- a×23n±1: https://primes.utm.edu/primes/search_proth.php?base=23&min_k=&max_k=&min_n=&max_n=&plus=on&minus=on&number=1000000&search=Start+Search
- a×24n±1: https://primes.utm.edu/primes/search_proth.php?base=24&min_k=&max_k=&min_n=&max_n=&plus=on&minus=on&number=1000000&search=Start+Search
- a×26n±1: https://primes.utm.edu/primes/search_proth.php?base=26&min_k=&max_k=&min_n=&max_n=&plus=on&minus=on&number=1000000&search=Start+Search
- a×28n±1: https://primes.utm.edu/primes/search_proth.php?base=28&min_k=&max_k=&min_n=&max_n=&plus=on&minus=on&number=1000000&search=Start+Search
- a×29n±1: https://primes.utm.edu/primes/search_proth.php?base=29&min_k=&max_k=&min_n=&max_n=&plus=on&minus=on&number=1000000&search=Start+Search
- a×30n±1: https://primes.utm.edu/primes/search_proth.php?base=30&min_k=&max_k=&min_n=&max_n=&plus=on&minus=on&number=1000000&search=Start+Search
- a×31n±1: https://primes.utm.edu/primes/search_proth.php?base=31&min_k=&max_k=&min_n=&max_n=&plus=on&minus=on&number=1000000&search=Start+Search
- a×33n±1: https://primes.utm.edu/primes/search_proth.php?base=33&min_k=&max_k=&min_n=&max_n=&plus=on&minus=on&number=1000000&search=Start+Search
- a×34n±1: https://primes.utm.edu/primes/search_proth.php?base=34&min_k=&max_k=&min_n=&max_n=&plus=on&minus=on&number=1000000&search=Start+Search
- a×35n±1: https://primes.utm.edu/primes/search_proth.php?base=35&min_k=&max_k=&min_n=&max_n=&plus=on&minus=on&number=1000000&search=Start+Search
Probable primes (i.e. c ≠ ±1 and/or d ≠ 1):
-
bn+c: http://www.primenumbers.net/prptop/searchform.php?form=b%5En%2Bc&action=Search
-
bn−c: http://www.primenumbers.net/prptop/searchform.php?form=b%5En-c&action=Search
-
a×bn+c: http://www.primenumbers.net/prptop/searchform.php?form=a*b%5En%2Bc&action=Search
-
a×bn−c: http://www.primenumbers.net/prptop/searchform.php?form=a*b%5En-c&action=Search
-
(bn+c)/d: http://www.primenumbers.net/prptop/searchform.php?form=%28b%5En%2Bc%29%2Fd&action=Search
-
(bn−c)/d: http://www.primenumbers.net/prptop/searchform.php?form=%28b%5En-c%29%2Fd&action=Search
-
(a×bn+c)/d: http://www.primenumbers.net/prptop/searchform.php?form=%28a*b%5En%2Bc%29%2Fd&action=Search
-
(a×bn−c)/d: http://www.primenumbers.net/prptop/searchform.php?form=%28a*b%5En-c%29%2Fd&action=Search
-
2n+c: http://www.primenumbers.net/prptop/searchform.php?form=2%5En%2Bc&action=Search
-
2n−c: http://www.primenumbers.net/prptop/searchform.php?form=2%5En-c&action=Search
-
a×2n+c: http://www.primenumbers.net/prptop/searchform.php?form=a*2%5En%2Bc&action=Search
-
a×2n−c: http://www.primenumbers.net/prptop/searchform.php?form=a*2%5En-c&action=Search
-
(2n+c)/d: http://www.primenumbers.net/prptop/searchform.php?form=%282%5En%2Bc%29%2Fd&action=Search
-
(2n−c)/d: http://www.primenumbers.net/prptop/searchform.php?form=%282%5En-c%29%2Fd&action=Search
-
(a×2n+c)/d: http://www.primenumbers.net/prptop/searchform.php?form=%28a*2%5En%2Bc%29%2Fd&action=Search
-
(a×2n−c)/d: http://www.primenumbers.net/prptop/searchform.php?form=%28a*2%5En-c%29%2Fd&action=Search
-
3n+c: http://www.primenumbers.net/prptop/searchform.php?form=3%5En%2Bc&action=Search
-
3n−c: http://www.primenumbers.net/prptop/searchform.php?form=3%5En-c&action=Search
-
a×3n+c: http://www.primenumbers.net/prptop/searchform.php?form=a*3%5En%2Bc&action=Search
-
a×3n−c: http://www.primenumbers.net/prptop/searchform.php?form=a*3%5En-c&action=Search
-
(3n+c)/d: http://www.primenumbers.net/prptop/searchform.php?form=%283%5En%2Bc%29%2Fd&action=Search
-
(3n−c)/d: http://www.primenumbers.net/prptop/searchform.php?form=%283%5En-c%29%2Fd&action=Search
-
(a×3n+c)/d: http://www.primenumbers.net/prptop/searchform.php?form=%28a*3%5En%2Bc%29%2Fd&action=Search
-
(a×3n−c)/d: http://www.primenumbers.net/prptop/searchform.php?form=%28a*3%5En-c%29%2Fd&action=Search
-
10n+c: http://www.primenumbers.net/prptop/searchform.php?form=10%5En%2Bc&action=Search
-
10n−c: http://www.primenumbers.net/prptop/searchform.php?form=10%5En-c&action=Search
-
a×10n+c: http://www.primenumbers.net/prptop/searchform.php?form=a*10%5En%2Bc&action=Search
-
a×10n−c: http://www.primenumbers.net/prptop/searchform.php?form=a*10%5En-c&action=Search
-
(10n+c)/d: http://www.primenumbers.net/prptop/searchform.php?form=%2810%5En%2Bc%29%2Fd&action=Search
-
(10n−c)/d: http://www.primenumbers.net/prptop/searchform.php?form=%2810%5En-c%29%2Fd&action=Search
-
(a×10n+c)/d: http://www.primenumbers.net/prptop/searchform.php?form=%28a*10%5En%2Bc%29%2Fd&action=Search
-
(a×10n−c)/d: http://www.primenumbers.net/prptop/searchform.php?form=%28a*10%5En-c%29%2Fd&action=Search
Home page of Proth Primes Search (search of primes of the form k×2n+1 with odd k): http://www.prothsearch.com/
Home page of Riesel Prime Search (search of primes of the form k×2n−1 with odd k): https://web.archive.org/web/20210817181915/http://www.15k.org/
References of minimal primes (https://en.wikipedia.org/wiki/Minimal_prime_(recreational_mathematics), https://primes.utm.edu/glossary/xpage/MinimalPrime.html) (the original definition, i.e. prime > base (b) is not required):
- http://www.cs.uwaterloo.ca/~shallit/Papers/minimal5.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_11.pdf) (base 10)
- https://cs.uwaterloo.ca/~cbright/reports/mepn.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_17.pdf) (bases 2 to 30)
- https://cs.uwaterloo.ca/~shallit/Papers/br10.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_18.pdf) (bases 2 to 30)
- https://cs.uwaterloo.ca/~cbright/talks/minimal-slides.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_19.pdf) (bases 2 to 30)
- https://doi.org/10.1080/10586458.2015.1064048 (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_20.pdf) (bases 2 to 30)
- https://scholar.colorado.edu/downloads/hh63sw661 (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_16.pdf) (bases 2 to 10) (warning: the datas for bases 8 and 10 have errors, the data for base 8 misses the prime 6101 and the data for base 10 misses the primes 9001 and 9049 and instead wrongly includes the primes 90001, 90469, and 9000049, and the correct values of Sm for bases 8 and 10 are 15 and 26 (instead of 14 and 27), respectively)
- https://github.com/curtisbright/mepn-data (bases 2 to 30)
- https://github.com/curtisbright/mepn (bases 2 to 30)
- https://github.com/RaymondDevillers/primes (bases 28 to 50)
- http://recursed.blogspot.com/2006/12/prime-game.html (base 10)
- https://inzitan.blogspot.com/2007/07/prime-game.html (in Spain) (base 10)
- http://www.pourlascience.fr/ewb_pages/a/article-nombres-premiers-inevitables-et-pyramidaux-24978.php (in French) (base 10)
- http://villemin.gerard.free.fr/aNombre/TYPMULTI/PremInev.htm (base 10)
- https://schoolbag.info/mathematics/numbers/66.html (base 10)
- https://www.microsiervos.com/archivo/ciencia/2-3-5-7-11.html (in Spain) (base 10)
- https://math.stackexchange.com/questions/58292/how-to-check-if-an-integer-has-a-prime-number-in-it (base 10)
- https://www.metafilter.com/62794/3-is-an-odd-prime-5-is-an-odd-prime-7-is-an-odd-prime-9-is-a-very-odd-prime (base 10)
- https://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1165031124 (base 10)
- https://www.cristal.univ-lille.fr/profil/jdelahay/pls:2002:094.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_100.pdf) (bases 2 to 10) (warning: the data for base 8 has error, the data misses the primes 444641 and 444444441)
- https://logs.esolangs.org/freenode-esoteric/2011-02-04.html (bases 2 to 10) (warning: the data for base 8 has error, the data misses the prime 111 and instead wrongly includes the primes 1101, 101111, 600111, 1000011, 1000111, 4411111, 64111111, 601111111, 41111111111111111, and possibly 6111111111111111111111 if the author of this article continues to search)
- http://www.bitman.name/math/article/730 (in Italian) (bases 2 to 20)
- http://www.bitman.name/math/table/497 (in Italian) (bases 2 to 16)
- http://www.bitman.name/math/table/498 (in Italian) (base 17)
- http://www.bitman.name/math/table/499 (in Italian) (base 18)
- http://www.bitman.name/math/table/500 (in Italian) (base 19)
- http://www.bitman.name/math/table/501 (in Italian) (base 20)
- https://www.primepuzzles.net/puzzles/puzz_178.htm (base 10)
- https://oeis.org/A071062 (base 10)
Other researches for the digits of the primes:
Left-truncatable primes (https://en.wikipedia.org/wiki/Truncatable_prime, https://primes.utm.edu/glossary/xpage/LeftTruncatablePrime.html, https://mathworld.wolfram.com/TruncatablePrime.html, https://www.numbersaplenty.com/set/truncatable_prime/), i.e. every nonempty suffix is prime:
- http://primerecords.dk/left-truncatable.txt (base 10)
- http://chesswanks.com/num/LTPs/ (bases 3 to 120)
- https://rosettacode.org/wiki/Find_largest_left_truncatable_prime_in_a_given_base (bases 3 to 17)
- https://www.ams.org/journals/mcom/1977-31-137/S0025-5718-1977-0427213-2/S0025-5718-1977-0427213-2.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_28.pdf) (bases 3 to 11)
- http://www.primerecords.dk/left-truncatable.htm (base 10)
- http://rosettacode.org/wiki/Truncatable_primes (base 10)
- https://www.primepuzzles.net/puzzles/puzz_002.htm (base 10)
- https://web.archive.org/web/20041204160717/http://www.wschnei.de/digit-related-numbers/circular-primes.html (base 10)
- http://www.bitman.name/math/article/1155 (in Italian) (bases 2 to 20)
- http://www.bitman.name/math/table/524 (in Italian) (bases 2 to 20)
- https://oeis.org/A103443 (largest left-truncatable prime in base b)
- https://oeis.org/A103463 (length of the largest left-truncatable prime in base b)
- https://oeis.org/A076623 (number of left-truncatable primes in base b)
Right-truncatable primes (https://en.wikipedia.org/wiki/Truncatable_prime, https://primes.utm.edu/glossary/xpage/RightTruncatablePrime.html, https://mathworld.wolfram.com/TruncatablePrime.html, https://www.numbersaplenty.com/set/truncatable_prime/), i.e. every nonempty prefix is prime:
- http://primerecords.dk/right-truncatable.txt (base 10)
- http://fatphil.org/maths/rtp/rtp.html (bases 3 to 90)
- https://www.ams.org/journals/mcom/1977-31-137/S0025-5718-1977-0427213-2/S0025-5718-1977-0427213-2.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_28.pdf) (bases 3 to 15)
- http://rosettacode.org/wiki/Truncatable_primes (base 10)
- https://www.primepuzzles.net/puzzles/puzz_002.htm (base 10)
- https://web.archive.org/web/20041204160717/http://www.wschnei.de/digit-related-numbers/circular-primes.html (base 10)
- http://www.bitman.name/math/article/1155 (in Italian) (bases 2 to 20)
- http://www.bitman.name/math/table/525 (in Italian) (bases 2 to 20)
- https://oeis.org/A023107 (largest right-truncatable prime in base b)
- https://oeis.org/A103483 (length of the largest right-truncatable prime in base b)
- https://oeis.org/A076586 (number of right-truncatable primes in base b)
Other researches for the minimal elements of other subsets of positive integers written in the positional numeral system with radix b, as digit strings with subsequence ordering:
Primes == 1 mod 4:
- https://www.primepuzzles.net/puzzles/puzz_178.htm
- https://github.com/curtisbright/mepn-data/blob/master/data/primes1mod4/minimal.10.txt
- https://www.primepuzzles.net/puzzles/Minimal%20Primes%204k+1,%204k-1,%20pu%20178.doc (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/doc_1.doc) (warning: the data has many errors, the data wrongly including many primes which are not minimal primes, including the largest "minimal 4k+1 prime" in the list: 9630493, this prime is not a minimal 4k+1 prime since 9949 is also a prime == 1 mod 4, and 9949 is a subsequence of 9630493, there are 146 (instead of 173) minimal 4k+1 primes and 113 (instead of 138) minimal 4k−1 primes, and the largest minimal 4k+1 prime is 87733 = (8*1079−503)/9 instead of 9630493 = 10633−507)
- https://oeis.org/A111055
Primes == 3 mod 4:
- https://www.primepuzzles.net/puzzles/puzz_178.htm
- https://github.com/curtisbright/mepn-data/blob/master/data/primes3mod4/minimal.10.txt
- https://www.primepuzzles.net/puzzles/Minimal%20Primes%204k+1,%204k-1,%20pu%20178.doc (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/doc_1.doc) (warning: the data has many errors, the data wrongly including many primes which are not minimal primes, including the largest "minimal 4k+1 prime" in the list: 9630493, this prime is not a minimal 4k+1 prime since 9949 is also a prime == 1 mod 4, and 9949 is a subsequence of 9630493, there are 146 (instead of 173) minimal 4k+1 primes and 113 (instead of 138) minimal 4k−1 primes, and the largest minimal 4k+1 prime is 87733 = (8*1079−503)/9 instead of 9630493 = 10633−507)
- https://oeis.org/A111056 (warning: the b-file does not include the prime 21915199)
Palindromic primes:
- https://www.primepuzzles.net/puzzles/puzz_178.htm
- https://oeis.org/A114835 (warning: the b-file does not include the probable prime 9943401999)
Composites:
- https://github.com/curtisbright/mepn-data/tree/master/data/composites
- http://www.bitman.name/math/table/504
- https://oeis.org/A071070
Squares:
Powers of 2:
- https://oeis.org/A071071/a071071.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_13.pdf)
- https://oeis.org/A071071
Multiples of 3:
Multiples of 4:
Other sets:
- https://arxiv.org/pdf/1607.01548.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_14.pdf) (sums of three squares, quadratic residues mod 6, quadratic residues mod 7, range of Euler’s totient function, range of "Euler’s totient function + 3", range of Dedekind psi function, perfect numbers)
- https://nntdm.net/papers/nntdm-25/NNTDM-25-1-036-047.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_15.pdf) (range of "Euler’s totient function + n", for 0 ≤ n ≤ 5)
Tools about this research: (in fact, you can also use Wolfram Alpha (https://www.wolframalpha.com/) or online Magma calculator (http://magma.maths.usyd.edu.au/calc/) or Pari/GP (https://pari.math.u-bordeaux.fr/) or Wolfram Mathematica (https://www.wolfram.com/mathematica/) or Maple (https://www.maplesoft.com/))
Prime checkers:
- https://primes.utm.edu/curios/includes/primetest.php
- https://www.numberempire.com/primenumbers.php
- http://www.numbertheory.org/php/lucas.html
- http://www.javascripter.net/faq/numberisprime.htm
- http://www.javascripter.net/math/primes/millerrabinprimalitytest.htm
- http://www.javascripter.net/math/calculators/100digitbigintcalculator.htm (just type x and click "prime?")
- http://www.math.com/students/calculators/source/prime-number.htm
- https://www.calculatorsoup.com/calculators/math/prime-number-calculator.php
- https://onlinemathtools.com/test-prime-number
- https://www.bigprimes.net/primalitytest
- https://www.archimedes-lab.org/primOmatic.html
- http://www.sonic.net/~undoc/java/PrimeCalc.html
- http://www.primzahlen.de/primzahltests/testverfahren.htm (in German)
- http://www.proftnj.com/calcprem.htm (in French) (use the box "Rechercher si un nombre est premier" and click "Rechercher")
- https://primes.utm.edu/nthprime/ (calculate the nth prime)
- http://factordb.com/nextprime.php (calculate the next (probable) prime above N, in fact, links 2, 6, 10, 11, 12, 13 can also calculate the next prime above N, besides, links 2, 6 can also calculate the previous prime below N)
Integer factorizers:
- https://www.numberempire.com/numberfactorizer.php
- https://www.alpertron.com.ar/ECM.HTM
- http://www.javascripter.net/math/calculators/primefactorscalculator.htm
- https://betaprojects.com/calculators/prime_factors.html
- https://www.emathhelp.net/calculators/pre-algebra/prime-factorization-calculator/
- http://www.numbertheory.org/php/factor.html
- https://primefan.tripod.com/Factorer.html
- https://www.calculatorsoup.com/calculators/math/prime-factors.php
- https://www.calculator.net/prime-factorization-calculator.html
- http://www.se16.info/js/factor.htm
- http://math.fau.edu/Richman/mla/factor-f.htm
- http://www.rsok.com/~jrm/factor.html
- http://www.brennen.net/primes/FactorApplet.html (need run with Java)
- https://web.archive.org/web/20161004191531/http://britton.disted.camosun.bc.ca/jbprimefactor.htm
- http://wims.unice.fr/~wims/en_tool~algebra~factor.en.html
- http://www.analyzemath.com/Calculators_3/prime_factors.html
- https://www.archimedes-lab.org/primOmatic.html
- http://www.proftnj.com/calcprem.htm (in French) (use the box "Factoriser un nombre" and click "Factoriser")
- http://factordb.com/ (online factor database)
- http://myfactorcollection.mooo.com:8090/dbio.html (online factor database for numbers of the form bn±1)
- https://web.archive.org/web/20120722020628/http://homes.cerias.purdue.edu/~ssw/cun/prime.php (online factor database for numbers of the form bn±1 for 2 ≤ b ≤ 12)
- https://web.archive.org/web/20120330032919/http://homes.cerias.purdue.edu/~ssw/cun/clientold.html (online factor database for numbers of the form bn±1 for 2 ≤ b ≤ 12)
Base converters:
- https://baseconvert.com/
- https://baseconvert.com/high-precision
- https://baseconvert.com/ieee-754-floating-point (for IEEE 754 (https://en.wikipedia.org/wiki/IEEE_754))
- https://www.calculand.com/unit-converter/zahlen.php?og=Base+2-36&ug=1
- https://www.calculand.com/unit-converter/zahlen.php?og=Base62&ug=1
- https://www.calculand.com/unit-converter/zahlen.php?og=Base64&ug=1
- https://www.calculand.com/unit-converter/zahlen.php?og=Base85&ug=1
- https://www.calculand.com/unit-converter/zahlen.php?og=System+calculand&ug=1
- http://www.math.com/students/converters/source/base.htm
- https://www.dcode.fr/base-n-convert
- https://www.cut-the-knot.org/Curriculum/Algorithms/BaseConversion.shtml
- http://www.tonymarston.net/php-mysql/converter.php
- http://math.fau.edu/Richman/mla/convert.htm
- https://web.archive.org/web/20190629223750/http://thedevtoolkit.com/tools/base_conversion
- http://www.kwuntung.net/hkunit/base/base.php (in Chinese)
- https://linesegment.web.fc2.com/application/math/numbers/RadixConversion.html (in Japanese)
- http://factordb.com/index.php?showid=1000000000000000127 (you can change the "showid" to the ID for your number)
Expression generators:
- https://stdkmd.net/nrr/exprgen.htm (only support base 10 forms)
- https://www.numberempire.com/simplifyexpression.php (e.g. for the form 5{7} in base 11, type "5*11^n+7*(11^n-1)/10")
Lists of small primes: (see https://primes.utm.edu/notes/faq/LongestList.html and https://primes.utm.edu/notes/faq/x_digit_primes.html, although we can quickly determine whether a number < 10300 is prime or not, but there is no list of all primes < 10300, since the space which we need is larger than the number of elementary particles (https://en.wikipedia.org/wiki/Elementary_particle) (i.e. quarks (https://en.wikipedia.org/wiki/Quark) and electrons (https://en.wikipedia.org/wiki/Electron)) in the universe (https://en.wikipedia.org/wiki/Universe))
- https://primes.utm.edu/lists/small/1000.txt
- https://primes.utm.edu/lists/small/10000.txt
- https://primes.utm.edu/lists/small/100000.txt
- https://primes.utm.edu/lists/small/millions/
- https://oeis.org/A000040/b000040.txt
- https://oeis.org/A000040/a000040.txt
- https://oeis.org/A000040/b000040_1.txt
- https://oeis.org/A000040/a000040_1B.7z
- http://www.prime-numbers.org/
- http://prime-numbers.org/sample.zip
- https://metanumbers.com/prime-numbers
- https://www.calculatorsoup.com/calculators/math/prime-numbers.php
- https://www2.cs.arizona.edu/icon/oddsends/primes.htm
- https://www.numbersaplenty.com/set/prime_number/more.php
- https://cdn1.byjus.com/wp-content/uploads/2021/10/Prime-Numbers-from-1-to-1000.png
- http://noe-education.org/D11102.php (in French)
- https://web.archive.org/web/20060513054350/http://www.walter-fendt.de/m14i/primes_i.htm (in Italian)
- https://primefan.tripod.com/500Primes1.html (warning: this site incorrectly includes 1 as a prime and misses the primes 3229 and 3329)
- https://www.gutenberg.org/files/65/65.txt
- http://www.primos.mat.br/indexen.html
- https://www.walter-fendt.de/html5/men/primenumbers_en.htm
- http://www.rsok.com/~jrm/printprimes.html
- http://www.numbertheory.org/php/prime_generator.html
- http://www.primzahlen.de/primzahltests/2-100003.htm (in German)
- https://jocelyn.quizz.chat/np/cache/index.html (in French)
- http://www.sosmath.com/tables/prime/prime.html
- https://www.bigprimes.net/archive/prime
- https://web.archive.org/web/20201130071856/http://www.mathematical.com/primelist1to100kk.html
- https://web.archive.org/web/20191118082053/http://www.tsm-resources.com/alists/prim.html
- https://web.archive.org/web/20090917191047/http://planetmath.org/encyclopedia/FirstThousandPositivePrimeNumbers.html
- https://faculty.lynchburg.edu/~nicely/gaps/gaplist.html (the longest list ever calculated, with all primes < 264 (but unlikely other lists here, the primes are not all stored))
- https://en.wikipedia.org/wiki/List_of_prime_numbers#The_first_1000_prime_numbers
Lists of factorizations of small integers:
- http://primefan.tripod.com/500factored.html
- http://www.sosmath.com/tables/factor/factor.html
- https://sites.google.com/view/prime-factorization-of-integer
- https://web.archive.org/web/20060210182347/http://bearnol.is-a-geek.com/Panfur%20Project/ (warning: this site does not factor the composite numbers 15, 51, 85, 91, 255, 435, 451, 561, 595, 679, 703, 771, 1105, 1261, 1285, 1351, 1387, ...)
- http://www.datapointed.net/visualizations/math/factorization/animated-diagrams/
- http://www.datapointed.net/visualizations/math/factorization/animated-diagrams/?infinity
- https://oeis.org/A027750/a027750.txt (all (prime or composite or unit) factors of N)
- http://factorzone.tripod.com/factors.htm (all (prime or composite or unit) factors of N)
- http://functions.wolfram.com/NumberTheoryFunctions/Divisors/03/02 (all (prime or composite or unit) factors of N)
- https://en.wikipedia.org/wiki/Table_of_prime_factors
- https://en.wikipedia.org/wiki/Table_of_divisors (all (prime or composite or unit) factors of N)
- http://factordb.com/index.php?query=n&use=n&n=0&VP=on&VC=on&EV=on&OD=on&PR=on&FF=on&PRP=on&CF=on&U=on&C=on&perpage=200&format=1&sent=Show (from factordb)
Lists of small integers in various bases:
Also, programs related to this research: (some of these programs can also be downloaded in http://www.fermatsearch.org/download.php or https://www.mersenne.org/download/freeware.php or https://download.mersenne.ca/) (some of these programs need to use GMP (https://gmplib.org/))
Primality (or probable primality) testing (https://en.wikipedia.org/wiki/Primality_test, https://www.rieselprime.de/ziki/Primality_test, https://mathworld.wolfram.com/PrimalityTest.html, https://primes.utm.edu/prove/index.html) programs (https://www.rieselprime.de/ziki/Primality_testing_program):
- LLR (http://jpenne.free.fr/index2.html, https://primes.utm.edu/bios/page.php?id=431, https://www.rieselprime.de/ziki/LLR, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/llr403win64, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/llr403linux64)
- PFGW (https://sourceforge.net/projects/openpfgw/, https://primes.utm.edu/bios/page.php?id=175, https://www.rieselprime.de/ziki/PFGW, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/pfgw_win_4.0.3)
- Primo (http://www.ellipsa.eu/public/primo/primo.html, http://www.rieselprime.de/dl/Primo309.zip, https://primes.utm.edu/bios/page.php?id=46, https://www.rieselprime.de/ziki/Primo, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/primo-433-lx64, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/Primo309)
- Proth.exe (https://primes.utm.edu/programs/gallot/, https://primes.utm.edu/bios/page.php?id=411, https://www.rieselprime.de/ziki/Proth.exe, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/proth)
- CHG (https://mersenneforum.org/attachment.php?attachmentid=21133&d=1571237465, https://primes.utm.edu/bios/page.php?id=797, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/CHG)
Sieving (https://www.rieselprime.de/ziki/Sieving, https://www.rieselprime.de/ziki/Sieving_a_range_of_sequences, https://mathworld.wolfram.com/Sieve.html, http://www.rechenkraft.net/yoyo/y_status_sieve.php) programs (https://www.rieselprime.de/ziki/Sieving_program):
- SRSieve (https://www.bc-team.org/app.php/dlext/?cat=3, http://web.archive.org/web/20160922072340/https://sites.google.com/site/geoffreywalterreynolds/programs/, http://www.rieselprime.de/dl/CRUS_pack.zip, https://primes.utm.edu/bios/page.php?id=905, https://www.rieselprime.de/ziki/Srsieve, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/srsieve_1.1.4, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/sr1sieve_1.4.6, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/sr2sieve_2.0.0, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/srbsieve)
- MTSieve (https://sourceforge.net/projects/mtsieve/, https://primes.utm.edu/bios/page.php?id=449, https://www.rieselprime.de/ziki/Mtsieve, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/mtsieve_2.3.3)
- NewPGen (https://primes.utm.edu/programs/NewPGen/, https://primes.utm.edu/bios/page.php?id=105, https://www.rieselprime.de/ziki/NewPGen, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/newpgen, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/newpgenlinux)
Integer factoring (https://en.wikipedia.org/wiki/Integer_factorization, https://www.rieselprime.de/ziki/Factorization, https://mathworld.wolfram.com/PrimeFactorization.html, https://mathworld.wolfram.com/PrimeFactorizationAlgorithms.html, http://www.numericana.com/answer/factoring.htm) programs (https://www.rieselprime.de/ziki/Factoring_program):
- GMP-ECM (https://web.archive.org/web/20210803045418/https://gforge.inria.fr/projects/ecm, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/ecm704dev-svn2990-win64, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/ecm704dev-svn2990-linux64, https://www.rieselprime.de/ziki/GMP-ECM)
- MSieve (https://sourceforge.net/projects/msieve, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/msieve153_win64)
- GGNFS (http://sourceforge.net/projects/ggnfs, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/GGNFS)
- CADO-NFS (https://web.archive.org/web/20210506173015/http://cado-nfs.gforge.inria.fr/index.html, https://www.rieselprime.de/ziki/CADO-NFS, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/cado-nfs-2.3.0)
- YAFU (http://bbuhrow.googlepages.com/home, https://github.com/bbuhrow/yafu)
- YTools (https://github.com/bbuhrow/ytools)
- YSieve (https://github.com/bbuhrow/ysieve)
For the files in this page:
- File "kernel b": Data for all known minimal primes in base b, expressed as base b strings
- File "left b": x{y}z (where x and z are strings (may be empty) of digits in base b, y is a digit in base b) families in base b such that we were unable to determine if they contain a prime > b or not (i.e. x{y}z (where x and z are strings (may be empty) of digits in base b, y is a digit in base b) families in base b such that no prime member > b could be found, nor could the family be ruled out as only containing composites (only count the numbers > b)), these families are sorted by "the length n number in these families, from the smallest number to the largest number, this n is large enough such that n replaced to any larger number does not affect the sorting" (e.g. for base 17, we sort with B{0}B3 -> B{0}DB -> {B}2BE -> {B}2E -> {B}E9 -> {B}EE, since in this case 7 digits is enough, B0000B3 < B0000DB < BBBB2BE < BBBBB2E < BBBBBE9 < BBBBBEE, if the 7 replaced to any larger number, this result of the sorting will not change)
See my article about this research: https://docs.google.com/document/d/e/2PACX-1vQct6Hx-IkJd5-iIuDuOKkKdw2teGmmHW-P75MPaxqBXB37u0odFBml5rx0PoLa0odTyuW67N_vn96J/pub