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];

:)