mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2019-11-21, 18:29   #1
sweety439
 
Nov 2016

54048 Posts
Default 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
sweety439 is offline   Reply With Quote
Old 2019-11-21, 19:34   #2
sweety439
 
Nov 2016

22×3×5×47 Posts
Default

Quote:
Originally Posted by sweety439 View Post
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
File Type: txt minimal set of primes.txt (659.3 KB, 245 views)

Last fiddled with by sweety439 on 2019-11-21 at 19:35
sweety439 is offline   Reply With Quote
Old 2019-11-23, 20:55   #3
sweety439
 
Nov 2016

282010 Posts
Default

I made proof for bases 2 to 6:

b=2: we obtain the 2-digit 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 2-kernel {10, 11} is complete.

b=3: we obtain the 2-digit 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 3-kernel {10, 12, 21, 111}.

b=4: we obtain the 2-digit 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 4-kernel {11, 13, 23, 31, 221}.

b=5: we obtain the 2-digit 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 5-kernel is complete!!!

b=6: we obtain the 2-digit 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 6-kernel is complete!!!
sweety439 is offline   Reply With Quote
Old 2019-11-23, 20:57   #4
sweety439
 
Nov 2016

22·3·5·47 Posts
Default

Quote:
Originally Posted by sweety439 View Post
I made proof for bases 2 to 6:

b=2: we obtain the 2-digit 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 2-kernel {10, 11} is complete.

b=3: we obtain the 2-digit 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 3-kernel {10, 12, 21, 111}.

b=4: we obtain the 2-digit 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 4-kernel {11, 13, 23, 31, 221}.

b=5: we obtain the 2-digit 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 5-kernel is complete!!!

b=6: we obtain the 2-digit 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 6-kernel is complete!!!
Thus, my base 5 (and base 2, 3, 4, 6) sets are all complete!!!
sweety439 is offline   Reply With Quote
Old 2019-11-24, 15:26   #5
sweety439
 
Nov 2016

22×3×5×47 Posts
Default

Quote:
Originally Posted by sweety439 View Post
I made proof for bases 2 to 6:

b=2: we obtain the 2-digit 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 2-kernel {10, 11} is complete.

b=3: we obtain the 2-digit 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 3-kernel {10, 12, 21, 111}.

b=4: we obtain the 2-digit 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 4-kernel {11, 13, 23, 31, 221}.

b=5: we obtain the 2-digit 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 5-kernel is complete!!!

b=6: we obtain the 2-digit 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 6-kernel is complete!!!
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
sweety439 is offline   Reply With Quote
Old 2019-11-25, 05:05   #6
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

83×113 Posts
Default

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
LaurV is offline   Reply With Quote
Old 2019-11-25, 07:37   #7
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

222578 Posts
Default

Quote:
Originally Posted by LaurV View Post
...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.
Batalov is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
generalized minimal (probable) primes sweety439 sweety439 127 2021-02-24 02:35
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
Sum of all integer digits of all primes between 1 an n AntonVrba Math 2 2006-09-20 17:20

All times are UTC. The time now is 20:50.

Sun Apr 18 20:50:10 UTC 2021 up 10 days, 15:31, 1 user, load averages: 1.89, 1.76, 1.91

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

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.