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).
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:
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;
}
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.
Precise statement of restrictions (enumerating these may give you a bit of a hint): You're allowed to use these operators: + - * / √ !
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:
√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.
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)).
This reminds me of Knuth's conjecture. http://www.perlmonks.org/?node_id=443037 (Starting with 3, apply some combination of factorial, square root, and floor functions. Knuth conjectured all natural numbers are achievable this way.)
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.)
The "no factorial is a perfect square" is used to justify why square roots are applied before any factorial on a given node of the evaluation tree.
No factorial is applied on a non integer intermediate result indeed, but if the intermediate result "becomes integer again", factorial are tried.
For example, if a candidate is (1/2) * 3 * 4 + 5, then the algorithm won't try to compute any factorial of (1/2) * 3 = 1.5, but it will consider (1/2) * 3 * 4 = 6.0 as integer and try the factorial on 6.
You've missed my point. Why do you not consider sqrt(3!)? It's not integral, but if you multiply by sqrt(6), the result IS integral. I don't think an optimal solution will have non-integral subexpressions, but you need an argument to justify that. Or you need to include them in your brute force search.
That's right, sorry I missed your point. I edited the post accordingly, thanks a lot for your input!
Note however that I did not pretend to have an exhaustive search, just a "brute" one to find a solution. I changed "enumerating all the candidate" to "enumerating the candidate" to remove some confusion.
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.
I'm somewhat amused that he says he found turning RPN to an infix expression awkward, because the easiest way of doing it (with redundant parentheses) is identical to actually evaluating the RPN, except you simply quote the operation you were going to apply, and the evaluation stack is made of strings.
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:
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.