A Pythonic Approach to a Math Problem
A few months ago, a friend of mine gave me a math problem and challenged me to find an elegant solution in Python. The problem was as follows:
Find the number of ordered pairs \((a,b,c,d)\) such that the equation -
\[(a^2 + b^2)(c^2 + d^2) = n\]
for a given n, where \(n \in \mathbb{N}\) and \(a,b,c,d \in \mathbb{Z}\), is satisfied.
An obvious but most inelegant way is to just create a quadruple nested loop and find all the pairs using pure brute force, something, which we shall actively avoid for we are trying to find a somewhat elegant solution. So, how should one proceed with this anyway?
The trick is to break the problem into multiple even smaller problems, here's how I did it -
First, notice that \(\forall\) \(a,b \in \mathbb{Z}\), \(a^2 + b^2\) also \(\in \mathbb{Z}\). Thus, the required problem can be broken down into something like this - \[A \times B = n\] where \(A = a^2 + b^2\) and \(B = c^2 + d^2\). This gives us a hint to only work with the factors of n, maybe factorise n and iterate through the factors? Well it might work, lets see.
Next, consider A, observe that for \((a,b)\) to be a valid solution, \(A-a^2\) and \(A-b^2\) must be squares. If only we had a function that could check if something is a perfect square!. Worry not! we shall create one for ourselves.
Next, see that \(A\) and \(B\) are factors of \(n\), basically, we are required to find the number of ordered pairs of integers, the sum of squares of which equals \(A\) and \(B\) respectively that is, \(\forall\) \(i \in F_n\) , if \(i\) and \(\frac{n}{i}\) can be represented as the sum of the squares of two integers then we shall count those two integers in a pair (where \(F_n\) represents the set of all the factors of \(n\)).
Now, the whole problem suddenly becomes clear! We have to construct a function that can check if a number is representable as the sum of the squares of two integers (that number should be \(A\) and \(B\) in our case) and then we must have both \(A\) and \(B\) as factors of n, so basically we must iterate through an array filled with the factors of n!.
Now lets begin with the actual code for the problem -
The factoriser
Obviously, since \(A\) and \(B\) are factors of \(n\), we must first find the factors of n and store them in an array, we shall construct a function to find the factors of n
def factors(n):
factor=[]
for i in range(1,int(n**(0.5)) + 1):
if n%i == 0:
factor.append(i)
factor.append(n//i)
factor.sort()
return factor
note - We are appending both \(i\) and \(\frac{n}{i}\) even in the case of perfect squares as we shall take care of it later. (As in we are appending 10 twice in case of n = 100)
The integer verifier
A very small program just to check if something is an integer, we will require it when checking if \(\sqrt{a}\) and \(\sqrt{A - a^2}\) are integer or not.
def int_check(n):
if int(n) == n:
return True
else:
return False
The square checker
This program will check if a number can be written as a sum of squares of two integers and then append those two integers in an array if its possible to do so.
def square_check(n):
ans = []
for i in range(0,int(n+1)):
a = i**(0.5)
b = (n-i)**(0.5)
if int_check(a) and int_check(b):
'''ans+=[(int(a),int(b))]'''
if (a*b!=0):
ans+=[(a,b),(a,-b),(-a,b),(-a,-b)]
elif a==0:
ans+= [(a,b),(a,-b)]
elif b==0:
ans+= [(a,b),(-a,b)]
return ans
The final Part
Finally, we shall iterate through the list of all the factors of n.
#We have a number n with us
extra_case = False
ans = True
if n == 0:
print(1)
else:
count = 0
for i in factors(n):
a = i
b = int(n/i)
if a!=b:
#print(int(square_check(int(a)),square_check(int(b)), a , b)'''
count+=len(square_check(a))*len(square_check(b))
print(len(square_check(a))*len(square_check(b)), a , b)
#print(count)
elif a == b and extra_case==False:
#print(square_check(int(a)),square_check(int(b)), a , b)
count+=len(square_check(a))*len(square_check(b))
print(len(square_check(a))*len(square_check(b)), a , b)
extra_case = True
#print(count)
print(count)
Let us try to understand what its actually doing, let \(F_n\) denote the set of all the factors \(1 = f_1,f_2,...,f_k = n\) of \(n\). We are iterating through this set, and for each \(f_i\), \(1 \leq i \leq k\), we are checking if \(f_i\) and \(\frac{n}{f_i}\) are each representable as the sum of two squares. If its possible, we are appending those squares in a list and all their negative combinations as well. (since if \((a,b,c,d)\) is a solution to the given equation then so is \((-a,-b,c,d)\), in fact \((\pm a,\pm b,\pm c, \pm d)\) is a solution set. At the end, we are just giving the length of the list as the output.
The Program
Here's the complete program, along with a few test cases.
def int_check(n):
if int(n) == n:
return True
else:
return False
def factors(n):
factor=[]
for i in range(1,int(n**(0.5)) + 1):
if n%i == 0:
factor.append(i)
factor.append(n//i)
factor.sort()
return factor
def square_check(n):
ans = []
for i in range(0,int(n+1)):
a = i**(0.5)
b = (n-i)**(0.5)
if int_check(a) and int_check(b):
'''ans+=[(int(a),int(b))]'''
if (a*b!=0):
ans+=[(a,b),(a,-b),(-a,b),(-a,-b)]
elif a==0:
ans+= [(a,b),(a,-b)]
elif b==0:
ans+= [(a,b),(-a,b)]
return ans
print("This is a computer program to calculate the number of integer solutions to the equation (A^2 + B^2)(C^2 + D^2) = n where n is the input")
# n = int(input("Enter the input - "))
extra_case = False
ans = True
if n == 0:
print(1)
else:
count = 0
for i in factors(n):
a = i
b = int(n/i)
if a!=b:
#print(int(square_check(int(a)),square_check(int(b)), a , b)'''
count+=len(square_check(a))*len(square_check(b))
print(len(square_check(a))*len(square_check(b)), a , b)
#print(count)
elif a == b and extra_case==False:
#print(square_check(int(a)),square_check(int(b)), a , b)
count+=len(square_check(a))*len(square_check(b))
print(len(square_check(a))*len(square_check(b)), a , b)
extra_case = True
#print(count)
print("The total number of ordered pairs for the given value of n: ",count)
For n = 100, we get the following output. The format of the output is the number of integers \((a,b,c,d)\) for the numbers \(A\) and \(B\), where \(A\) and \(B\) are the factors of n = 100.
This is a computer program to calculate the number of integer solutions to the equation (A^2 + B^2)(C^2 + D^2) = n where n is the input 48 1 100 48 2 50 48 4 25 64 5 20 64 10 10 64 20 5 48 25 4 48 50 2 48 100 1 480
note - We accounted for the repeated occuring of \(\sqrt{n}\) in case of \(n\) being squared by introducing a bool extra_case. As soon as we encounter the repeated factor, we simply calculate the value and flip the boolean to True thus avoiding it at a later point of time (which is just the next iteration).
Some things about the solution :
While I do agree that its not the most efficient solution, in fact it's probably a lot more inefficient since for each factor of n, we are doing about \(O(k)\) work which, when added with all the factors, results in a bigger time complexity and it scales even poorly for a larger value of \(n\).
But that being said, I still think deconstructing a problem is the best way to go about solving one. Fragmenting it into various smaller related problems and then attacking each one of them simplifies it to such an extent where solving the whole problem becomes less tedious.
Not to mention its still better than the brute force solution with a monstrous time complexity of around \(O(n^4)\).
I also think that implementing the same in scheme (a dialect of Lisp) would have been way more fun but that's for some other time!