Winkler ZeroesAndOnes

challenge.md

Which Zeroes and Ones?

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.

Haskell:

map (\y -> take 1 (filter (\x-> (fromList (show (x * y))) `isSubsetOf` (fromList "01")) [1..])) [1..100]

(My style is neither elegant nor idiomatic, and this is brute force with little thought going into it. But it's a start. And it fits in a tweet!)

BTW, the result for 9 is missing from your list above. That's a shame, as it's a lovely one.

9 is large, if i recall. 12,345,679?

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.

@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 by x.

@Vaguery that's the algorithm in The American Mathematical Monthly article that I found. It guaranteed a solution that's a bunch of 1's followed by a bunch of 0's, which turns out to be suboptimal when n=7.

Also, do more like this!

[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

• build a ruby Enumerator that generates every number containing only 0 and 1, up to a given size
• factor that into its prime factors
• produce every possible pair of multiplicands, based on those prime factors, and store them (in a Set instance, so I don't have to worry about the many many many repeated ones)

So for example if the Enumerator gives me 10 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.

require 'prime'
require 'set'

# generator for all integers up to a given length containing only 0 and 1
["0","1"].repeated_permutation(9) do |variant|
  product = "#{variant.join}".to_i
  unless product < 2
    factors = product.prime_division # e.g. 10 -> [[2,1],[5,1]]
    factor_list = factors.inject([1]) do |list,prime_count|
      list += Array.new(prime_count[1], prime_count[0])
    end

    # now recombine the prime factors we've collected to make all pairs of multipliers
    pairs = Set.new()

    # we had such luck with repeated_permutation before, let's use it again
    [true,false].repeated_permutation(factor_list.length) do |mask|
      arg1,arg2 = 1,1
      mask.each_with_index do |i,idx|
        prime = factor_list[idx]
        i ? arg1 *= prime : arg2 *= prime
      end
      pairs.add([arg1,arg2].sort)
    end

    puts "#{product} has factors #{factor_list.inspect} >> #{pairs.to_a.sort}" 
  end
end

A minor modification, so it prints a list of numbers it's actually accounted for anywhere along the way.

require 'prime'
require 'set'

found_factors = Set.new()

# generator for all integers up to a given length containing only 0 and 1
["0","1"].repeated_permutation(9) do |variant|
  product = "#{variant.join}".to_i
  unless product < 2
    factors = product.prime_division # e.g. 10 -> [[2,1],[5,1]]
    factor_list = factors.inject([1]) do |list,prime_count|
      list += Array.new(prime_count[1], prime_count[0])
    end

    # now recombine the prime factors we've collected to make all pairs of multipliers
    pairs = Set.new()

    # we had such luck with repeated_permutation before, let's use it again
    [true,false].repeated_permutation(factor_list.length) do |mask|
      arg1,arg2 = 1,1
      mask.each_with_index do |i,idx|
        prime = factor_list[idx]
        i ? arg1 *= prime : arg2 *= prime
      end
      pairs.add([arg1,arg2].sort)
      found_factors.merge([arg1,arg2])
    end

    puts "#{product} has factors #{factor_list.inspect} >> #{pairs.to_a.sort}" 
  end
end

puts "\nNumbers accounted for: #{found_factors.to_a.sort.inspect}"