20191121, 18:29  #1 
Nov 2016
5404_{8} Posts 
Minimal set of the strings for primes with at least two digits
https://primes.utm.edu/glossary/page...t=MinimalPrime
In 1996, Jeffrey Shallit [Shallit96] suggested that we view prime numbers as strings of digits. He then used concepts from formal language theory to define an interesting set of primes called the minimal primes: A string a is a subsequence of another string b, if a can be obtained from b by deleting zero or more of the characters in b. For example, 514 is a substring of 251664. The empty string is a subsequence of every string. Two strings a and b are comparable if either a is a substring of b, or b is a substring of a. A surprising result from formal language theory is that every set of pairwise incomparable strings is finite [Lothaire83]. This means that from any set of strings we can find its minimal elements. A string a in a set of strings S is minimal if whenever b (an element of S) is a substring of a, we have b = a. This set must be finite! For example, if our set is the set of prime numbers (written in radix 10), then we get the set {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}, and if our set is the set of composite numbers (written in radix 10), then we get the set {4, 6, 8, 9, 10, 12, 15, 20, 21, 22, 25, 27, 30, 32, 33, 35, 50, 51, 52, 55, 57, 70, 72, 75, 77, 111, 117, 171, 371, 711, 713, 731} Besides, if our set is the set of prime numbers written in radix b, then we get these sets: Code:
b, we get the set 2: {10, 11} 3: {2, 10, 111} 4: {2, 3, 11} 5: {2, 3, 10, 111, 401, 414, 14444, 44441} 6: {2, 3, 5, 11, 4401, 4441, 40041} Now, let's consider: if our set is the set of prime numbers >= b written in radix b (i.e. the prime numbers with at least two digits in radix b), then we get the sets: Code:
b, we get the set 2: {10, 11} 3: {10, 12, 21, 111} 4: {11, 13, 23, 31, 221} 5: {10, 12, 21, 23, 32, 34, 43, 111, 131, 133, 313, 401, 414, 14444, 30301, 33001, 33331, 44441, 300031} 6: {11, 15, 21, 25, 31, 35, 45, 51, 4401, 4441, 40041} 7: {10, 14, 16, 23, 25, 32, 41, 43, 52, 56, 61, 65, 113, 115, 131, 133, 155, 212, 221, 304, 313, 335, 344, 346, 364, 445, 515, 533, 535, 544, 551, 553, 1112, 1211, 1222, 2111, 3031, 3055, 3334, 3503, 3505, 3545, 4504, 4555, 5011, 5455, 5545, 5554, 6034, 6634, 11111, 30011, 31111, 33001, 33311, 35555, 40054, 300053, 33333301} 8: {13, 15, 21, 23, 27, 35, 37, 45, 51, 53, 57, 65, 73, 75, 107, 111, 117, 141, 147, 161, 177, 225, 255, 301, 343, 361, 401, 407, 417, 431, 433, 463, 467, 471, 631, 643, 661, 667, 701, 711, 717, 747, 767, 3331, 3411, 4043, 4443, 4611, 5205, 6007, 6101, 6441, 6477, 6707, 6777, 7461, 7641, 47777, 60171, 60411, 60741, 444641, 500025, 505525, 3344441, 4444477, 5500525, 5550525, 55555025, 444444441, 744444441} Can someone complete my base 5, 7 and 8 set? Also find the sets of bases 9 to 36. Last fiddled with by sweety439 on 20191121 at 18:32 
20191121, 19:34  #2  
Nov 2016
2^{2}×3×5×47 Posts 
Quote:
Last fiddled with by sweety439 on 20191121 at 19:35 

