\n#! /usr/bin/ruby -w\n\n# With one argument, the product 1*2*..*n\n# With two arguments with m <= n, the product m*(m+1)*..*n\n# With two arguments with n < m, 1.\ndef factorial(n, m=1)\n  n = n.to_i;\n  m = m.to_i;\n  product = 1;\n  (m..n).each {|i| product *= i}\n  product\nend\n\n# Sums an array.\ndef sum(numbers)\n  ans = 0;\n  numbers.each{|i| ans += i}\n  ans\nend\n\n# The number of ways to find m things in n.\n@choose_cache = Hash.new\ndef choose(n, m)\n  key = "#{n} #{m}";\n  unless @choose_cache.has_key?(key)\n    if (m > n/2)\n      m = n - m;\n    end\n    @choose_cache[key] = factorial(n, n + 1 - m) / factorial(m);\n  end\n  return @choose_cache[key]\nend\n\n# Calculate the number of possible birthday assignments to some number of\n# people using some number of days with a given maximimum number of people\n# getting the same day.\n@birthday_assignments = Hash.new();\ndef possible_birthday_assignments(people, days, max_one_day)\n  if (people > days*max_one_day)\n    return 0;\n  elsif days < 2\n    return 1;\n  else \n    key = "#{people}|#{days}|#{max_one_day}";\n    ans = 0;\n    unless @birthday_assignments.has_key?(key)\n      if (days/2*2 == days)\n        # Divide the days in half\n        (0..people).each {|people_in_first|\n          ans += possible_birthday_assignments(\n              people_in_first,\n              days/2,\n              max_one_day\n            ) * possible_birthday_assignments(\n              people - people_in_first,\n              days/2,\n              max_one_day\n            ) * choose(people, people_in_first);\n        }\n      else\n        # Divide people in 1 day, people in the rest\n        limit = people < max_one_day ? people : max_one_day\n        (0..limit).each{ |people_in_first|\n          ans += possible_birthday_assignments(\n            people - people_in_first,\n            days - 1,\n            max_one_day\n          ) * choose(people, people_in_first)\n        }\n      end\n      @birthday_assignments[key] = ans;\n    end\n    return @birthday_assignments[key];\n  end\nend\n\ndef fraction_to_float(a, b)\n  precision = 100_000_000;\n  return ( (a * precision + a/2)/b ).to_f / precision;\nend\n\n# Calculate birthday probability but ignore leap day.\ndef basic_birthday_probability(people, max_one_day)\n  count = possible_birthday_assignments(people.to_i, 365, max_one_day.to_i)\n  return fraction_to_float(count, 365**(people.to_i));\nend\n\n# Calculate birthday probability and include leap day.\ndef birthday_probability(people, max_one_day)\n  people = people.to_i;\n  max_one_day = max_one_day.to_i;\n  limit = people < max_one_day ? people : max_one_day;\n  ans = 0;\n  (0..limit).each {|i|\n    ans += basic_birthday_probability(\n        people - i, max_one_day\n      ) * fraction_to_float(\n        choose(people, i) * (365*4)**(people-i),\n        (365*4 + 1)**people\n      );\n  }\n  return ans;\nend\n\nprob = birthday_probability(*ARGV);\nputs "Odds #{prob} that #{ARGV[0]} people have at most #{ARGV[1]} birthdays together";\n