Peter Winkler, in one of the first puzzles in his excellent Mathematical Puzzles: A Connoisseur's Collection, asks for proof that every positive integer can be multiplied by some (other) integer, and the resulting product will contain only the digits 0
and 1
.
As prep for a small project, I'd rather ask you: For each of the first 100 integers (or 1000 if you're ambitious), what is the smallest integer multiplicand which gives a product with only 1
and 0
among its base-10 digits?
Real question for you: How did you find them? Code welcomed, any language.
The Pigeonhole Principle is awesome here because it proves that there's an upper bound to the number that you're searching for.
Generate a series of target candidates (1, 11, 111, 1111, ... , n ones). For each of them test your number against the candidate and see if it divides evenly. If it does not, compute the remainder.
We try this with the number 4, and get remainders 1, 3, 3, 3. We know by the pigeonhole principle that if you have 4 numbers picked from a set of 4 alternatives that you have at least one number that's picked twice, or you get an exact match on zero remainder . Subtract the smaller from the larger and you have a result that's all 1's and 0's (a series of 1s followed by a series of 0s). That's a solution, and an upper bound.