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/

Primality of these probable primes (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, 28, 30) 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, 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), if they are in fact primes, then they are minimal primes to the corresponding bases.

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 (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 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.

The "primoinput" files are the input files for 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) (local copy from factordb (http://factordb.com/)), they should be renamed to ".in" files before inputting to Primo. (there is no input files for Primo for the PRP 95197420 in base 13 (which equals the PRP (113×13197420−5)/12) since this PRP is too large (>10150000) to be PRP-tested in factordb, and factordb does not have input files for Primo for numbers with status (http://factordb.com/status.html) "U", factordb only has input files for Primo for numbers with status "PRP")

e.g. File "primoinput11_1068" is the input files for Primo for the 1068th minimal prime in base 11, i.e. the input files for Primo for the PRP 5762668 in base 11, which equals the PRP (57×1162668−7)/10.