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.

[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}"