Problem 1387. Points on a circle.

Created by James

Solve Later

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:

(0, 5) and (0, -5)
(5, 0) and (-5, 0)
(4, 3) and (4, -3)
(-4, 3) and (-4, -3)
(3, 4) and (3, -4)
(-3, 4) and (-3, -4)

Some radii are quite large, so watch out. Good luck!

Solve

Solution Stats

Last solution submitted on Aug 16, 2019

Last 200 Solutions

Problem Comments

3 Comments

3 Comments

Chris Cleveland on 14 Jul 2017

Great problem! Learned a bunch from others solutions as well.

HH on 3 Dec 2017

In the problem statement, I think you meant '3' and '4', rather than '1' and '2', in the respective +/- combinations.

James on 4 Dec 2017

Thanks for catching my stupidity on that one, HH. It's fixed now.

Solution Comments

Solution 441168

1 Comment

1 Comment

J.R.! Menzinger on 10 May 2014

Brute force explodes for really big radius... :'(

Solution 225176

1 Comment

1 Comment

Jean-Marie Sainthillier on 29 Mar 2013

Just to study Tim and James solutions.

Solution 223930

3 Comments

3 Comments

Marco Castelli on 26 Mar 2013

Cases (from 6 to 9) of Test Suite are too long te caltulate: Mathwork's server give a error.

James on 26 Mar 2013

They can be calculated with relative ease without switch/case or if/then commands. There's just a trick on how to do so.

Marco Castelli on 27 Mar 2013

Otherwise part of my solution can calculate every small case but with giant radius give error. I will provide a new solution

Solution 223792

4 Comments

4 Comments

Show 1 older comment

Jean-Marie Sainthillier on 28 Mar 2013

Can you explain your solution ?

Tim on 28 Mar 2013

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).

Jan Orwat on 13 May 2014

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) :-/

James on 27 May 2015

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.

Problem 1387. Points on a circle.

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Recent Solvers15

Suggested Problems

More from this Author80

Tags

Problem 1387. Points on a circle.

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Recent Solvers15

Suggested Problems

More from this Author80

Tags

Players