All Pythagorean Triplets Less Than Equal to N in Optimal Time Complexity
Pythagorean Triplets are set of three ordered positive integers (x,y,z) such that
x^2 + y^2 = z^2 --- (1)
where,
x < y < z <= NThere are several techniques for generating Pythagorean Triplets for example using Gaussian Integers and using Euclid’s formula. They can be used to generate all primitive Pythagorean Triplets, which again can be used to generate all non-primitive Pythagorean triplets by using the fact that the non Primitive Pythagorean triples are a positive integer multiple of primitive Pythagorean Triplets.
Generating Pythagorean triplets simply using two loops by iterating over x and y for all possible x and y, and checking if they satisfy Equation (1), takes time O(N² ). Also using the above methods for generating primitive Pythagorean triplets and from them generating all Pythagorean triples may take time O(N² ).
I used Equation (2) which easily follows from Equation (1) by solving the quadratic equation for x, thus for “ x > 0 ”,
x = (b - a) + sqrt{2b(b - a)} --- (2)where,
a = y - x,
b = z - x and
0 < a < b
To find all Pythagorean Triples, we need to find the all values for a and b such that they are integers and Equation (2) holds. To find values for a and b, first, we will go step by step by finding ranges of each.
From the definition of a, it’s upper and lower limits depends upon b and can be written as
1 ≤ a ≤ b − 1Since b > a and since the lower limit of a is 1 thus lower limit of b is 2. Now we need To find the upper limit of b.
we know 0< z ≤ N, from (b = z − x) ⇒ (x + b ≤ N), thus from Equation (2) and a = b − 1,
(b − a) + sqrt{2b(b − a)} + b ≤ N
⇒ b + 1 + sqrt{2b} ≤ N
⇒ 0 ≤ b ≤ N − sqrt{2N − 1}Since first pythagorean Triple is (3,4,5), which makes N ≥ 5
Let, v = 2b(b − a), since x is a positive integer and 1 < a < b, thus from Equation (2),
2b ≤ v ≤ 2b(b − 1) and
sqrt{v} ∈ N and
v (mod 2b) = 0To find actual values for v, We use prime factorization of 2b,
Where, p_i are k prime numbers, each of order α_i .
Using the prime factors of 2b we can calculate values for v by Equation,
Where, p_j are k prime numbers, each of order ceil{a_j /2} and p_i = p_j and α_i = α_j for all i and j from Equation (3) and Equation (4) respectively. Equaltion (4) can be proved which is not rivial but not hard also.
The Algorithm
Everything has been setup, now we look at the pseudocode of the algorithm:
Above algorithm in python can be written as,
In the above algorithm, the for-loop runs for N-sqrt{2N-1} times, in it, we are calculating the prime factor of 2b and then γ which can be calculated in time O(ln N) See Theorem 2. Since the number of Pythagorean Triplets (x, y, z) with z ≤ N are of order O(N ln N)[1][2], and in while loop we are computing Triples till z ≤ N, each time we iterate, we find a Pythagorean Triplet in order O(1), because we are just doing multiplication to find v because v = (iγ)^2 and from v we are calculating q which is b-a by floor division of v by 2b, having q and v we calculate, Triplets by
x = (b − a) + sqrt{2b(b − a)}
⇒ x = q + √(v) y = x + a
⇒ y = a + √(v) z = x + b
⇒ z = q + √(v) + b
and since operations in the while loop takes O(1) time, so, the while-loop takes O(ln(N)) time, making the whole algorithm take O(N ln N) time and take O(N) space.
Computing SPF Array
For computing the smallest prime factor of each integer less than equal to N we can use the Eratosthenes Sieve Algorithm. This algorithm is not the optimal algorithm but since it does not hurt the runtime complexity of the whole algorithm its good.
There are other algorithms better than the Eratosthenes Sieve Algorithm, but for just as illustration and for sake of simplicity, we will stick with Eratosthenes Sieve Algorithm.
And, the above algorithm can be written in python as:
We can pre-compute the Lowest Prime Factor of each positive integer less than N in linear time[3] and store it in an array say spf, and use spf to compute the prime factors of x by Using Trial dividion method . The Trial division using spf array takes time O(ln x) and spf array itself takes space O(N)[3] (space for storing an integer less than 2N).
Computing Gamma
By slightly changing Trial Division, we can also compute the γ using spf directly, See Algorithm below,
above algorithm can be written in python as,
If we do not want to store Lowest Prime Factors of each integer or in some conditions we have less storage space to work on, we need to calculate the prime factor of 2b from start each time and then calculate γ for that, which can easily be done in O(N^0.5) (See Algorithm below), simply by replacing the “getReducedFactorization” function in final Algorithm with Trial division method and doing some changes, similar to the getReducedFactorization function to compute γ, thus making the final Algorithm take O(N^1.5).
Final Algorithm where all functions are in one python file can be found Here.
If you find any error please let me know so that other readers can get corrected results.
References
[1] Nowak, W. G., & Recknagel, W. ”The distribution of Pythagorean triples and a threedimensional divisor problem”, Math. J. Okayama Univ, 31, 213–220, 1989.
[2] Manuel Benito, Juan L.Varona, ”Pythagorean triangles with legs less than n”, Journal of Computational and Applied Mathematics, Elsevier, 143, 117–126, 2002.
[3] David Gries, Jayadev Misra. ”A Linear Sieve Algorithm for Finding Prime Numbers”, 1978