20191123, 20:55  #3 
Nov 2016
2820_{10} Posts 
I made proof for bases 2 to 6:
b=2: we obtain the 2digit primes 10 and 11, since for any prime p > 11, p must start and end with digit 1, and we have 11 <<< p, thus the 2kernel {10, 11} is complete. b=3: we obtain the 2digit primes 10, 12 and 21, for any prime p > 21, if p end with 2 and 12 !<<< p, then p must contain only 0 and 2, thus p is divisible by 2 and > 2, thus not prime, therefore, p must end with 1 (p cannot end with 0, or p is divisible by 10 and not prime), since 21 !<<< p, p must contain only 0 and 1, but since 10 !<<< p and p cannot have leading zeros, thus p can only have the digit 1, i.e. p is a repunit, and the smallest repunit prime is 111, thus completed the 3kernel {10, 12, 21, 111}. b=4: we obtain the 2digit primes 11, 13, 23 and 31, for any prime p > 31, if p end with 3 and 13 !<<< p and 23 !<<< p, then p must contain only 0 and 3, thus p is divisible by 3 and > 3, thus not prime, therefore, p must end with 1 (p cannot end with 0 or 2, or p is divisible by 2 and not prime), since 11 !<<< p and 31 !<<< p, thus p (before the final digit 1) must contain only 0 and 2, and we obtain the prime 221, since p cannot have leading zeros, the remain case is only 2{0}1, but all numbers of the form 2{0}1 are divisible by 3 and > 3, thus not prime, thus we completed the 4kernel {11, 13, 23, 31, 221}. b=5: we obtain the 2digit primes 10, 12, 21, 23, 32, 34 and 43, for any prime p>43: p end with 2 > before this 2, p cannot contain 1 or 3 > p only contain 0, 2 and 4 > p is divisible by 2 and > 2 > p is not prime (thus, 12 and 32 are the only such primes end with 2) p end with 3 > before this 3, p cannot contain 2 or 4 > p only contain 0, 1 and 3 > we obtain the primes 133 and 313, thus other primes p cannot contain both 1 and 3 (before the final digit 3), and since p cannot have leading zeros, if p begin with 1, then p is of the form 1{0,1}3 > it must be of the form {1}3 (to avoid the prime 10) > but 113 is not prime and all primes except 111 contain at most two 1 > this way cannot find any primes, if p begin with 3, then p is of the form 3{0,3}3 > p is divisible by 3 and > 3 > p is not prime (thus, all such primes end with 3 are 23, 43, 133 and 313) p end with 4 > before this 4, p cannot contain 3 > since all primes > 2 are odd, p must contain at least one 1 > we obtain the prime 414 and we know that no 2 can before this 1 (to avoid the prime 21) and no 0 or 2 can after this 1 (to avoid the primes 10 and 12) > 1 must be the leading digit (since p cannot have leading zeros, and no 2, 3, 4 can before this 1 (to avoid the primes 21, 34 and 414, respectively) > p must be of the form 1{4} or 11{4} (since all primes except 111 contain at most two 1) > and we obtain the prime 14444 (thus, all such primes end with 4 are 34, 414 and 14444) p end with 1: (assume p is a prime in the minimal set of the strings for primes with at least two digits in base 5 other than 10, 12, 21, 23, 32, 34, 43, 111, 131, 133, 313, 401, 414, 14444, 30301, 33001, 33331, 44441, 300031) * before this 1, p cannot contain 2 (because of 21) * if before this 1, p contain 1 > assume p is {xxx}1{yyy}1 > y cannot contain 0, 1, 2, or 3 (because of 10, 111, 12, and 131) ** if y is not empty > y contain only the digits 4 > x cannot contain 1, 2, 3, or 4 (because of 111, 21, 34, and 414) > x contain only the digits 0 (a contradiction, since a number cannot have leading zeros) ** thus y is empty > p is {xxx}11 > x cannot contain 1 or 2 (because of 111 and 21), but x cannot contain both 3 and 4 (because of 34 and 43) > x contain either only 0 and 3, or only 0 and 4, however, {0,3}11 is divisible by 3, and {0,4}11 is divisible by 2, and neither can be primes, a contradiction!!! > thus, before this 1, p cannot contain 1 Therefore, before this 1, p can only contain the digits 0, 3, and 4. However, p cannot contain both 3 and 4 (because of 34 and 43) thus, before this 1, p contain either only 0 and 3, or only 0 and 4 For the primes contain only 0 and 3: Since the first digit cannot be 0, it can only be 3 thus p is 3{xxx}1 x should contain at least one 3 (or p is of the form 3{0}1, and 3{0}1 is divisible by 2) thus we can assume p is 3{xxx}3{yyy}1 * if both x and y contain 0, then we have the prime 30301 * if x does not contain 0, then x contain only 3 ** if x contain at least two 3, then we have the prime 33331 ** if x contain exactly one 3, then p is 3{0}3{0}3{yyy}1, and y can contain only the digits 0 (y cannot contain 3, because of 33331) > p is of the form 3{0}3{0}3{0}1 and divisible by 2, a contradiction ** if x is empty, then p is 33{yyy}1, and y can contain only the digits 0 (y cannot contain at least two 3 because of 33331, and if y contain exactly one 3, then p is divisible by 2 and cannot be prime), then we have the prime 33001 * if y does not contain 0, then y contain only 3 ** if y contain at least two 3, then we have the prime 33331 ** if y contain exactly one 3, then p is 3{xxx}3{0}3{0}1, and x can contain only the digits 0 (x cannot contain 3, because of 33331) > p is of the form 3{0}3{0}3{0}1 and divisible by 2, a contradiction ** if y is empty, then p is 3{xxx}31, and x can contain only the digits 0 (x cannot contain at least two 3 because of 33331, and if x contain exactly one 3, then p is divisible by 2 and cannot be prime), then we have the prime 300031 For the primes contain only 0 and 4: Since the first digit cannot be 0, it can only be 4 thus p is 4{xxx}1 if x contain 0, then we have the prime 401 if x does not contain 0 (thus contain only the digit 4), then we have the prime 44441 Therefore, no such prime p can exist!!! The 5kernel is complete!!! b=6: we obtain the 2digit primes 11, 15, 21, 25, 31, 35, 45 and 51, for any prime p > 51: * if p end with 5 > before this 5, p cannot contain 1, 2, 3, or 4, however, all numbers of the form {0, 5}5 is divisible by 5 and cannot be prime * thus, p can only end with 1 > before this 1, p cannot contain 1, 2, 3, or 5 > before this 1, p can only contain the digits 0 and 4 > since the first digit cannot be 0, it can only be 4 > p is of the form 4{xxx}1 > x should contain at least one 4 (or p is of the form 4{0}1, and 4{0}1 is divisible by 5) > thus we can assume p is 4{xxx}4{yyy}1 * if y contain at least one 0, then we have the prime 4401 * if y contain at least one 4, then we have the prime 4441 * if y is empty: ** if x contain at least one 4, then we have the prime 4441 ** if x does not contain 4 (thus contain only the digit 0), then we have the prime 40041 The 6kernel is complete!!! 
20191123, 20:57  #4  
Nov 2016
2^{2}·3·5·47 Posts 
Quote:


20191124, 15:26  #5  
Nov 2016
2^{2}×3×5×47 Posts 
Quote:
* if before this 1, p contain 1 > assume p is {xxx}1{yyy}1 > y cannot contain 0, 1, 2, or 3 (because of 10, 111, 12, and 131) ** if y is not empty > y contain only the digits 4 > x cannot contain 1, 2, 3, or 4 (because of 111, 21, 34, and 414) > x contain only the digits 0 (a contradiction, since a number cannot have leading zeros, and all numbers of the form 1{4}1 is divisible by 2 and cannot be primes) Last fiddled with by sweety439 on 20191124 at 15:27 

20191125, 05:05  #6 
Romulan Interpreter
Jun 2011
Thailand
83×113 Posts 
You really like quoting yourself, especially when posting long piles of rubbish, don't you?
Those selfquotes, and generally, quotes of the full text of the immediately preceding post (regardless of the fact that is yours or someone's else) are totally futile. They result in people not reading the text because they see it as endless and the same, again and again, and they will skip it completely. Moreover, it eats the space on the server, and it clutters the forum, so we see this habit as detrimental. And because we believe that the people are clever and educated, we can't imagine they do this by mistake, like stupid people would do. So the only left possibility is that they do it on purpose to clutter the forum and piss us off... We are very tempted to edit the posts and delete the long selfquotes, but we are a bit afraid that our name will appear at the end of those posts ("edited by") and then you will claim we changed the meaning of your words... In which case, there is still the possibility of total annihilation of those posts, so nobody ever see them... Last fiddled with by LaurV on 20191125 at 05:09 
20191125, 07:37  #7 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
22257_{8} Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
generalized minimal (probable) primes  sweety439  sweety439  127  20210224 02:35 
Digit strings containing primes  davar55  Puzzles  13  20180315 14:46 
Primes from powers of 2 strings.  Flatlander  Puzzles  40  20110210 09:42 
Strings of Digits  davar55  Puzzles  5  20081102 00:08 
Sum of all integer digits of all primes between 1 an n  AntonVrba  Math  2  20060920 17:20 