Project Euler 501 - Tangent Circles

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

Thought Process

Lucky for me I had to solve this problem in one of my Mathematics courses at university, so I have already proved Descartes theorem for the special case where one of the circles is a straight line, which is integral for this problem.

With this information already you can solve the problem ~200 seconds for me

  1. you know rA and rB must be square numbers, so you can just loop through all possible rB and then rA less than rB while ensuring that their gcd is 1.

  2. Check if equation (2) is an integer, if it is you have found a candidate rC now you can just add all the multiples of this triplet.

    • The multiples will just be be 1(rA +rB +rC) + 2(rA +rB +rC) + ... + m(rA +rB +rC) can you simplify this and find what m is? Hint

But we can go further and make our algorithm much faster

With this small arrangements of terms we can now make our algorithm from around O(n^1.5) to O(n^0.75), all we need to do now is loop through α and β such that gcd(α, β) = 1 and sum the multiples same as usual

Interactive Code

Enter a number (yourinput)

Code will output S(yourinput)