Cliff Pickover’s puzzle from 2006-02-22 queries the reader to come up with 3 pairs, or possibly more, of numbers, m and n, which satisfy the equation n! + 1 = m². I didn’t think too hard about it. I just went straight to code which turned out to be a good thing because one of the solutions is quite large. Click more to see the reasoning I went through and the solutions output from my program.

My first impulse was to try as many pairs of numbers as I had enough computing cycles to test. Then I decided it would be marginally more efficient to compute the factorial, add 1, and see if the square root of that sum is a whole number. Actually, this is very efficient since not many factorials need to be computed before the factorial is too large to fit inside a 64-bit number (30! seems to do the trick). This method yielded the “at least” 3 solutions.

But the big brain guy asked if there were anymore solutions. One small problem with the previous approach is that it seems somewhat constrained to 64 bits because of its need to compute square roots. Another method, strictly integer-based, is to count up through values of m, square m, subtract 1 and then figure out if the difference is a valid factorial by dividing 2, then 3, then 4, etc. For this exercise, the second method will only yield the same results as the first method, only more slowly. However, it seems reasonable that, combined with a decent “big integer” programming library, this method could seek much higher.

Here are the solutions:

method 1 (compute factorial, add 1, compute square root):
  solution for n! + 1 = m^2: n = 4, m = 5
  solution for n! + 1 = m^2: n = 5, m = 11
  solution for n! + 1 = m^2: n = 7, m = 71
method 2 (compute square, subtract 1, iteratively divide):
  solution for n! + 1 = m^2: n = 4, m = 5
  solution for n! + 1 = m^2: n = 5, m = 11
  solution for n! + 1 = m^2: n = 7, m = 71

Pickover’s solutions were, thankfully, the same as mine. Apparently, this is a problem put forth by some famous math dude who had offered a cash prize to anyone who could find another solution. Given that kind of motivation it seems reasonable that someone smarter than me has come up with better methods and used computers to search much larger possibilities. Still, there have apparently been no other solutions found.

I’m glad to learn that there wasn’t an obvious deductive solution to the problem. Or is there? Anyway, here are the more interesting parts of the code, the 2 search methods:

    fprintf (f, "method 1 (compute factorial, add 1, compute square root):\n");
    fflush(f);
    n = 0;
    while (++n) {
        fact = factorial(n);
        square_root = sqrt(fact + 1);
        /* if we have hit this constant, we are are the end of the useful
         * numerical range */
        if ((int)square_root == -2147483648)
            break;
        if (square_root - floor(square_root) < 0.00001)
            fprintf (f, "  solution for n! + 1 = m^2: n = %d, m = %d\n",
                n, (int)square_root);
            fflush(f);
    }

    fprintf (f, "method 2 (compute square, subtract 1, iteratively divide):\n");
    fflush(f);
    m = 2;
    while (++m < 0x7FFFFFFFFFFFFFFFULL) {
        if (m % 1000000 == 0) {
            fprintf (f, "testing %lld\n", m);
            fflush(f);
        }
        square = m * m;
        square--;
        n = 1;
        while (++n) {
            if ((square / n == 1) && (square % n == 0)) {
                fprintf (f, "  solution for n! + 1 = m^2: n = %d, m = %lld\n",
                    n, m);
                fflush(f);
            } else if (square % n == 0)
                square /= n;
            else
                break;
        }
    }

C code colorized by the CodeColorizer.