from Hacker News

The answer is 2011. The question can be brute force.

by qbonnard on 10/27/11, 12:18 PM with 20 comments

  • by barrkel on 10/27/11, 2:37 PM

    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.

  • by waterhouse on 10/27/11, 1:48 PM

    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)).

  • by shasta on 10/27/11, 3:18 PM

    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.)

  • by franze on 10/27/11, 1:48 PM

  • by chrislloyd on 10/27/11, 1:51 PM

    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.

  • by lt on 10/27/11, 3:10 PM

    Julian Bucknall just posted an article he wrote for PCPlus last year on this very subject.

    http://blog.boyet.com/blog/pcplus/pcplus-297-arithmetic-with...

    As usual, well explained and interesting.

  • by VMG on 10/27/11, 3:06 PM

    I'm curious to know what a list implementation would look like

  • by jsvaughan on 10/27/11, 2:35 PM

    nice work but pity about the caveat "That leaves the door open to solutions with less than 5 initial numbers. I would bet that there aren't any..."

  • by munin on 10/27/11, 2:42 PM

    isn't this what SAT solvers are for?