Re: [math-fun] How often does every bit matter?
Warren D Smith <warren.wds@gmail.com> wrote:
Each of the following is a prime number P, such that if any single bit of P's binary representation is changed, then you no longer have a prime. (And this is the full list of such P<10000.)
I take it that leading zeros aren't allowed. If they are, I suspect the list would be empty, as any entry would be an odd prime such that if you add any power of 2 to it the result will always be composite. I doubt such a number exists, but I can't see how to prove it.
On 3/30/2013 3:27 PM, Keith F. Lynch wrote:
Warren D Smith <warren.wds@gmail.com> wrote:
Each of the following is a prime number P, such that if any single bit of P's binary representation is changed, then you no longer have a prime. (And this is the full list of such P<10000.)
I take it that leading zeros aren't allowed. If they are, I suspect the list would be empty, as any entry would be an odd prime such that if you add any power of 2 to it the result will always be composite. I doubt such a number exists, but I can't see how to prove it.
271129 is such a number; it is prime and 271129 + 2^k is always divisible by (at least) one of 3, 5, 7, 13, 17 and 241. 271129 is also, not coincidentally, the smallest prime proved to be a Sierpinski number (n such that n*2^k + 1 is composite for all k). Any number proved to be a Sierpinski number by using covering congruences (the only method known) will also have n + 2^k composite for all k. Relevant OEIS sequences: A076336, A137715, A094076. -- Fred W. Helenius fredh@ix.netcom.com
Re the Sierpinski problem this link: http://www.prothsearch.net/sierp.html may be of interest, especially the March 2013 update. On Sat, Mar 30, 2013 at 3:44 PM, Fred W. Helenius <fredh@ix.netcom.com>wrote:
On 3/30/2013 3:27 PM, Keith F. Lynch wrote:
Warren D Smith <warren.wds@gmail.com> wrote:
Each of the following is a prime number P, such that if any single bit of P's binary representation is changed, then you no longer have a prime. (And this is the full list of such P<10000.)
I take it that leading zeros aren't allowed. If they are, I suspect the list would be empty, as any entry would be an odd prime such that if you add any power of 2 to it the result will always be composite. I doubt such a number exists, but I can't see how to prove it.
271129 is such a number; it is prime and 271129 + 2^k is always divisible by (at least) one of 3, 5, 7, 13, 17 and 241. 271129 is also, not coincidentally, the smallest prime proved to be a Sierpinski number (n such that n*2^k + 1 is composite for all k). Any number proved to be a Sierpinski number by using covering congruences (the only method known) will also have n + 2^k composite for all k.
Relevant OEIS sequences: A076336, A137715, A094076.
-- Fred W. Helenius fredh@ix.netcom.com
______________________________**_________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/**cgi-bin/mailman/listinfo/math-**fun<http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun>
participants (3)
-
Fred W. Helenius -
James Buddenhagen -
Keith F. Lynch