Project Euler 540 - Counting Primitive Pythagorean Triples

Official link: https://projecteuler.net/problem=540

Note: My code takes ~500 seconds to run, ~15s with pypy

Thought Process

Another great problem!

First I tired optimizing my Pythagorean Triples function, with that I could get P(10^8) relatively fast, but it was no where near good enough but it allowed me to find https://oeis.org/A101931 which showed a limit as n goes to infinity

So we already know roughly what our answer will be. After further research I found a paper Pythagorean triangles with legs less than n which was very similar to the problem and could be adapted easily.

After reading and understanding the paper, I just turned the math in the paper into an algorithm which is always incredibly fun for me!

I recommend reading the paper and figuring it out yourself, I give my working below where I rename some functions to make it very easy to make an algorithm.

Please read the article for the proof, it's quite easy to follow.

Now the algorithm is clear.

We just brute force R(n) and we need a good mobius sieve which I have already done before, and the problem is done!

Interactive Code

Enter an Integer (yourinput)

Code will output P(yourinput)