Phil Hantman posed an interesting question, which I will phrase in my own words.

  • Suppose that we choose five random integers between 0 and 9 inclusive (ordered, with replacement) and a target integer between 0 and 99 inclusive. What is the probability that the target integer can be generated from the other five integers using the operations of addition, subtraction, multiplication, and division?

There are 10^7 ways to choose the set of random integers, and many ways to combine these integers, so a naive brute force search is not feasible. But we can reduce the number of cases greatly using the fact that the order of the input numbers doesn't matter. For example, the same target values can be obtained with (3,3,4,5,6) and (4,5,6,3,3). The number of combinations with repetition allowed of 10 objects taken 5 at a time is C(10+5-1,5-1) = 2002.

My Python script uses this idea, and it also uses memoization to avoid redundant calculations. When the function combine_numbers is called, it looks up the input values in a table. If the input values exist in the table, then the function returns the previously computed output value. Otherwise, it computes the value, and then stores the result in the table before returning it.