This post is about an open problems column by Gasarch-Gezalyn-Patrick so they can be considered co-authors on this post. The column is here.
Known: A permutable prime is a prime so that, no matter how you permute the digits, you get a prime.
The first 22 of them are:
2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97, 113, 131, 199, 311, 337, 373, 733, 919, 991.
11 might seem like a silly example. However, all of the known ones past 991 are just all 1's. Let \(R_n\) be the base 10 number which is represented by n 1's.
The next three permutable primes are \(R_{23}\), \(R_{317}\), \(R_{1031}\).
Those are all of the permutable primes that are known. The 2 conjecture is that there are
(1) there are an infinite number of them
(2) all those past 991 are of the form \(R_n\).
There is more information and more conjectures about them in the open problems col pointed to above.
I know of three online papers on permutable primes, see my website of them here.
New: A number n is a k-compatible (henceforth k-comp) prime if there are k permutations of n that are prime but not k+1 such permutations.
Examples:
a) 103 is 3-comp: 013, 031, 103 are prime BUT 130, 310,301 are NOT prime.
b) 97 is 2-comp: 79 and 97 are prime and there are no other perms of 97.
c) 41 is 1-comp: 41 is prime BUT 14 is NOT prime.
We have some (though not much) empirical data that suggests the following. Fix L, the length of numbers being considered. If you look at L-length primes that are 1-comp, 2-comp, etc the number of them will (with some exceptions) first increase then (with some exceptions) decrease, though past k=L/2 (actually smaller) the are no L-length, k-comp primes.
For rigorous conjectures and more information see the paper pointed to above.
Fun fact. 73 is the 21st prime number and its mirror, 37, is the 12th.
ReplyDeleteAnd 7*3=21 ;)
DeleteIf we search for permutable primes in binary we immediately see that all must consist of a string of 1's, if it contains a 0 it can be permuted to a number ending in 0 which is even and so not prime (except for 10, but 01 is not a prime).
ReplyDeleteSo you see that all binary permutable primes are of the from R_n. But here R_n = 2^n - 1 so these are the Mersenne primes. It is still unknown whether there is an infinite amount of Mersenne primes.
Wikipedia says that the problem: 'Are there an infinite number of Mersenne primes?' is still open. Also, if this was known then either Lance or I or my local number theorist Larry Washington would have heard about it. Hence i am skeptical that the proof is correct.
ReplyDeleteYes, the paper IF IT IS A GEM should have been uploaded to ArXiv to begin with. This might be sign that it's on of those papers where P=NP, or a reason IF CORRECT it's not well-known. In either case, reaching out to Fensui Liu is challenging but why not try a certain Kai Thompson who helped revise Liu's English for this text.
ReplyDeleteThere are some other ambiguities that are definition dependened and hence vary from author to author.
ReplyDeleteSome authors require permutable to have at least two different digits, otherwise you might end up with numbers like 1111111111111111111, 11111111111111111111111 . Correct me if I am wrong?
How does this fit with Mersenne Primes?
Some crackpot highfalutin inspiration perhaps.
ReplyDelete> (1) there are an infinite number of them
To say there are a finite number of them (a set with members with specific properties that satisfy constraints) is akin to solving the halting problem on a never-ending range. You can not say of a future prime number that you have not even computed, if it will have certain properties (twin prime, permutable prime) or not, much like you cannot say if the Kolmogorov Complexity of a string will be cleanly dividable by 2.
But just because you can not say it, it may still be so. But like P = NP it involves a degree of belief, not a certainty (for now). If betting, probably there are an infinite number of them, since there are an infinite number of primes to test if these pass property constraints.
To prove prime numbers are infinite, you first assume these are finite. If we want to use a similar proof for infinite permutable primes, we then must assume that we can solve the halting problem (that there are finite permutable primes), which is a very insane assumption, and if allowed, would also put us in a reality with many other crazy things, like breaking all encryption and super-Turing computation.
> (2) all those past 991 are of the form Rn
Very likely. Reasonable to assume true until proven otherwise by computing the previously unknown. To prove it would be akin to claiming to have solved the halting problem. So still proof that it is unprovable by Turing machines?