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.
@Morendil my original algorithm was even more brute-force than yours, since it just walked through a moderate range of a hundred for each multiplicand, and stopped when it found a match, or skipped if it didn't find one. An even dirtier one (but also interesting, because it opens up another question or two) just made every number possible from
{0,1}
and factored them all. :)@vielmetti Did you read the answer in the back of the book for that, or one of the papers? Because it's actually quite close to what Winkler describes, though subtly different.
Also: @RonJeffries asked what other pairs of numerals might work. I don't know, especially in other base representations, but of course any
{x,0}
numeral pair will work in base 10 just by multiplying out the{0,1}
answer byx
.