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.
[Dagnabbit, I accidentally deleted the earlier version! Let me try to recover it...]
Based on an offhand comment to @Morendil, I decided to design-spike a weird ass-backwards approach---one I should point out I would never have thought of at all without this conversation. So thanks!
Basically in this Ruby code I
Enumerator
that generates every number containing only 0 and 1, up to a given sizeSet
instance, so I don't have to worry about the many many many repeated ones)So for example if the
Enumerator
gives me10
as the product, the factors are[1,2,5]
, and the possible partitions are[[1,10],[2,5]]
.Anyway, it's weird. It prints each product, its factors, and the pairs it has found, one per line. Setting the number of digits to 9 produces the entire result in 3.4 seconds, including print time, on my antique laptop.
And now I want to know how many other other ways there are to approach it.