Sometimes, when writing a program, you need to use a prime number for some reason or other (e.g. cryptography). I assume that sometimes, you need to use a composite number, too. Sometimes, at least here on PPCG, your program has to be able to deal with arbitrary changes. And in circumstances conveniently contrived to make an interesting PPCG question, perhaps even the numbers you're using have to be resistant to corruption…
A composite number is an integer ≥ 4 that isn't prime, i.e. it is the product of two smaller integers greater than 1. A bitflip-resistant composite number is defined as follows: it's a composite positive integer for which, if you write it in binary in the minimum possible number of bits, you can change any one or two bits from the number, and the number is still composite.
For example, consider the number 84. In binary, that's
1010100. Here are all the numbers which differ by no more than 2 bits from that:
0000100 4 2×2 0010000 16 4×4 0010100 20 4×5 0010101 21 3×7 0010110 22 2×11 0011100 28 4×7 0110100 52 4×13 1000000 64 8×8 1000100 68 4×17 1000101 69 3×23 1000110 70 7×10 1001100 76 4×19 1010000 80 8×10 1010001 81 9×9 1010010 82 2×41 1010100 84 7×12 1010101 85 5×17 1010110 86 2×43 1010111 87 3×29 1011000 88 8×11 1011100 92 4×23 1011101 93 3×31 1011110 94 2×47 1100100 100 10×10 1110000 112 8×14 1110100 116 4×29 1110101 117 9×13 1110110 118 2×59 1111100 124 4×31
The first column is the number in binary; the second column is the number in decimal. As the third column indicates, all of these numbers are composite. As such, 84 is a bitflip-resistant composite number.
You must write one of the following three programs or functions, whichever makes the most sense for your language:
- A program or function that takes a nonnegative integer n as input, and outputs the first n bitflip-resistant composite numbers.
- A program or function that takes a nonnegative integer n as input, and outputs all bitflip-resistant composite numbers less than n (or if you prefer, less than or equal to n, i.e. you can choose whether n is included in the output if bitflip-resistant).
- A program or function that takes no input, and outputs all bitflip-resistant composite numbers. (This must use an output mechanism capable of producing output while the program is still running, such as printing to stdout, a lazy list, or a generator; you can't just calculate the entire list and then print it.)
Here are the first few bitflip-resistant composite numbers:
84, 184, 246, 252, 324, 342, 424, 468, 588, 636, 664, 670, 712, 730, 934, 958
- It's only the numbers you produce that have to be resistant to bitflips. This isn't a task about making the program that finds them resistant to bitflips; use whatever numbers in the program itself that you like.
- The numbers you output don't have to be resistant to a bitflip in the "leading zeroes"; imagine that the numbers will be stored in the minimum possible number of bits, and only those bits have to be immune to flipping. However, the initial 1 bits on the numbers you output do have to be immune to bitflips.
- Use any algorithm you like that produces the right result; you aren't being marked on efficiency here.
- If you can prove that there are finitely many bitflip-resistant composite numbers, then a) the restrictions on output format are lifted, and b) hardcoding the list will be allowed (although probably more verbose than just calculating it). This rule is mostly just for completeness; I don't expect it to be relevant.
This is code-golf, so as usual, shorter is better. Also as usual, the length of the program will be measured in bytes.