Project Euler #388

Question

I need some help in fine-tuning my algorithm for Project Euler problem 388. I have concluded that you have to get the gcd of the 3 numbers in the co-ordinate and if the gcd is 1 than that point gives you a distinct line to the origin. This works fine for up to about 10^5 and then it slows down a lot. Can anyone here help me to see how I can reduce the time? Maybe by eliminating a good chunk of co-ordinates or something? I am using Visual Basic in VS2010.

Thanks.

Answer 1

In problem is stated "You are given that D(1 000 000) = 831909254469114121". This could be a hint to search for a recurrence relation.