This is an extended version of the numbers game on the UK TV gameshow Countdown, which is itself based off of a French gameshow (I don't know the details of it, though).<p>I had to solve this version of the problem once upon a time in a programming competition. I approached it slightly differently than this article; I implemented a RPN stack machine evaluator, and a recursive routine which permuted first over operators, then operands; the core routine looked like this:<p><pre><code> static int FindSolutions(int[] numbers, int numberIndex, int stackDepth)
{
int result = 0;
if (stackDepth == 1)
if (Evaluate(g_program.Program) == g_target)
++result;
// Try the operators (all are binary here)
if (stackDepth > 1)
{
for (OpCode opCode = OpCode.Add; opCode <= OpCode.Div; ++opCode)
{
g_program.Push(opCode);
result += FindSolutions(numbers, numberIndex, stackDepth - 1);
g_program.Pop();
}
}
if (numberIndex < numbers.Length)
{
// Try each number
for (int i = numberIndex; i < numbers.Length; ++i)
{
Swap(numbers, numberIndex, i);
g_program.Push(numbers[numberIndex]);
result += FindSolutions(numbers, numberIndex + 1, stackDepth + 1);
g_program.Pop();
Swap(numbers, numberIndex, i);
}
// Try without the number
result += FindSolutions(numbers, numberIndex + 1, stackDepth);
}
return result;
}
</code></pre>
If you know that g_program is writing the RPN program as a stack itself (so it can easily push and pop the last instruction), I think it's reasonably easy to follow.
An old math teacher of mine gave me this fun little problem: For each number n from 1 to 9, make 6 from three copies of n, using only basic-ish arithmetic and no other numbers. For example, 2+2+2 = 6. I will leave the rest as a puzzle for the reader.<p>Precise statement of restrictions (enumerating these may give you a bit of a hint): You're allowed to use these operators: + - * / √ !<p>I did this, and then I figured out that if you're allowed to use the floor function as well, you can fulfill this task for any n ≥ 1. If [x] denotes the floor of x, then I'll demonstrate with 56:<p>√56 is somewhat less than 8. √√56 is somewhat less than 3. √√√56 is somewhat less than 2. Then [√√√56] = 1. Thus, we can have: ([√√√56]+[√√√56]+[√√√56])! = 3! = 6.<p>The expression to find "number of times you'll have to take square root of n" is slightly interesting: we want to take k square roots and end up with something less than 2, so n^(1/2^k) < 2, or n < 2^(2^k), so k > log_2(log_2(n)).
Reasoning in the article has a flaw - no factorial is a perfect square, but how do you know all intermediate results need be integers? At the least, this deserves an additional argument. (Though it would be fair to say that factorial is only defined on integers, I think.)
Fascinating article. I remember in high school I had a teacher who set us a similar problem. We had to find every number from 0 to 30 with any operator but at most only four 2's. Most fun I've had in a math class ever.
Julian Bucknall just posted an article he wrote for PCPlus last year on this very subject.<p><a href="http://blog.boyet.com/blog/pcplus/pcplus-297-arithmetic-with-cards/" rel="nofollow">http://blog.boyet.com/blog/pcplus/pcplus-297-arithmetic-with...</a><p>As usual, well explained and interesting.