In this article, we have explained the famous Brocard's problem and implemented solutions to find the 3 solutions to the problem.

Table of contents

1. Definitions
2. Algorithm
3. Time complexity
4. A way of implementation

1. Definitions

Henri Brocard postulated in 2 different years,1876 and 1885, that there is a relation between factorial numbers and the power of 2.
$$n! + 1 = m^2$$
Basically we do have to solve one equation with 2 unknown variables.

2. Algorithm

Since we have 2 variables to check for, 2 for loops will be required to solve the equation. Another thing that we might notice is that m will always be grather than n.
We start with initialization of one variable until we reach n, and then we initialize another variable with the value of the first one, until we reach the power of 2 of n.

    i <- 1;
    j <- i;
    
    loop( i <= n )
        {
        loop ( j <= n*n )
            {
            if ( factorial(i)+1 == j*j) 
                print ("Brown numbers (i,j)" );
            j <- j+1;
            }
        i <- i+1;
        }

The factorial implementation will depend on your side, since there are many ways to do so.

3. Time complexity

Since we are using 2 loops the overall time complexity is \(O(n^2)\)

4. A way of implementation

#include <iostream>

using namespace std;

unsigned long long factorial (unsigned long long n)
{
    unsigned long long i,p=1;
    
    if(n==1 || n==0) return 1;
    
    for (i=2; i<=n; i++)
        p*=i;
        
    return p;
}

void checkBrocardProblem(int n)
{
    for(int i=1; i<=n; i++)
        for (int j=i; j<=n*n; j++)
            if (factorial(i)+1 == j*j) cout<<"Brown numbers ("<<i<<","<<j<<")"<<endl;
}

int main()
{
    checkBrocardProblem(10);

    return 0;
}

Output:

Brown numbers (4,5)
Brown numbers (5,11)
Brown numbers (7,71)

It seems that the above pairs are the only ones known to satisfy the Brocard's equation, and they are named "Brown" after Clifford A. Pickover wrote in his 1995 book Keys to Infinity about this problem learned from Kevin S. Brown.

With this article at OpenGenus, you must have the complete idea of Brocard's problem.