# Project Euler #39: Integer right triangles

# Project Euler #39: Integer right triangles

+ 3 comments This is the algorithm I used:

Generate all Pythagorean triplets(pt) by Euclid's method. a = m*m-n*n; b = 2*m*n; c = m*m+n*n; for all m>n>0 and m and n are integers. For primitive pt gcd(m,n)==1 and one of m or n should be even.

thus the sum of a+b+c = p will be 2*m*(m+n); Since perimeter is only 5*10^6 then iterate m till 1200.

To generate all non primitive pt just multiply by k(>0) every value of a, b, c. Thus perimeter of all non primitive pt will be k*2*m*(m+n).

now the algorithm:

for(m = 2 to 1200) // including 1200 for(n = 1 to m) // excluding m if (m+n)%2!=0 and gcd(m,n)==1 perimeter = 2*m*(m+n) for(k=1 to infinity) if k*p > 5000000 then break; else freq[k*p]++;

Here freq[p] has count of all values of pt whose perimeter is p.

now make another array which stores the largest number less than n whose number of pt's is max.

simply the condition will be:

if(freq[i]>freq[b[i-1]]) b[i] = i; else b[i] = b[i-1];

now for every input n output b[n];

:)

+ 2 comments First of all hi everybody. My question might sound stupid, but if i have successfully solved a contest problem is there any way to see the solutions of other competitors for that problem? I ask because for the domain problems this i know how to do, but here i don't see any option to view a competitors solution. I would like to see this for this problem because even though i solved the problem, i did so very, very ugly and i am looking for a nicer and more enlightening solution. Thanks in advance :D

+ 0 comments public class Solution { static int[] getIntegerRightTriangles() { int[] freq = new int[5_000_001]; for (int m = 2; m <= 1200; m++) { for (int n = 1; n < m; n++) { if ((m + n) % 2 == 0 || gcd(m, n) != 1) continue; int p = 2 * m * (m + n); int k = 1; while (k * p <= 5_000_000) { freq[k * p]++; k++; } } } int[] res = new int[freq.length]; for (int i = 1; i < freq.length; i++) res[i] = freq[i] > freq[res[i - 1]] ? i : res[i - 1]; return res; } private static int gcd(int m, int n) { while (true) { if (n == 0) return m; int tmp = m; m = n; n = tmp % n; } } public static void main(String[] args) { int[] res = getIntegerRightTriangles(); Scanner scan = new Scanner(System.in); int T = scan.nextInt(); for (int i = 0; i < T; i++) { int N = scan.nextInt(); System.out.println(res[N]); } } }

+ 0 comments How it can be proven that Euclid's formula for a Pythagorean triple gives us unique a,b and c for each unique m and n ?

I mean that there may exist two different set of (m,n) which give the same a and b and c . If so, we will count a Pythagorean triple more than once.

+ 0 comments Find my java solution here. But 2/7 test cases passed:(

Sort 12 Discussions, By:

Please Login in order to post a comment