Minimal set of the strings for primes with at least two digits - Page 5

sweety439 · 2020-12-30, 04:52

In base 9, family {3}{0}5 does not need to be tested because....

* If the number of digits 3 is even, then the number is divisible by 5.
* If the number of digits 3 is odd, then the number is divisible by 2.

Thus, this family has a numerical covering set {2,5} and is ruled out to only contain composites.

Note that {3}{0}5 is not simple family (simple families are x{d}y with d digit, x,y strings of digits (can be empty string))

In base 9, many such non-simple families exist, e.g. {1}6{1}, see page 13 of https://cs.uwaterloo.ca/~cbright/reports/mepn.pdf

sweety439 · 2020-12-30, 05:04

Some simple families which are ruled out to only contain composites: (all substrings with length >=2 of all numbers in these families are not primes, except base 8 6{4}7 and 60{4}7 families, they are listed here because all substrings with length >=2 of all numbers with <220 4's in these two families are not primes)

Base 5:

3{0}1 (divisible by 2)

Base 6:

4{0}1 (divisible by 5)

Base 8:

1{0}1 (sum of cubes)
2{0}5 (divisible by 7)
4{0}3 (divisible by 7)
44{0}3 (divisible by 3)
6{0}1 (divisible by 7)
6{4}7 (divisible by 3, 5, or 13)
60{4}7 (divisible by 17)

Base 9:

{1} (difference of squares)
{1}5 (divisible by 2 or 5)
2{7} (divisible by 2 or 5)
3{1} (difference of squares)
{3}5 (divisible by 2 or 5)
{3}8 (divisible by 2 or 5)
3{8} (difference of squares)
5{1} (divisible by 2 or 5)
5{7} (divisible by 2 or 5)
6{1} (divisible by 2 or 5)
{7}2 (divisible by 2 or 5)
{7}5 (divisible by 2 or 5)
{8}5 (difference of squares)

Base 10:

4{6}9 (divisible by 7)

Base 12:

A{0}1 (divisible by 11)
{B}9B (even number of B's is difference of squares, odd number of B's is divisible by 13)

Base 14:

3{D} (divisible by 3 or 5)
4{0}1 (divisible by 3 or 5)
8{D} (even number of D's is difference of squares, odd number of D's is divisible by 5)
A{D} (divisible by 3 or 5)
B{0}1 (divisible by 3 or 5)
{D}3 (divisible by 3 or 5)
{D}5 (even number of D's is divisible by 5, odd number of D's is difference of squares)

Base 16:

1{5} (difference of squares)
8{F} (difference of squares)
{C}D (x^4+4*y^4)
{F}7 (difference of squares)

Base 17:

1{9} (even number of 9's is difference of squares, odd number of 9's is divisible by 2)

Base 20:

7{J} (divisible by 3 or 7)
8{0}1 (divisible by 3 or 7)
C{J} (divisible by 3 or 7)
D{0}1 (divisible by 3 or 7)

Base 24:

3{N} (even number of N's is difference of squares, odd number of N's is divisible by 5)
5{N} (even number of N's is divisible by 5, odd number of N's is difference of squares)
{6}1 (even number of 6's is difference of squares, odd number of 6's is divisible by 5)
8{N} (even number of N's is difference of squares, odd number of N's is divisible by 5)

Base 25:

{1} (difference of squares)
1{3} (difference of squares)
1{8} (difference of squares)
D{1} (divisible by 2 or 13)

Base 27:

8{0}1 (sum of cubes)
9{G} (difference of cubes)
{D}E (sum of cubes)

Base 32:

1{0}1 (sum of 5th powers)
{1} (difference of 5th powers, the only trivial is 11111, but 11111 is not prime)

Base 38:

C{b} (divisible by 3, 5, or 17)
G{0}1 (divisible by 3, 5, or 17)

Base 47:

8{0}1 (divisible by 3, 5, or 13)
D{k} (divisible by 3, 5, or 13)
G{0}1 (divisible by 3, 5, or 17)

sweety439 · 2020-12-30, 05:35

Quote:

Originally Posted by sweety439

Base b minimal primes (start with 2 digits) includes:

* The smallest repunit prime base b if exists
* The smallest generalized Fermat prime base b for even b if exists
* The smallest generalized half Fermat prime (> (b+1)/2) base b for odd b if exists
* The smallest Williams prime with 1st kind base b if exists
* The smallest Williams prime with 2nd kind base b if exists
* The smallest Williams prime with 4th kind base b for bases b which no generalized Fermat primes exist (this includes all odd bases) and b is not prime (this condition is not needed if as LaurV's suggestion, the prime 10 (=b) is also excluded) if exists
* The smallest dual Williams prime with 1st kind base b if exists
* The smallest dual Williams prime with 2nd kind base b for composite bases b (this condition is not needed if as LaurV's suggestion, the prime 10 (=b) is also excluded) if exists
* The smallest dual Williams prime with 4th kind base b for bases b which no generalized Fermat primes exist (this includes all odd bases) and b is not prime (this condition is not needed if as LaurV's suggestion, the prime 10 (=b) is also excluded) if exists
* The smallest prime of the form 2*b^n+1 for bases b>2 if exists
* The smallest prime of the form 2*b^n-1 for bases b>2 if exists
* The smallest prime of the form b^n+2 for bases b>2 with gcd(b,2)=1 for composite bases b (this condition is not needed if as LaurV's suggestion, the prime 10 (=b) is also excluded) if exists
* The smallest prime of the form b^n-2 for bases b>2 with gcd(b,2)=1 if exists
* The smallest prime of the form 3*b^n+1 for bases b>3 if exists
* The smallest prime of the form 3*b^n-1 for bases b>3 if exists
* The smallest prime of the form b^n+3 for bases b>3 with gcd(b,3)=1 for composite bases b (this condition is not needed if as LaurV's suggestion, the prime 10 (=b) is also excluded) if exists
* The smallest prime of the form b^n-3 for bases b>3 with gcd(b,3)=1 if exists
* The smallest prime of the form 4*b^n+1 for bases b>4 if exists
* The smallest prime of the form 4*b^n-1 for bases b>4 if exists
* The smallest prime of the form b^n+4 for bases b>4 with gcd(b,4)=1 for composite bases b (this condition is not needed if as LaurV's suggestion, the prime 10 (=b) is also excluded) if exists
* The smallest prime of the form b^n-4 for bases b>4 with gcd(b,4)=1 if exists
...
* The smallest prime of the form k*b^n+1 for fixed 1<=k<=b-1 (i.e. the prime for the CRUS Sierpinski conjecture for fixed 1<=k<=b-1) if exists
* The smallest prime of the form k*b^n-1 for fixed 1<=k<=b-1 (i.e. the prime for the CRUS Riesel conjecture for fixed 1<=k<=b-1) if exists
* The smallest prime of the form b^n+k for fixed 1<=k<=b-1 if exists
* The smallest prime of the form b^n-k for fixed 1<=k<=b-1 if exists
* The smallest prime of the form (k*b^n-1)/gcd(k-1,b-1) for fixed k with 0<=(k-1)/gcd(k-1,b-1)<=b-1 and gcd(k-1,b-1) < b-1 (this reason is because if the repeating digit is 1, then this prime may not be minimal prime (start with 2 digits), unless there are no repunit primes base b (e.g. b = 9, 25, 32, 49, 64, 81, ...) (i.e. the prime for the extended Riesel conjecture for fixed k satisfying these two conditions) if exists
* The smallest prime of the form (b^n-k)/gcd(k-1,b-1) for fixed k with gcd(b,k) = 1 and 0<=k<=b-1

These are the minimal primes (start with 2 digits) in base b for 2<=b<=64:

* The smallest repunit prime base b:

3, 13, 5, 31, 7, 2801, 73, (not exist), 11, 50544702849929377, 13, 30941, 211, 241, 17, 307, 19, 109912203092239643840221, 421, 463, 23, 292561, 601, (not exist), 321272407, 757, 29, 732541, 31, 917087137, (not exist), 1123, 2458736461986831391, 57785511861854089559605684285384747472873075954938549266821996762520614682090417010479587236790517340193840109863642510356045237096340500854836834673594590986502765133399405931445515950293723048093118292954035082630781507315268041070570042738804650015484793905221070413101021864355439951875266340353210153398276807146377561258956649022201316646128234211457693681312361704211065831222237374054447781785197765525068555496240581389620280398439369732560881984414556748507653965669519761, 37, 6765811783780036261, 1483, 50322737201397037309232643922534935391510719645806123027236338191297773996287037475296763303738120063947710508065397284342914454082093489188333435337356055506801965232663559960802538728833796534291601599594460801094950652338245308336678262969650945954793076571188076285097774508994928135805851461589780682301845186135236651321513610921527111042159747801555758087206120961819012271336066498881331471146011538796171976969227414611180652471781807744608704658147356974307300714996994451224795449952999716213239830256631836859640201416928684063130279139058641, 41, 1723, 43, 3500201, 3835261, 585578449280908796570517800071, 47, 4939353696332137648660158610486273245800498531219046056285398249895046060595791007616253627660064463584012737427605759732894439061580553419678353685587762357233722998146101218334328347614340561470069315963989297, 1868467947605686541562499217713, (not exist), 2551, (51^4229-1)/50, 53, 178250690949465223, 2971, 7141212583461249612878870081, 31401724537, 3307, 59, 3541, 61, 52379047267, 3907, 16007041, (not exist)

* The smallest Williams prime with 1st kind base b:

3, 5, 11, 19, 29, 41, 3583, 71, 89, 109, 131, 2027, 181, 408700964355468749, 239, 271, 5507, 846825857, 379, 419, 461, 17276416353328819798072137388863592892072278184923153720493777138850572564953, 839967991029301247, 599, 3885038158778096269468893991882380063764065770433606110283149695964997245520484669311748838825973451239771955518933348332721403496018696846203290707966794803507099534240007184258836096614399, 701, 2368778164222232774191928573951, 811, 26099, 929, 991, 34847, 3095263992211830248865791, 1457749, 1259, 3417547576787, 37*38^136211-1, 1481, 1559, 7790170955239, 1721, 11416381666493, 13728945815551, 1979, 2069, 2161, 108287, 2351, 146031379699707031249999999999999999999999999, 2549, 19390405631, 7741603, 2861, 2969, 3079, 3191, 191747, 11911981, 3539, 3659, 139784395906071076766586020581268962303747288598567336951484722224451313085811771730116807299236427117842661797319704284843879372078242712851621827298082457986459462052386395974649371235894861683121487306574721459683501339777513560734278325650981380266285435618548139498448328096596807841457960474839935725016673894773768583677720662043161779832373490477494167310555190935956550302093326676711884265997512315330943608474964176395642249725224549579353670398605084716869153595460341758191671267601756450678548385413476307461538457595934906420684517898691543670687505315965265329598657370673413817965286377458043419147312784602056733277747759104526431673619974552441432434037533316091375742425601781283038065394099553927737205886353765152865548598839643177897844563113475601473328953408482456049673131973616976185783209288099190146109681267522543094039170871215260791829073435382418155171778782135316645578882955339664308529274906792023008178996964036098381727671689194723738996872705045605820037786049396276334730253078530300611653046136767706617293109455653251330444209017346414173013914938198059188297805588034443087345116883221415800773297093648337901984538392154514037514582882439555394954054641625018652439839301610996424664396983974323085517222193755969542276935638297070776680160676683227405039735827499267662993946306495247080085431407385375097236369554025762623869932975200275621419639360304816808572748496017393168318232665972570446440075892500649906727508939244057537554716592457169274187691031345168964785229426983746654648388804888079257248797899967499299858456238588374112649305901600140655206101680127, 15502913, 4648579506574807007231

* The smallest Williams prime with 2nd kind base b:

3, 7, 13, 101, 31, 43, 449, 73, 9001, 259374246011, 19009, 157, 2549, 211, 241, 1336337, 307, 218336795902605993201009018384568383223, 31129600000000000001, 421, 463, 255042399139852495799, 13249, 601, 16901, 13817467, 757, 23549, 23490001, 858874531, 35740566642812256257, 34849, 1123, 41651, 45361, 4678622632622773, 699421969744001971270254593, 1483, 62401, 42147180671470348388835886625344411346196083191529631288482561146240326026998221506440783978133517939838164995885825751477859968041, 1723, 77659, 161168129, 89101, 4380121, 26080959134473636132102571567, 108289, 115249, 122501, 2551, 2802982140528952023258759169, 10491513900891286499026738735135091160586124006333470053075798452149811519270024300012619626518018615344041193898353540073317686478669982334935722735157214044438750121387067129353403131395924739885547787541632580071542418404213751970278909499759877550283845617177464886504494817733888728186342721678314630157112704845506395528141971726016370931785914435731423398869999159630585365445775982492048522620099890853763237006462647136796940109416875810919060529600308292936053534656732307484233137785394600768454409163465028938105210676278897166335101081590402220699091389419760947664521051089812248945464579938920557862949540927479290799182068014020779544988135009962261241327200782535102674719135072434562508040789141676449576125079219727758870356884247118065440773617950056021530846873049589550019133078080663722176789313870897580396810177755781909618527239261721244480572786387976447602293449132613742946319671833328964972697119246892682336265152730921237713665354507537137443702829445952017487340491300683675985895629691084321187366733688850419017738601345840255501180273454585732065945743750216650542146084610529712530337630563500776116033357996283312548212598145790910607713043929753354827632869448608011951580713339509715548347910626001375466250058120039571083029723284705185200451797478498912933282140762819306704853286212160517919160926804950671170197329021477887747077647785029849474482618823322434015887000629289614915885122710872705478908601275767330249679458511998686296432297421162041793449010008226217042869255891247535123750707697346124793337408964749519851092431624559732210808836121020390168896446735325790252142542398429166658420843624167654453, 5130766694717659087768092673, 2971, 540897281, 10370809, 3307, 359216400347725176472840139, 3541, 3091222461661, 42969828958366879401068146141598580737, 3907, 16515073

sweety439 · 2020-12-30, 05:48

* The smallest Williams prime with 4th kind base b (for b != 1 mod 3): [not minimal prime (start with 2 digits) if either b is prime or base b has smaller generalized Fermat prime, but for the case that b is prime, it is still minimal prime (start with 2 digits) if we use LaurV's suggestion, i.e. start with b+1 instead of b]

7, 13, 31, 43, 73, 811, 1453, 157, 211, 241, 307, 3768826516993, 421, 463, 12697, 601, 18253, 757, 615334471, 27901, 1107296257, 1123, 44101, 1726273, 1483, 2372761, 1723, 75853, 87121, 93151, 106033, 599298932737, 2551, 158981126352779044590102826209115342318059775372698133871491241388097301966680877821738760704616125782843491355455960710073030287313404870590681666644752545879191893959727029866211537628677981607279205572507381073830401006677162824033234341436459420880686565908174585159142942438136179315586329074318947952541865853, 151687, 2971, 178753, 3307, 3541, 1338153989063049216000000000000000000001, 3907, 48326086052867645032352571108528903615254734667108057821332757600957454538355546211631290156513879123036351230974951391062798157776810891656336682957284917485088940693788242992185798654992956966627018064055387274320725152943868432582696386314597516885379356294528772183874293272350708412107233383892387582454781698467578958840732553153

* The smallest generalized Fermat prime base b (for even b):

3, 5, 7, (not exist), 11, 13, 197, 17, 19, 401, 23, 577, 677, 29, 31, (not exist), 1336337, 37, [unknown], 41, 43, 197352587024076973231046657, 47, 5308417, [unknown], 53, 2917, 3137, 59, 61, [unknown], (not exist)

* The smallest generalized half Fermat prime (> (b+1)/2) base b (for odd b):

5, 13, 1201, 41, 61, 14281, 113, 41761, 181, 97241, 139921, 313, (not exist), 421, [unknown], 703204309121, 613, [unknown], 761, 31879515457326527173216321, 5844100138801, 1013, 11905643330881, 1201, 1301, 31129845205681, [unknown], 5278001, 1741, 1861, [unknown]

* The smallest dual Williams prime with 1st kind base b:

3, 7, 13, 3121, 31, 43, 549755813881, 73, 991, 1321, 248821, 157, 2731, 211, 241, 34271896307617, 307, 6841, 13107199999999999999981, 421, 463, 141050039560662968926081, 331753, 601, 17551, 7625597484961, 757, 1816075630094014572464024421543167816955354437761, 21869999971, 29761, 34359738337, 1185889, 1123, 42841, 60466141, 1173587600912967505181585220815870451386152316472799938266409866089889961869797411886878993830039201370297, 79235131, 1483, 262143999999961, 68881, 1723, 3418759, 121987944123281928470243645070631579418581, 91081, 4477411, 229344961, 254803921, 36703368217294125441230211032033660188753, 124951, 2551, 140557, 1621038246414954860589967996431649201, 157411, 2971, 5416169448144841, 185137, 3307, 30155888444737842601, 3541, 844596241, 238267, 3907, 16777153

* The smallest dual Williams prime with 2nd kind base b: [not minimal prime (start with 2 digits) if b is prime, but still minimal prime (start with 2 digits) if we use LaurV's suggestion, i.e. start with b+1 instead of b]

3, 5, 7, 29, 11, 13, 71, 17, 19, 131, 23, 181, 2177953337809371149, 29, 31, 83537, 5849, 37, 419, 41, 43, 279863, 47, 15649, 701, 53, 811, 420707233300229, 59, 61, 3599131035634557106248430806148785487095757694641533306480604458089470064537190296255232548883112685719936728506816716098566612844395439751206812144692131084107807, 35969, 67, 1259, 71, 73, 1481, 1559, 79, 1721, 83, 79549, 1979, 89, 2161, 2766668711962335809450748011342447, 2351, 97, 2549, 101, 103, 2861, 107, 109, 3191, 113, 11316553, 3539, 3659, 3142742836081, 218340105584957, 250109, 127

* The smallest dual Williams prime with 4th kind base b (for b != 1 mod 3): [not minimal prime (start with 2 digits) if either b is prime or base b has smaller generalized Fermat prime, but for the case that b is prime, it is still minimal prime (start with 2 digits) if we use LaurV's suggestion, i.e. start with b+1 instead of b]

5, 7, 11, 13, 17, 19, 23, 157, 29, 31, 307, 37, 41, 43, 47, 601, 53, 757, 59, 61, 32801, 67, 71, 73, 1483, 79, 83, 74131, 89, 8303765671, 4879729, 97, 101, 103, 107, 109, 113, 3307, 3541, 216061, 3907, 127

sweety439 · 2020-12-30, 10:21

Quote:

Originally Posted by LaurV

I found an easy way to generate those sets, and to prove that they are complete.

For the "starting from two digits" version, neither one of the exposed sets for 7 and 8 are complete. Some larger primes are still lurking in the dark there. I have the complete sets for both 8, and 7 for the both cases when the base itself is included in the set or not*, but I don't want to spoil the puzzle, this is an interesting little problem... hehe...

Hint:

Code:

gp > a=(7^17-5)/2
%1 = 116315256993601
gp > isprime(a)
%2 = 1
gp > digits(a,7)
%3 = [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1]
gp >

---------
*when the base is prime, like for 5 and 7, the sets are different; including the base results in automatic elimination of all possible extension numbers with "0 after 1" from the set, which is quite restrictive, so I also calculated the lists for the "base is not included" version, i.e. base-5 starting from 6, and base-7 starting from 8; in this case, for example, base-5 will include numbers like 104 and 10103 which are prime, and base-7 list will include 1022, 1051, 1202, .... 1100021 ... etc, they are "enriched" compared with the case when the first "10" is included. So I have the complete list for 8, and the complete two lists for 7, the normal one, and the "enriched" one. Base-5 is easy, in any case.

Proof of base 5 in the case which the prime 10 (i.e. the prime = base) is also not counted just as the primes < base:

The possible (first digit,last digit) for an element with >=3 digits in the minimal set of the strings for primes with at least two digits are:

(1,1), (1,2), (1,3), (1,4), (2,1), (2,2), (2,3), (2,4), (3,1), (3,2), (3,3), (3,4), (4,1), (4,2), (4,3), (4,4)

* Case (1,1):

** Since 12, 21, 111, 131 are primes, we only need to consider the family 1{0,4}1 (since any digits 1, 2, 3 between them will produce smaller primes)

*** All numbers of the form 1{0,4}1 are divisible by 2, thus cannot be prime.

* Case (1,2):

** 12 is prime, and thus the only minimal prime in this family.

* Case (1,3):

** Since 12, 23, 43, 133 are primes, we only need to consider the family 1{0,1}3 (since any digits 2, 3, 4 between them will produce smaller primes)

*** Since 111 is prime, we only need to consider the families 1{0}3 and 1{0}1{0}3 (since any digit combo 11 between (1,3) will produce smaller primes)

**** All numbers of the form 1{0}3 are divisible by 2, thus cannot be prime.

**** For the 1{0}1{0}3 family, since 10103 is prime, we only need to consider the families 1{0}13 and 11{0}3 (since any digit combo 010 between (1,3) will produce smaller primes)

***** The smallest prime of the form 1{0}13 is 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000013, which can be written as 10₉₃13 and equal the prime 5^95+8

***** All numbers of the form 11{0}3 are divisible by 3, thus cannot be prime.

* Case (1,4):

** Since 12, 34, 104 are primes, we only need to consider the families 1{1,4}4 (since any digits 0, 2, 3 between them will produce smaller primes)

*** Since 111, 414 are primes, we only need to consider the family 1{4}4 and 11{4}4 (since any digit combo 11 or 41 between them will produce smaller primes)

**** The smallest prime of the form 1{4}4 is 14444.

**** All numbers of the form 11{4}4 are divisible by 2, thus cannot be prime.

sweety439 · 2020-12-30, 10:41

* Case (2,1):

** 21 is prime, and thus the only minimal prime in this family.

* Case (2,2):

** Since 21, 23, 12, 32 are primes, we only need to consider the family 2{0,2,4}2 (since any digits 1, 3 between them will produce smaller primes)

*** All numbers of the form 2{0,2,4}2 are divisible by 2, thus cannot be prime.

* Case (2,3):

** 23 is prime, and thus the only minimal prime in this family.

* Case (2,4):

** Since 21, 23, 34 are primes, we only need to consider the family 2{0,2,4}4 (since any digits 1, 3 between them will produce smaller primes)

*** All numbers of the form 2{0,2,4}4 are divisible by 2, thus cannot be prime.

* Case (3,1):

** Since 32, 34, 21 are primes, we only need to consider the family 3{0,1,3}1 (since any digits 2, 4 between them will produce smaller primes)

*** Since 313, 111, 131, 3101 are primes, we only need to consider the families 3{0,3}1 and 3{0,3}11 (since any digit combo 10, 11, 13 between (3,1) will produce smaller primes)

**** For the 3{0,3}1 family, we can separate this family to four families:

***** For the 30{0,3}01 family, we have the prime 30301, and the remain case is the family 30{0}01.

****** All numbers of the form 30{0}01 are divisible by 2, thus cannot be prime.

***** For the 30{0,3}31 family, note that there must be an even number of 3's between (30,31), or the result number will be divisible by 2 and cannot be prime.

****** Since 33331 is prime, any digit combo 33 between (30,31) will produce smaller primes.

******* Thus, the only possible prime is the smallest prime in the family 30{0}31, and this prime is 300031.

***** For the 33{0,3}01 family, note that there must be an even number of 3's between (33,01), or the result number will be divisible by 2 and cannot be prime.

****** Since 33331 is prime, any digit combo 33 between (33,01) will produce smaller primes.

******* Thus, the only possible prime is the smallest prime in the family 33{0}01, and this prime is 33001.

***** For the 33{0,3}31 family, we have the prime 33331, and the remain case is the family 33{0}31.

****** All numbers of the form 33{0}31 are divisible by 2, thus cannot be prime.

* Case (3,2):

** 32 is prime, and thus the only minimal prime in this family.

* Case (3,3):

** Since 32, 34, 23, 43, 313 are primes, we only need to consider the family 3{0,3}3 (since any digits 1, 2, 4 between them will produce smaller primes)

*** All numbers of the form 3{0,3}3 are divisible by 3, thus cannot be prime.

* Case (3,4):

** 34 is prime, and thus the only minimal prime in this family.

sweety439 · 2020-12-30, 10:48

* Case (4,1):

** Since 43, 21, 401 are primes, we only need to consider the family 4{1,4}1 (since any digits 0, 2, 3 between them will produce smaller primes)

*** Since 414, 111 are primes, we only need to consider the family 4{4}1 and 4{4}11 (since any digit combo 14 or 11 between them will produce smaller primes)

**** The smallest prime of the form 4{4}1 is 44441.

**** All numbers of the form 4{4}11 are divisible by 2, thus cannot be prime.

* Case (4,2):

** Since 43, 12, 32 are primes, we only need to consider the family 4{0,2,4}2 (since any digits 1, 3 between them will produce smaller primes)

*** All numbers of the form 4{0,2,4}2 are divisible by 2, thus cannot be prime.

* Case (4,3):

** 43 is prime, and thus the only minimal prime in this family.

* Case (4,4):

** Since 43, 34, 414 are primes, we only need to consider the family 4{0,2,4}4 (since any digits 1, 3 between them will produce smaller primes)

*** All numbers of the form 4{0,2,4}4 are divisible by 2, thus cannot be prime.

sweety439 · 2020-12-30, 10:51

Thus, we completed and proved the set of minimal primes (start with b+1, instead of b or 2) of base b=5:

Code:

12
21
23
32
34
43
104
111
131
133
313
401
414
3101
10103
14444
30301
33001
33331
44441
300031
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000013

sweety439 · 2020-12-30, 10:52

Proof of base 2 in the case which the prime 10 (i.e. the prime = base) is also not counted just as the primes < base:

The possible (first digit,last digit) for an element with >=3 digits in the minimal set of the strings for primes with at least two digits are:

(1,1)

* Case (1,1):

** 11 is prime, and thus the only minimal prime in this family.

sweety439 · 2020-12-30, 10:55

Proof of base 3 in the case which the prime 10 (i.e. the prime = base) is also not counted just as the primes < base:

The possible (first digit,last digit) for an element with >=3 digits in the minimal set of the strings for primes with at least two digits are:

(1,1), (1,2), (2,1), (2,2)

* Case (1,1):

** Since 12, 21, 111 are primes, we only need to consider the family 1{0}1 (since any digits 1, 2 between them will produce smaller primes)

*** All numbers of the form 1{0}1 are divisible by 2, thus cannot be prime.

* Case (1,2):

** 12 is prime, and thus the only minimal prime in this family.

* Case (2,1):

** 21 is prime, and thus the only minimal prime in this family.

* Case (2,2):

** Since 21, 12 are primes, we only need to consider the family 2{0,2}2 (since any digits 1 between them will produce smaller primes)

*** All numbers of the form 2{0,2}2 are divisible by 2, thus cannot be prime.

sweety439 · 2020-12-30, 10:59

Proof of base 4:

The possible (first digit,last digit) for an element with >=3 digits in the minimal set of the strings for primes with at least two digits are:

(1,1), (1,3), (2,1), (2,3), (3,1), (3,3)

* Case (1,1):

** 11 is prime, and thus the only minimal prime in this family.

* Case (1,3):

** 13 is prime, and thus the only minimal prime in this family.

* Case (2,1):

** Since 23, 11, 31, 221 are primes, we only need to consider the family 2{0}1 (since any digits 1, 2, 3 between them will produce smaller primes)

*** All numbers of the form 2{0}1 are divisible by 3, thus cannot be prime.

* Case (2,3):

** 23 is prime, and thus the only minimal prime in this family.

* Case (3,1):

** 31 is prime, and thus the only minimal prime in this family.

* Case (3,3):

** Since 31, 13, 23 are primes, we only need to consider the family 3{0,3}3 (since any digits 1, 2 between them will produce smaller primes)

*** All numbers of the form 3{0,3}3 are divisible by 3, thus cannot be prime.

2020-12-30, 05:04	#46
sweety439 "99(4^34019)99 palind" Nov 2016 (P^81993)SZ base 36 E62₁₆ Posts	Some simple families which are ruled out to only contain composites: (all substrings with length >=2 of all numbers in these families are not primes, except base 8 6{4}7 and 60{4}7 families, they are listed here because all substrings with length >=2 of all numbers with <220 4's in these two families are not primes) Base 5: 3{0}1 (divisible by 2) Base 6: 4{0}1 (divisible by 5) Base 8: 1{0}1 (sum of cubes) 2{0}5 (divisible by 7) 4{0}3 (divisible by 7) 44{0}3 (divisible by 3) 6{0}1 (divisible by 7) 6{4}7 (divisible by 3, 5, or 13) 60{4}7 (divisible by 17) Base 9: {1} (difference of squares) {1}5 (divisible by 2 or 5) 2{7} (divisible by 2 or 5) 3{1} (difference of squares) {3}5 (divisible by 2 or 5) {3}8 (divisible by 2 or 5) 3{8} (difference of squares) 5{1} (divisible by 2 or 5) 5{7} (divisible by 2 or 5) 6{1} (divisible by 2 or 5) {7}2 (divisible by 2 or 5) {7}5 (divisible by 2 or 5) {8}5 (difference of squares) Base 10: 4{6}9 (divisible by 7) Base 12: A{0}1 (divisible by 11) {B}9B (even number of B's is difference of squares, odd number of B's is divisible by 13) Base 14: 3{D} (divisible by 3 or 5) 4{0}1 (divisible by 3 or 5) 8{D} (even number of D's is difference of squares, odd number of D's is divisible by 5) A{D} (divisible by 3 or 5) B{0}1 (divisible by 3 or 5) {D}3 (divisible by 3 or 5) {D}5 (even number of D's is divisible by 5, odd number of D's is difference of squares) Base 16: 1{5} (difference of squares) 8{F} (difference of squares) {C}D (x^4+4y^4) {F}7 (difference of squares) Base 17: 1{9} (even number of 9's is difference of squares, odd number of 9's is divisible by 2) Base 20: 7{J} (divisible by 3 or 7) 8{0}1 (divisible by 3 or 7) C{J} (divisible by 3 or 7) D{0}1 (divisible by 3 or 7) Base 24: 3{N} (even number of N's is difference of squares, odd number of N's is divisible by 5) 5{N} (even number of N's is divisible by 5, odd number of N's is difference of squares) {6}1 (even number of 6's is difference of squares, odd number of 6's is divisible by 5) 8{N} (even number of N's is difference of squares, odd number of N's is divisible by 5) Base 25: {1} (difference of squares) 1{3} (difference of squares) 1{8} (difference of squares) D{1} (divisible by 2 or 13) Base 27: 8{0}1 (sum of cubes) 9{G} (difference of cubes) {D}E (sum of cubes) Base 32: 1{0}1 (sum of 5th powers) {1} (difference of 5th powers, the only trivial is 11111, but 11111 is not prime) Base 38: C{b} (divisible by 3, 5, or 17) G{0}1 (divisible by 3, 5, or 17) Base 47: 8{0}1 (divisible by 3, 5, or 13) D{k} (divisible by 3, 5, or 13) G{0}1 (divisible by 3, 5, or 17) Last fiddled with by sweety439 on 2020-12-30 at 05:20*

2020-12-30, 10:41	#50
sweety439 "99(4^34019)99 palind" Nov 2016 (P^81993)SZ base 36 2×7×263 Posts	* Case (2,1): ** 21 is prime, and thus the only minimal prime in this family. * Case (2,2): Since 21, 23, 12, 32 are primes, we only need to consider the family 2{0,2,4}2 (since any digits 1, 3 between them will produce smaller primes) * All numbers of the form 2{0,2,4}2 are divisible by 2, thus cannot be prime. * Case (2,3): ** 23 is prime, and thus the only minimal prime in this family. * Case (2,4): Since 21, 23, 34 are primes, we only need to consider the family 2{0,2,4}4 (since any digits 1, 3 between them will produce smaller primes) * All numbers of the form 2{0,2,4}4 are divisible by 2, thus cannot be prime. * Case (3,1): Since 32, 34, 21 are primes, we only need to consider the family 3{0,1,3}1 (since any digits 2, 4 between them will produce smaller primes) * Since 313, 111, 131, 3101 are primes, we only need to consider the families 3{0,3}1 and 3{0,3}11 (since any digit combo 10, 11, 13 between (3,1) will produce smaller primes) ** For the 3{0,3}1 family, we can separate this family to four families: * For the 30{0,3}01 family, we have the prime 30301, and the remain case is the family 30{0}01. ** All numbers of the form 30{0}01 are divisible by 2, thus cannot be prime. * For the 30{0,3}31 family, note that there must be an even number of 3's between (30,31), or the result number will be divisible by 2 and cannot be prime. ** Since 33331 is prime, any digit combo 33 between (30,31) will produce smaller primes. *** Thus, the only possible prime is the smallest prime in the family 30{0}31, and this prime is 300031. * For the 33{0,3}01 family, note that there must be an even number of 3's between (33,01), or the result number will be divisible by 2 and cannot be prime. ** Since 33331 is prime, any digit combo 33 between (33,01) will produce smaller primes. *** Thus, the only possible prime is the smallest prime in the family 33{0}01, and this prime is 33001. * For the 33{0,3}31 family, we have the prime 33331, and the remain case is the family 33{0}31. **** All numbers of the form 33{0}31 are divisible by 2, thus cannot be prime. * Case (3,2): ** 32 is prime, and thus the only minimal prime in this family. * Case (3,3): Since 32, 34, 23, 43, 313 are primes, we only need to consider the family 3{0,3}3 (since any digits 1, 2, 4 between them will produce smaller primes) * All numbers of the form 3{0,3}3 are divisible by 3, thus cannot be prime. * Case (3,4): ** 34 is prime, and thus the only minimal prime in this family. Last fiddled with by sweety439 on 2020-12-30 at 10:53

2020-12-30, 10:51	#52
sweety439 "99(4^34019)99 palind" Nov 2016 (P^81993)SZ base 36 2·7·263 Posts	Thus, we completed and proved the set of minimal primes (start with b+1, instead of b or 2) of base b=5: Code: 12 21 23 32 34 43 104 111 131 133 313 401 414 3101 10103 14444 30301 33001 33331 44441 300031 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000013

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
generalized minimal (probable) primes	sweety439	sweety439	140	2022-12-20 07:08
Minimal set of the strings for primes with at least two digits	sweety439	sweety439	6	2019-11-25 07:37
Digit strings containing primes	davar55	Puzzles	13	2018-03-15 14:46
Primes from powers of 2 strings.	Flatlander	Puzzles	40	2011-02-10 09:42
Strings of Digits	davar55	Puzzles	5	2008-11-02 00:08

2020-12-30, 04:52	#45
sweety439 "99(4^34019)99 palind" Nov 2016 (P^81993)SZ base 36 3682₁₀ Posts	In base 9, family {3}{0}5 does not need to be tested because.... * If the number of digits 3 is even, then the number is divisible by 5. * If the number of digits 3 is odd, then the number is divisible by 2. Thus, this family has a numerical covering set {2,5} and is ruled out to only contain composites. Note that {3}{0}5 is not simple family (simple families are x{d}y with d digit, x,y strings of digits (can be empty string)) In base 9, many such non-simple families exist, e.g. {1}6{1}, see page 13 of https://cs.uwaterloo.ca/~cbright/reports/mepn.pdf

2020-12-30, 05:48	#48
sweety439 "99(4^34019)99 palind" Nov 2016 (P^81993)SZ base 36 2×7×263 Posts	* The smallest Williams prime with 4th kind base b (for b != 1 mod 3): [not minimal prime (start with 2 digits) if either b is prime or base b has smaller generalized Fermat prime, but for the case that b is prime, it is still minimal prime (start with 2 digits) if we use LaurV's suggestion, i.e. start with b+1 instead of b] 7, 13, 31, 43, 73, 811, 1453, 157, 211, 241, 307, 3768826516993, 421, 463, 12697, 601, 18253, 757, 615334471, 27901, 1107296257, 1123, 44101, 1726273, 1483, 2372761, 1723, 75853, 87121, 93151, 106033, 599298932737, 2551, 158981126352779044590102826209115342318059775372698133871491241388097301966680877821738760704616125782843491355455960710073030287313404870590681666644752545879191893959727029866211537628677981607279205572507381073830401006677162824033234341436459420880686565908174585159142942438136179315586329074318947952541865853, 151687, 2971, 178753, 3307, 3541, 1338153989063049216000000000000000000001, 3907, 48326086052867645032352571108528903615254734667108057821332757600957454538355546211631290156513879123036351230974951391062798157776810891656336682957284917485088940693788242992185798654992956966627018064055387274320725152943868432582696386314597516885379356294528772183874293272350708412107233383892387582454781698467578958840732553153 * The smallest generalized Fermat prime base b (for even b): 3, 5, 7, (not exist), 11, 13, 197, 17, 19, 401, 23, 577, 677, 29, 31, (not exist), 1336337, 37, [unknown], 41, 43, 197352587024076973231046657, 47, 5308417, [unknown], 53, 2917, 3137, 59, 61, [unknown], (not exist) * The smallest generalized half Fermat prime (> (b+1)/2) base b (for odd b): 5, 13, 1201, 41, 61, 14281, 113, 41761, 181, 97241, 139921, 313, (not exist), 421, [unknown], 703204309121, 613, [unknown], 761, 31879515457326527173216321, 5844100138801, 1013, 11905643330881, 1201, 1301, 31129845205681, [unknown], 5278001, 1741, 1861, [unknown] * The smallest dual Williams prime with 1st kind base b: 3, 7, 13, 3121, 31, 43, 549755813881, 73, 991, 1321, 248821, 157, 2731, 211, 241, 34271896307617, 307, 6841, 13107199999999999999981, 421, 463, 141050039560662968926081, 331753, 601, 17551, 7625597484961, 757, 1816075630094014572464024421543167816955354437761, 21869999971, 29761, 34359738337, 1185889, 1123, 42841, 60466141, 1173587600912967505181585220815870451386152316472799938266409866089889961869797411886878993830039201370297, 79235131, 1483, 262143999999961, 68881, 1723, 3418759, 121987944123281928470243645070631579418581, 91081, 4477411, 229344961, 254803921, 36703368217294125441230211032033660188753, 124951, 2551, 140557, 1621038246414954860589967996431649201, 157411, 2971, 5416169448144841, 185137, 3307, 30155888444737842601, 3541, 844596241, 238267, 3907, 16777153 * The smallest dual Williams prime with 2nd kind base b: [not minimal prime (start with 2 digits) if b is prime, but still minimal prime (start with 2 digits) if we use LaurV's suggestion, i.e. start with b+1 instead of b] 3, 5, 7, 29, 11, 13, 71, 17, 19, 131, 23, 181, 2177953337809371149, 29, 31, 83537, 5849, 37, 419, 41, 43, 279863, 47, 15649, 701, 53, 811, 420707233300229, 59, 61, 3599131035634557106248430806148785487095757694641533306480604458089470064537190296255232548883112685719936728506816716098566612844395439751206812144692131084107807, 35969, 67, 1259, 71, 73, 1481, 1559, 79, 1721, 83, 79549, 1979, 89, 2161, 2766668711962335809450748011342447, 2351, 97, 2549, 101, 103, 2861, 107, 109, 3191, 113, 11316553, 3539, 3659, 3142742836081, 218340105584957, 250109, 127 * The smallest dual Williams prime with 4th kind base b (for b != 1 mod 3): [not minimal prime (start with 2 digits) if either b is prime or base b has smaller generalized Fermat prime, but for the case that b is prime, it is still minimal prime (start with 2 digits) if we use LaurV's suggestion, i.e. start with b+1 instead of b] 5, 7, 11, 13, 17, 19, 23, 157, 29, 31, 307, 37, 41, 43, 47, 601, 53, 757, 59, 61, 32801, 67, 71, 73, 1483, 79, 83, 74131, 89, 8303765671, 4879729, 97, 101, 103, 107, 109, 113, 3307, 3541, 216061, 3907, 127

2020-12-30, 10:48	#51
sweety439 "99(4^34019)99 palind" Nov 2016 (P^81993)SZ base 36 111001100010₂ Posts	* Case (4,1): Since 43, 21, 401 are primes, we only need to consider the family 4{1,4}1 (since any digits 0, 2, 3 between them will produce smaller primes) * Since 414, 111 are primes, we only need to consider the family 4{4}1 and 4{4}11 (since any digit combo 14 or 11 between them will produce smaller primes) ** The smallest prime of the form 4{4}1 is 44441. ** All numbers of the form 4{4}11 are divisible by 2, thus cannot be prime. * Case (4,2): Since 43, 12, 32 are primes, we only need to consider the family 4{0,2,4}2 (since any digits 1, 3 between them will produce smaller primes) * All numbers of the form 4{0,2,4}2 are divisible by 2, thus cannot be prime. * Case (4,3): ** 43 is prime, and thus the only minimal prime in this family. * Case (4,4): Since 43, 34, 414 are primes, we only need to consider the family 4{0,2,4}4 (since any digits 1, 3 between them will produce smaller primes) * All numbers of the form 4{0,2,4}4 are divisible by 2, thus cannot be prime.

2020-12-30, 10:52	#53
sweety439 "99(4^34019)99 palind" Nov 2016 (P^81993)SZ base 36 7142₈ Posts	Proof of base 2 in the case which the prime 10 (i.e. the prime = base) is also not counted just as the primes < base: The possible (first digit,last digit) for an element with >=3 digits in the minimal set of the strings for primes with at least two digits are: (1,1) * Case (1,1): ** 11 is prime, and thus the only minimal prime in this family.

2020-12-30, 10:55	#54
sweety439 "99(4^34019)99 palind" Nov 2016 (P^81993)SZ base 36 2×7×263 Posts	Proof of base 3 in the case which the prime 10 (i.e. the prime = base) is also not counted just as the primes < base: The possible (first digit,last digit) for an element with >=3 digits in the minimal set of the strings for primes with at least two digits are: (1,1), (1,2), (2,1), (2,2) * Case (1,1): Since 12, 21, 111 are primes, we only need to consider the family 1{0}1 (since any digits 1, 2 between them will produce smaller primes) * All numbers of the form 1{0}1 are divisible by 2, thus cannot be prime. * Case (1,2): ** 12 is prime, and thus the only minimal prime in this family. * Case (2,1): ** 21 is prime, and thus the only minimal prime in this family. * Case (2,2): Since 21, 12 are primes, we only need to consider the family 2{0,2}2 (since any digits 1 between them will produce smaller primes) * All numbers of the form 2{0,2}2 are divisible by 2, thus cannot be prime.

2020-12-30, 10:59	#55
sweety439 "99(4^34019)99 palind" Nov 2016 (P^81993)SZ base 36 2×7×263 Posts	Proof of base 4: The possible (first digit,last digit) for an element with >=3 digits in the minimal set of the strings for primes with at least two digits are: (1,1), (1,3), (2,1), (2,3), (3,1), (3,3) * Case (1,1): ** 11 is prime, and thus the only minimal prime in this family. * Case (1,3): ** 13 is prime, and thus the only minimal prime in this family. * Case (2,1): Since 23, 11, 31, 221 are primes, we only need to consider the family 2{0}1 (since any digits 1, 2, 3 between them will produce smaller primes) * All numbers of the form 2{0}1 are divisible by 3, thus cannot be prime. * Case (2,3): ** 23 is prime, and thus the only minimal prime in this family. * Case (3,1): ** 31 is prime, and thus the only minimal prime in this family. * Case (3,3): Since 31, 13, 23 are primes, we only need to consider the family 3{0,3}3 (since any digits 1, 2 between them will produce smaller primes) * All numbers of the form 3{0,3}3 are divisible by 3, thus cannot be prime.