Project Euler 251 - Cardano Triplets

Official link:

Note: My solutions runtime is ~1 hour 45 mins so it is way too slow

Thought Process

A fun problem. I had all the math knowledge I needed, but could only solve it the next year with some improved coding skills, however my solution is still extremely slow.

First we simply the problem to a more readable expression

Now we investigate the potential values a, b, c can be

So to recap we know:

On last thing I did was to bound k. If not the code takes way too long. 

Now we have what we need to solve the problem.

I outline the algorithm

Step 2.3 is of special importance.

Instead of finding divisors of t directly we can find prime factors of (a + 1)/3 and (8a - 1)/3 and then get the prime factors of t from there. Once we have the prime factors of t, we can recursively generate the square divisors of t.

I include my code for this section below as it can be a little tricky to implement, take the time to read it carefully and you will see that it's not so hard!

Interactive Code

Input an integer < 1,000,000 (yourinput)

Code will output the number of Cardano triplets (a, b, c) such that a + b + c yourinput