Finding if n! + 1 is a perfect square

Question

I'm trying to write a program to look for a number, n, between 0 and 100 such that n! + 1 is a perfect square. I'm trying to do this because I know there are only three so it was meant as a test of my Python ability.

Refer to Brocard's problem.

Answer 1

For very large numbers it's better to avoid using floating point square roots altogether because you will run into too many precision issues and you can't even guarantee that you will be within 1 integer value of the correct answer. Fortunately Python natively supports integers of arbitrary size, so you can write an integer square root checking function, like this:

def isSquare(x):
    if x == 1:
        return True
    low = 0
    high = x // 2
    root = high
    while root * root != x:
       root = (low + high) // 2
       if low + 1 >= high:
          return False
       if root * root > x:
          high = root
       else:
          low = root
    return True

Then you can run through the integers from 0 to 100 like this:

n = 0
while n <= 100:
    x = math.factorial(n) + 1
    if isSquare(x):
        print n
    n = n + 1