Improving the complexity of Brocard's problem?

Question

Brocard's problem is n! + 1 = m^2. The solutions to this problems are pairs of integers called Brown numbers (4,5), etc, of which only three are known.

A very literal implementation to Brocard's problem:

import math 

def brocard(n,m):
    if math.factorial(n)+1 == m**2:
        return (n,m)
    else:
        return

a=10000

for n in range(a):
    for m in range(a):
        b=brocard(n,m)
        if b is not None:
            print(b)

The time complexity of this should be O(n^2) because of the nested for loops with differing variables and the complexity of whatever math.factorial algorithm is (apparently divide-and-conquer). Is there any way to improve upon O(n^2)?

There are other interpretations on SO like this. How does the time complexity of this compare with my implementation?

Have you run that program? How long did it take to finish? Are the results correct? — Ralf Kleberhoff, Dec 15 '20 at 14:55
@RalfKleberhoff Yes, the results are correct. Timing it has opened up a can of worms for me, though... (4, 5) 0.0213 seconds, (5, 11) 0.030 seconds, (7, 71) 0.04362 seconds. There are actually no solutions beyond this up to some crazy number like 10^15. However, if I time just after brocard(n,m) is called, I can see that it takes 75.7325 just to reach (1,9999)->(2,0)... So how can it get (7,71) in 0.04362s?! — smollma, Dec 16 '20 at 00:05

Ralf Kleberhoff · Accepted Answer · 2020-12-16T10:20:49.273

Your algorithm is O(n^3).

You have two nested loops, and inside you use factorial(), having O(n) complexity itself.

Your algorithm tests all (n,m) combinations, even those where factorial(n) and m^2 are far apart, e.g. n=1 and m=10000.

You always recompute the factorial(n) deep inside the loop, although it's independent of the inner loop variable m. So, it could be moved outside of the inner loop.

And, instead of always computing factorial(n) from scratch, you could do that incrementally. Whenever you increment n by 1, you can multiply the previous factorial by n.

A different, better approach would be not to use nested loops, but to always keep n and m in a number range so that factorial(n) is close to m^2, to avoid checking number pairs that are vastly off. We can do this by deciding which variable to increment next. If the factorial is smaller, then the next brocard pair needs a bigger n. If the square is smaller, we need a bigger m.

In pseudo code, that would be

n = 1; m = 1; factorial = 1;
while n < 10000 and m < 10000
    if factorial + 1 == m^2
        found a brocard pair
        // the next brocard pair will have different n and m,
        // so we can increment both
        n = n + 1
        factorial = factorial * n
        m = m + 1
    else if factorial + 1 < m^2
        // n is too small for the current m
        n = n + 1
        factorial = factorial * n
    else
        // m is too small for the given n
        m = m + 1

In each loop iteration, we either increment n or m, so we can have at most 20000 iterations. There is no inner loop in the algorithm. We have O(n). So, this should be fast enough for n and m up to the millions range.

P.S. There are still some optimizations possible.

Factorials (after n=1, known to have no brocard pair) are always even numbers, so m^2 must be odd to satisfy the brocard condition, meaning that we can always increment m by 2, skipping the even number in between.

For larger n values, the factorial increases much faster than the square. So, instead of incrementing m until its square reaches the factorial+1 value, we could recompute the next plausible m as integer square root of factorial+1.

Or, using the square root approach, just compute the integer square root of factorial(n), and check if it matches, without any incremental steps for m.

Improving the complexity of Brocard's problem?

1 Answers1