Extending the Search for Brocard's Problem: From 10¹² to 10¹⁵

Introduction

Brocard's problem, posed by Henri Brocard in 1876, asks if there are integers n and m such that n! + 1 = m^2. Known solutions include n = 4, 5, and 7, with extensive searches up to 10^12 yielding no additional solutions. Inspired by the comprehensive paper by Robert D. Matson, I sought to extend the search up to 10^15.

Understanding the Paper

Matson's paper utilized quadratic residues and the Legendre symbol to efficiently test large values of n. The approach relies on testing n! + 1 against a set of large primes to determine if it could be a perfect square. If n! + 1 is not a quadratic residue modulo any of these primes, then n is not a solution.

Developing the Code

Using the insights from Matson's paper, I developed a C++ program that partitions the search range (1, 10^15) into smaller sub-ranges and employs parallel processing to improve efficiency. Here's a breakdown of the key steps in the code:

Initialization: The program initializes a list of large primes and prepares the search ranges.
Parallel Processing: The search range is divided into smaller chunks, each processed in parallel to speed up the computation.
Modular Arithmetic and Jacobi Symbol: For each candidate n, the program calculates n! + 1 and tests it against the set of primes using the Jacobi symbol to determine if it is a quadratic residue.
Logging and Results: Potential solutions are logged and written to a file, with progress updates printed to the console.

// Example of logging output
std::cout << "Testing range " << start << " to " << end << std::endl;
if (is_potential_solution) {{
    std::cout << "Potential solution found: n = " << n << ", m = " << m << std::endl;
}}

Running the Program

The program systematically tests each sub-range, leveraging modern multi-core processors to handle the extensive calculations required. Despite the extended range, no new solutions were found up to 10^15.

Conclusion

The extension of the search for solutions to Brocard's problem from 10^12 to 10^15 showcases the power of combining theoretical insights with computational methods. While no new solutions were discovered, the process highlights the importance of continued exploration and the potential for future discoveries in number theory.