This problem is related to 1283, Points on a Sphere. In this case, instead of a sphere, you have a circle. Given a radius R, calculate the number of points on the circumference of the circle that have two integer coordinates. For a circle of radius 5, you would have 12 points:
Some radii are quite large, so watch out. Good luck!
Great problem! Learned a bunch from others solutions as well.
In the problem statement, I think you meant '3' and '4', rather than '1' and '2', in the respective +/- combinations.
Thanks for catching my stupidity on that one, HH. It's fixed now.
The tip for this question is the sum of squares function, which I use in my solution. There are many possible solutions to this problem, but the huge circle radii limit what we can employ, so be careful.
Brute force explodes for really big radius... :'(
Just to study Tim and James solutions.
Cases (from 6 to 9) of Test Suite are too long te caltulate: Mathwork's server give a error.
They can be calculated with relative ease without switch/case or if/then commands. There's just a trick on how to do so.
Otherwise part of my solution can calculate every small case but with giant radius give error. I will provide a new solution
Can you explain your solution ?
This is derived from the Mathematica algorithm for sequence A046080 at oeis.org (arrived at from A046109). Instead of factoring (because of the large integers) it checks for divisibility by the various primes (up to 325643, which is enough to handle the test set).
It seems to be around 4 times faster than solution with factoring for this testsuite. But you have to pay with incorrect answer for relatively small radius such as 326441 (prime) :-/
I just came back to this problem for the first time in a long time for help with another problem. I changed the test suite for a few of the solutions that don't work with all of the radii.
801 Solvers
Test if a Number is a Palindrome without using any String Operations
213 Solvers
195 Solvers
1935 Solvers
247 Solvers