tag:blogger.com,1999:blog-3722233.post7486493523166407962..comments2024-09-11T21:44:26.059-05:00Comments on Computational Complexity: Permutable Primes and Compatible PrimesLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-3722233.post-63575327236189288662023-08-13T13:00:27.459-05:002023-08-13T13:00:27.459-05:00And 7*3=21 ;)And 7*3=21 ;)Rolandhttp://rolandglueck.de/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-27675665311272720172023-08-09T20:12:33.880-05:002023-08-09T20:12:33.880-05:00Some crackpot highfalutin inspiration perhaps.
&g...Some crackpot highfalutin inspiration perhaps.<br /><br />> (1) there are an infinite number of them<br /><br />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.<br /><br />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.<br /><br />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.<br /><br />> (2) all those past 991 are of the form Rn<br /><br />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?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30938430413740290562023-08-08T20:31:27.144-05:002023-08-08T20:31:27.144-05:00There are some other ambiguities that are definiti...There are some other ambiguities that are definition dependened and hence vary from author to author.<br />Some 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?<br />How does this fit with Mersenne Primes? Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-65169105140455563042023-08-08T19:52:54.402-05:002023-08-08T19:52:54.402-05:00Yes, the paper IF IT IS A GEM should have been upl...Yes, 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-4636789700778513612023-08-08T17:08:54.862-05:002023-08-08T17:08:54.862-05:00Wikipedia says that the problem: 'Are there an...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. William Gasarchnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-41588372726159536202023-08-08T10:55:34.434-05:002023-08-08T10:55:34.434-05:00If we search for permutable primes in binary we im...If 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).<br /><br />So 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.Robertnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19040829558320267162023-08-08T09:09:33.345-05:002023-08-08T09:09:33.345-05:00Fun fact. 73 is the 21st prime number and its mir...Fun fact. 73 is the 21st prime number and its mirror, 37, is the 12th.Sheldonnoreply@blogger.com