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.
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.
759 Solvers
619 Solvers
46 Solvers
Find the index of n in magic(n)
132 Solvers
A Simple Tide Gauge with MATLAB
309 Solvers