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.

As an example, I've got a program running right now that's told me

1 = 1 * 1
10 = 2 * 5
111 = 3 * 37
100 = 4 * 25
10 = 5 * 2
1110 = 6 * 185
1001 = 7 * 143
1000 = 8 * 125
10 = 10 * 1
11 = 11 * 1
11100 = 12 * 925
1001 = 13 * 77
10010 = 14 * 715
1110 = 15 * 74
10000 = 16 * 625
11101 = 17 * 653
...

Other than possibly requiring some cloud rental time, brute force is easy:

require 'rspec'

def is_one_zero(n)
  n_string = n.to_s
  n_string.chars do |c|
    return false unless c == '1' || c == '0'
  end
  return true
end

def find_multiplier(input)
  mult = 1
  begin
    return mult if is_one_zero(input*mult)
    mult += 1
  end until mult > 1000000000000
  return -1
end

context 'hookup' do
  it "should hook up" do
    expect(2).to eq 2
  end
end

context 'recognizing one-zero numbers' do
  it "should accept 1010101010101010101010101010101010101010" do
    large_number = 1010101010101010101010101010101010101010
    ok = is_one_zero(large_number)
    expect(ok).to be true
    large_number = large_number + 2
    expect(is_one_zero(large_number)).to be false
  end

  it "should find least multiplier" do
    input = 12
    output = find_multiplier(input)
    expect(is_one_zero(input*output)).to be true
    puts output
  end
end

(1..100).each do |i|
  mult = find_multiplier(i)
  puts "#{i} * #{mult} = #{i*mult}"
end

interesting that you went for construction and i went for discovery.

what's a good way to enumerate increasing pairs without a boundary value?

i guess x = 1..inf, y = 1..x

Do me a favor and drop code fencing around the code?

I plugged your series of solutions to this into OEIS and found

https://oeis.org/A079339

A079339 Least k such that the decimal representation of k*n contains only 1's and 0's.

which gives as its formula a relation to this sequence

A004290 Least positive multiple of n that when written in base 10 uses only 0's and 1's.

which in turn leads to

Chai Wah Wu
The American Mathematical Monthly
Vol. 121, No. 6 (June–July), pp. 529-533

which gives an existence proof via the Pigeonhole Principle.

Awesome.

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