require 'openssl'

def md4(s)
  OpenSSL::Digest::MD4.hexdigest(s)
end

def brute
  i = 0
  loop do
    input = "0e#{i}"
    output = md4(input)
    puts "progress: #{input}" if (i % 100_000).zero?
    return [input, output] if md4(input)[/^0+e[0-9]+$/]
    i += 1
  end
end

puts brute