mersenneforum.org Minimal set of the strings for primes with at least two digits
 Register FAQ Search Today's Posts Mark Forums Read

 2019-11-21, 18:29 #1 sweety439   Nov 2016 22·3·5·47 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} these are already researched in https://cs.uwaterloo.ca/~cbright/reports/mepn.pdf. 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} However, I do not think that my base 5, 7 and 8 sets are complete (I use PARI program to find these primes (all written in base b), but I only searched the primes with <= 8 digits, so there may be missing primes), I proved that my base 2, 3, 4 and 6 sets are complete. (I proved that my base 5 set is complete for primes end with 0, 2, 3 or 4 in base 5, but I cannot prove that my base 5 set is complete for primes end with 1 in base 5, so there may be missing primes end with 1 in base 5) 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 2019-11-21 at 18:32
2019-11-21, 19:34   #2
sweety439

Nov 2016

22·3·5·47 Posts

Quote:
 Originally Posted by sweety439 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} these are already researched in https://cs.uwaterloo.ca/~cbright/reports/mepn.pdf. 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} However, I do not think that my base 5, 7 and 8 sets are complete (I use PARI program to find these primes (all written in base b), but I only searched the primes with <= 8 digits, so there may be missing primes), I proved that my base 2, 3, 4 and 6 sets are complete. (I proved that my base 5 set is complete for primes end with 0, 2, 3 or 4 in base 5, but I cannot prove that my base 5 set is complete for primes end with 1 in base 5, so there may be missing primes end with 1 in base 5) Can someone complete my base 5, 7 and 8 set? Also find the sets of bases 9 to 36.
These are the first few primes in the minimal set strings of primes with at least two digits in bases 2 through 24, can someone complete these sets?
Attached Files
 minimal set of primes.txt (659.3 KB, 235 views)

Last fiddled with by sweety439 on 2019-11-21 at 19:35

2019-11-23, 20:57   #4
sweety439

Nov 2016

22×3×5×47 Posts

Quote:
Thus, my base 5 (and base 2, 3, 4, 6) sets are all complete!!!

2019-11-24, 15:26   #5
sweety439

Nov 2016

22×3×5×47 Posts

Quote:
I missed one step: b=5, p end with 1:

* 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 2019-11-24 at 15:27

 2019-11-25, 05:05 #6 LaurV Romulan Interpreter     Jun 2011 Thailand 33·347 Posts You really like quoting yourself, especially when posting long piles of rubbish, don't you? Those self-quotes, 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 self-quotes, 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 2019-11-25 at 05:09
2019-11-25, 07:37   #7
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

41·229 Posts

Quote:
 Originally Posted by LaurV ...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...
No, no, just use Hanlon's razor.

 Similar Threads Thread Thread Starter Forum Replies Last Post sweety439 sweety439 127 2021-02-24 02:35 davar55 Puzzles 13 2018-03-15 14:46 Flatlander Puzzles 40 2011-02-10 09:42 davar55 Puzzles 5 2008-11-02 00:08 AntonVrba Math 2 2006-09-20 17:20

All times are UTC. The time now is 10:37.

Tue Apr 13 10:37:37 UTC 2021 up 5 days, 5:18, 1 user, load averages: 1.42, 1.48, 1.47

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.