Skip to content
main
Switch branches/tags

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?
minimal-elements-of-the-prime-numbers/unproven-probable-primes/
minimal-elements-of-the-prime-numbers/unproven-probable-primes/

Files

Permalink
Failed to load latest commit information.
Type
Name
Latest commit message
Commit time

Primality of these 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) in the minimal sets for bases 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 ≤ 10 unsolved families) are not certificated yet (technically, probable primality tests (https://en.wikipedia.org/wiki/Probabilistic_algorithm) such as Miller–Rabin primality test (https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test, https://primes.utm.edu/glossary/xpage/MillersTest.html, https://www.rieselprime.de/ziki/Miller-Rabin_pseudoprimality_test, https://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html) and Baillie–PSW primality test (https://en.wikipedia.org/wiki/Baillie%E2%80%93PSW_primality_test, https://mathworld.wolfram.com/Baillie-PSWPrimalityTest.html) are used for these numbers (and thus these numbers are only probable primes and not definitely primes (https://en.wikipedia.org/wiki/Provable_prime), i.e. they might be pseudoprimes (https://en.wikipedia.org/wiki/Pseudoprime, https://primes.utm.edu/glossary/xpage/Pseudoprime.html, https://www.rieselprime.de/ziki/Pseudoprime, https://mathworld.wolfram.com/Pseudoprime.html)), because of their sizes and neither N−1 nor N+1 can be ≥ 1/4 factored (https://en.wikipedia.org/wiki/Integer_factorization, https://www.rieselprime.de/ziki/Factorization, https://mathworld.wolfram.com/PrimeFactorization.html), all known primality tests (https://en.wikipedia.org/wiki/Primality_test, https://www.rieselprime.de/ziki/Primality_test, https://mathworld.wolfram.com/PrimalityTest.html) run far too slowly (the CPU time (https://en.wikipedia.org/wiki/CPU_time) is longer than the age of the universe (https://en.wikipedia.org/wiki/Age_of_the_universe), 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, the only known primality test with polynomial time (https://en.wikipedia.org/wiki/Time_complexity#Polynomial_time, https://mathworld.wolfram.com/PolynomialTime.html) of the number of digits is AKS primality test (https://en.wikipedia.org/wiki/AKS_primality_test, https://mathworld.wolfram.com/AKSPrimalityTest.html), but it has time complexity (https://en.wikipedia.org/wiki/Time_complexity) O(log(n)12) (where O is the big O notation (https://en.wikipedia.org/wiki/Big_O_notation, https://primes.utm.edu/glossary/xpage/BigOh.html, https://mathworld.wolfram.com/Big-ONotation.html), log 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)) and too large, also a near-polynomial time (although not completely polynomial time) primality test, APR primality test (https://en.wikipedia.org/wiki/Adleman%E2%80%93Pomerance%E2%80%93Rumely_primality_test, https://www.rieselprime.de/ziki/Adleman%E2%80%93Pomerance%E2%80%93Rumely_primality_test, https://mathworld.wolfram.com/Adleman-Pomerance-RumelyPrimalityTest.html, https://primes.utm.edu/prove/prove4_1.html), which has time complexity O(log(n)log(log(log(n)))) and also too large), all of these probable primes are > 1025000, if they are in fact primes, then they are minimal primes to the corresponding bases.

Primes p such that p−1 has many factors Primes p such that p+1 has many factors
Fermat probable 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) Lucas probable primality test (https://en.wikipedia.org/wiki/Lucas_pseudoprime, https://mathworld.wolfram.com/LucasPseudoprime.html)
Miller–Rabin probable 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) Strong Lucas probable primality test (https://en.wikipedia.org/wiki/Lucas_pseudoprime#Strong_Lucas_pseudoprimes, https://mathworld.wolfram.com/StrongLucasPseudoprime.html)
Carmichael number (https://oeis.org/A002997, https://en.wikipedia.org/wiki/Carmichael_number, https://primes.utm.edu/glossary/xpage/CarmichaelNumber.html, https://mathworld.wolfram.com/CarmichaelNumber.html) Lucas–Carmichael number (https://oeis.org/A006972, https://en.wikipedia.org/wiki/Lucas%E2%80%93Carmichael_number)
Euler’s totient function (https://oeis.org/A000010, https://en.wikipedia.org/wiki/Euler%27s_totient_function, https://primes.utm.edu/glossary/xpage/EulersPhi.html, https://mathworld.wolfram.com/TotientFunction.html), its range is https://oeis.org/A002202, and the even numbers not in its range are https://oeis.org/A005277 Dedekind psi function (https://oeis.org/A001615, https://en.wikipedia.org/wiki/Dedekind_psi_function, https://mathworld.wolfram.com/DedekindFunction.html), its range is https://oeis.org/A203444, and the even numbers not in its range are https://oeis.org/A307055
Pépin primality test (https://en.wikipedia.org/wiki/P%C3%A9pin%27s_test, https://primes.utm.edu/glossary/xpage/PepinsTest.html, https://www.rieselprime.de/ziki/P%C3%A9pin%27s_test, https://mathworld.wolfram.com/PepinsTest.html) for Fermat numbers (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), i.e. numbers of the form 2n+1 (https://oeis.org/A000051), if 2n+1 is prime, then n must be power of 2, such numbers are https://oeis.org/A000215, and such primes are https://oeis.org/A019434 Lucas–Lehmer primality test (https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test, https://www.rieselprime.de/ziki/Lucas-Lehmer_test, https://mathworld.wolfram.com/Lucas-LehmerTest.html) for Mersenne numbers (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), i.e. numbers of the form 2n−1 (https://oeis.org/A000225), if 2n−1 is prime, then n must be prime, such numbers are https://oeis.org/A001348, and such primes are https://oeis.org/A000668
Pépin primality test numbers: https://oeis.org/A060377 Lucas–Lehmer primality test numbers: https://oeis.org/A003010
Residues of Pépin primality test for Fermat numbers: https://oeis.org/A152153 Residues of Lucas–Lehmer primality test for Mersenne numbers: https://oeis.org/A095847
Possible bases for Pépin primality test for Fermat numbers (the original base for Pépin primality test is 3): https://oeis.org/A129802 Possible starting values for Lucas–Lehmer primality test for Mersenne numbers (the original starting value for Lucas–Lehmer primality test is 4): https://oeis.org/A018844
Proth primality test (https://en.wikipedia.org/wiki/Proth%27s_theorem, https://www.rieselprime.de/ziki/Proth%27s_theorem, https://mathworld.wolfram.com/ProthsTheorem.html) for numbers of the form k×2n+1 with k odd and k < 2n, such numbers are called "Proth numbers" (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), and such primes are called "Proth primes", such numbers are https://oeis.org/A080075, and such primes are https://oeis.org/A080076 Lucas–Lehmer–Riesel primality test (https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer%E2%80%93Riesel_test) for numbers of the form k×2n−1 with k odd and k < 2n, such numbers are called "Proth numbers of the second kind" (https://www.rieselprime.de/ziki/Riesel_prime), and such primes are called "Proth primes of the second kind", such numbers are https://oeis.org/A112714, and such primes are https://oeis.org/A112715
Pocklington N−1 primality test (https://primes.utm.edu/prove/prove3_1.html, https://en.wikipedia.org/wiki/Pocklington_primality_test, https://www.rieselprime.de/ziki/Pocklington%27s_theorem, https://mathworld.wolfram.com/PocklingtonsTheorem.html) for numbers N such that N−1 can be ≥ 1/3 factored Morrison N+1 primality test (https://primes.utm.edu/prove/prove3_2.html) for numbers N such that N+1 can be ≥ 1/3 factored
Sierpiński problem (http://www.prothsearch.com/sierp.html, http://www.primegrid.com/forum_thread.php?id=1647, http://www.primegrid.com/stats_sob_llr.php, 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://mathworld.wolfram.com/SierpinskiNumberoftheSecondKind.html), finding and proving the smallest odd k such that k×2n+1 is composite for all n ≥ 1, the smallest such k is conjectured to be 78557, such k are called Sierpiński numbers Riesel problem (http://www.prothsearch.com/rieselprob.html, http://www.primegrid.com/forum_thread.php?id=1731, http://www.primegrid.com/stats_trp_llr.php, https://en.wikipedia.org/wiki/Riesel_number, https://primes.utm.edu/glossary/xpage/RieselNumber.html, https://www.rieselprime.de/ziki/Riesel_problem, https://mathworld.wolfram.com/RieselNumber.html), finding and proving the smallest odd k such that k×2n−1 is composite for all n ≥ 1, the smallest such k is conjectured to be 509203, such k are called Riesel numbers
Generalized Sierpiński problems to bases b > 2 (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/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)), finding and proving the smallest k such that k×bn+1 is composite for all n ≥ 1 Generalized Riesel problems to bases b > 2 (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/all_ck_riesel.txt), finding and proving the smallest k such that k×bn−1 is composite for all n ≥ 1
Pollard P−1 integer factorization method (https://en.wikipedia.org/wiki/Pollard%27s_p_%E2%88%92_1_algorithm, https://www.rieselprime.de/ziki/P-1_factorization_method, https://mathworld.wolfram.com/Pollardp-1FactorizationMethod.html) Williams P+1 integer factorization method (https://en.wikipedia.org/wiki/Williams%27s_p_%2B_1_algorithm, https://www.rieselprime.de/ziki/P%2B1_factorization_method, https://mathworld.wolfram.com/WilliamspPlus1FactorizationMethod.html)

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 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 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) to 1016 (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 since all of them are > 1025000, thus the property that they are in fact composite is less than 10−2000 (but still not zero!), 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) (bases 11, 16, 22, 30 have no unsolved families but have unproven PRPs, thus, we can 99.999999...999999% (with >2000 9's) say that the minimal sets for bases 11, 16, 22, 30 are these four sets, but we still cannot 100% say this)

A reference of many types of pseudoprimes: http://ntheory.org/pseudoprimes.html

If 5762668 (base 11) is in fact composite, then 5{7} will be an additional unsolved family for base 11.

If C523755C (base 13) is in fact composite, then C{5}C will be an additional unsolved family for base 13.

If 8032017111 (base 13) is in fact composite, then 8{0}111 will be an additional unsolved family for base 13.

If 95197420 (base 13) is in fact composite, then 9{5} will be an additional unsolved family for base 13.

If DB32234 (base 16) is in fact composite, then D{B} will be an additional unsolved family for base 16.

If 472785DD (base 16) is in fact composite, then {4}DD will be an additional unsolved family for base 16.

If 3116137AF (base 16) is in fact composite, then {3}AF will be an additional unsolved family for base 16.

If BK220015 (base 22) is in fact composite, then B{K}5 will be an additional unsolved family for base 22.

If 5193916F (base 26) is in fact composite, then {5}6F will be an additional unsolved family for base 26.

If 720279OL (base 26) is in fact composite, then {7}OL will be an additional unsolved family for base 26.

If LD0209757 (base 26) is in fact composite, then LD{0}7 will be an additional unsolved family for base 26.

If 6K233005 (base 26) is in fact composite, then 6{K}5 will be an additional unsolved family for base 26.

If J044303KCB (base 26) is in fact composite, then J{0}KCB will be an additional unsolved family for base 26.

If M0611862BB (base 26) is in fact composite, then M{0}2BB will be an additional unsolved family for base 26.

If N624051LR (base 28) is in fact composite, then N{6}LR will be an additional unsolved family for base 28.

If 5OA31238F (base 28) is in fact composite, then 5O{A}F will be an additional unsolved family for base 28 (unless a prime in the family O{A}F is known, since the family 5O{A}F is covered by the unsolved family O{A}F (if the prime in the family 5O{A}F has longer length than the prime in the family O{A}F) (i.e. the family O{A}F is a subfamily of the family 5O{A}F), and there is still a possibility that the smallest prime in the family 5O{A}F has longer length than the smallest prime in the family O{A}F, thus we still cannot definitely say that there are 25529 minimal primes in base 28 even if we assume the heuristic argument (https://en.wikipedia.org/wiki/Heuristic_argument, https://primes.utm.edu/glossary/xpage/Heuristic.html, https://mathworld.wolfram.com/Heuristic.html) that all unsolved families have a prime).

If O4O945359 (base 28) is in fact composite, then O4{O}9 will be an additional unsolved family for base 28.

If I024608D (base 30) is in fact composite, then I{0}D will be an additional unsolved family for base 30.

If 7K26567Z (base 36) is in fact composite, then 7{K}Z will be an additional unsolved family for base 36.

If S0750078H (base 36) is in fact composite, then S{0}8H will be an additional unsolved family for base 36.

If P81993SZ (base 36) is in fact composite, then {P}SZ will be an additional unsolved family for base 36.

For the files in this page:

File "unprovenPRP b": The unproven probable primes which are minimal primes in base b (assuming their primality), expressed as base b strings with x(y^n)z format (y^n means n copies of y, e.g. 34(5^6)78 is 3455555578)

File "primoinput b n": The input file for Primo for the nth minimal prime in base b (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) (local copy from factordb (http://factordb.com/)), they should be renamed to ".in" files before inputting to Primo, e.g. file "primoinput11_1068" is the input file for Primo for the 1068th minimal prime in base 11, i.e. the input file for Primo for the PRP 5762668 in base 11, which equals the PRP (57×1162668−7)/10. (Note: There is no input file for Primo for the PRP 95197420 in base 13 (which equals the PRP (113×13197420−5)/12) since this PRP is too large (>10149999) to be PRP-tested in factordb, and factordb does not have input file for Primo for numbers with status (http://factordb.com/status.html) "U", factordb only has input file for Primo for numbers with status "PRP")