"Fred W. Helenius" <fredh@ix.netcom.com> wrote:

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.

Interesting. Thanks. I think allowing leading zeros makes the problem better, since you otherwise have an annoying asymmetry where it's not always the case that if you can get A from B via a single bit flip you can get B from A the same way. Does this generalize to powers of numbers other than 2? To the Fibonacci sequence, i.e. is there a number which when added to any Fibonacci number is always composite? To any other interesting sequences? Thanks.