Problem 1387. Points on a circle.

Created by James

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>This problem is related to</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"url=http://www.mathworks.com/matlabcentral/cody/problems/1283-points-on-a-sphere>Problem\"><w:r><w:t>1283, Points on a Sphere.</w:t></w:r></w:hyperlink><w:r><w:t> 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:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>(0, 5) and (0, -5)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>(5, 0) and (-5, 0)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>(4, 3) and (4, -3)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>(-4, 3) and (-4, -3)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>(3, 4) and (3, -4)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>(-3, 4) and (-3, -4)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Some radii are quite large, so watch out. Good luck!</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Solve

Solution Stats

86 Solutions
19 Solvers

Last Solution submitted on Apr 14, 2021

Last 200 Solutions

Problem Comments

4 Comments

4 Comments

Show 1 older comment

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.

Rafael S.T. Vieira on 23 Jun 2020

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.

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 Recent Solvers19

Problem Tags

circle circumference integer points

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 1387. Points on a circle.

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers19

Suggested Problems

More from this Author80

Problem Tags

Community Treasure Hunt

Problem 1387. Points on a circle.

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers19

Suggested Problems

More from this Author80

Problem Tags

Community Treasure Hunt

Players