Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: rational n-gon inscribed in a unit circle
Replies: 59   Last Post: Dec 19, 2013 12:56 AM

 Messages: [ Previous | Next ]
 Richard Tobin Posts: 1,436 Registered: 12/6/04
Re: rational n-gon inscribed in a unit circle
Posted: Dec 13, 2013 6:08 PM

In article <1k2na9p7tn11k8bq0obtfc8ih1binge4gr@4ax.com>,
quasi <quasi@null.set> wrote:

>>Let me know if you want the program.

>Definitely!

Ok, it's at http://www.cogsci.ed.ac.uk/~richard/rational-polygons.c
You'll need a C compiler and Gnu MPFR and GMP libraries.

It works by brute force, enumerating for each successive integer
radius sets of integer sides that produce a polygon. It takes an
argument that is a limit on the number of sides to allow it to
investigate small numbers of sides for a range of radiuses in a
reasonable amount of time. It has an optional "-d" argument to make
all the sides different.

It uses floating point trig functions to determine the angles, so it
(a) has to have a small tolerance to allow for inexact calculation and
(b) produces false positives. I've used double precision (assumed to
be 64 bit) with a generous tolerance, and then check the successful
results with 1000-bit precision using Gnu MPFR. Results that fail the
check have a "?" in front of them; reject them.

Example usage:

rational-polygons -d 4
- quickly find rational quadrilaterals (and triangles) with all
sides different.

rational-polygons 20
- find rational polygons with up to 20 sides; gets slow quickly

Below is output with up to 100 sides for radiuses up to 21. The
16-sided radius 21 case is an example of a false positive rejected
by the multi-precision check; it's off by about 2E-13.

* 6 sides: 1 1 1 1 1 1
* 4 sides: 1 1 1 2
* 2 sides: 2 2
* 6 sides: 2 2 2 2 7 7
* 6 sides: 2 2 4 4 4 7
* 4 sides: 2 2 7 8
* 5 sides: 5 5 5 6 8
* 4 sides: 6 6 8 8
* 3 sides: 6 8 10
* 6 sides: 2 2 2 11 11 11
* 6 sides: 2 2 7 7 11 11
* 6 sides: 2 7 7 7 7 11
* 4 sides: 2 7 11 14
* 4 sides: 2 11 11 13
* 4 sides: 7 7 11 13
* 10 sides: 2 2 2 2 2 2 9 9 9 9
* 8 sides: 2 2 2 2 9 9 9 12
* 8 sides: 2 2 2 4 4 9 9 14
* 8 sides: 2 2 2 8 8 8 9 9
* 6 sides: 2 2 2 9 9 16
* 6 sides: 2 2 9 9 12 12
* 6 sides: 2 4 4 9 12 14
* 6 sides: 2 8 8 8 9 12
* 4 sides: 2 9 12 16
* 4 sides: 4 11 14 14
* 4 sides: 9 12 12 12
* 6 sides: 2 2 12 12 12 12
* 6 sides: 2 3 3 12 12 17
* 6 sides: 2 6 6 12 12 14
* 6 sides: 2 9 9 9 12 12
* 4 sides: 2 12 12 18
* 6 sides: 3 3 3 3 17 17
* 6 sides: 3 3 6 6 14 17
* 6 sides: 3 3 9 9 9 17
* 4 sides: 3 3 17 18
* 6 sides: 6 6 6 6 14 14
* 6 sides: 6 6 9 9 9 14
* 4 sides: 6 6 14 18
* 6 sides: 1 1 1 22 22 22
* 6 sides: 1 1 13 13 22 22
* 5 sides: 1 10 13 22 24
* 6 sides: 1 13 13 13 13 22
* 4 sides: 1 13 22 26
* 4 sides: 1 22 22 23
* 4 sides: 10 10 24 24
* 5 sides: 10 13 13 13 24
* 3 sides: 10 24 26
* 4 sides: 13 13 22 23
* 6 sides: 3 3 14 14 25 25
* 6 sides: 3 14 15 15 15 25
* 5 sides: 3 14 18 24 25
* 4 sides: 3 14 25 30
* 4 sides: 14 19 25 25
* 8 sides: 4 4 4 4 4 18 18 31
* 6 sides: 4 4 4 4 31 31
* 8 sides: 4 4 4 7 18 18 20 20
* 10 sides: 4 4 4 8 8 8 8 17 18 18
* 8 sides: 4 4 4 8 17 18 18 22
* 8 sides: 4 4 4 12 12 18 18 23
* 6 sides: 4 4 4 18 24 31
* 6 sides: 4 4 7 20 20 31
* 8 sides: 4 4 8 8 8 8 17 31
* 6 sides: 4 4 8 8 28 31
* 6 sides: 4 4 8 17 22 31
* 6 sides: 4 4 12 12 23 31
* 6 sides: 4 4 16 16 16 31
* 4 sides: 4 4 31 32
* 6 sides: 4 7 18 20 20 24
* 8 sides: 4 8 8 8 8 17 18 24
* 6 sides: 4 8 17 18 22 24
* 6 sides: 4 12 12 18 23 24
* 4 sides: 4 24 24 31
* 6 sides: 7 7 20 20 20 20
* 8 sides: 7 8 8 8 8 17 20 20
* 6 sides: 7 8 8 20 20 28
* 6 sides: 7 8 17 20 20 22
* 6 sides: 7 12 12 20 20 23
* 6 sides: 7 16 16 16 20 20
* 4 sides: 7 20 20 32
* 10 sides: 8 8 8 8 8 8 8 8 17 17
* 8 sides: 8 8 8 8 8 8 17 28
* 8 sides: 8 8 8 8 8 17 17 22
* 8 sides: 8 8 8 8 12 12 17 23
* 8 sides: 8 8 8 8 16 16 16 17
* 6 sides: 8 8 8 8 17 32
* 6 sides: 8 8 8 17 22 28
* 6 sides: 8 8 12 12 23 28
* 6 sides: 8 8 17 17 22 22
* 6 sides: 8 12 12 17 22 23
* 6 sides: 8 16 16 16 17 22
* 4 sides: 8 17 22 32
* 6 sides: 12 12 12 12 23 23
* 6 sides: 12 12 16 16 16 23
* 4 sides: 12 12 23 32
* 4 sides: 17 22 22 28
* 4 sides: 16 16 30 30
* 5 sides: 16 17 17 17 30
* 3 sides: 16 30 34
* 6 sides: 11 11 11 26 26 26
* 6 sides: 11 11 19 19 26 26
* 6 sides: 11 19 19 19 19 26
* 4 sides: 11 19 26 38
* 4 sides: 11 26 26 37
* 4 sides: 19 19 26 37
* 5 sides: 10 10 24 32 35
? 16 sides: 2 2 3 4 4 4 5 5 6 6 8 8 13 18 18 23
* 6 sides: 6 12 21 22 28 33
* 6 sides: 12 12 22 22 28 28
* 6 sides: 12 21 21 21 22 28
* 4 sides: 12 22 28 42
* 4 sides: 22 28 28 38

-- Richard

Date Subject Author
12/10/13 quasi
12/10/13 ross.finlayson@gmail.com
12/10/13 quasi
12/11/13 quasi
12/11/13 quasi
12/11/13 quasi
12/12/13 quasi
12/12/13 Helmut Richter
12/12/13 quasi
12/11/13 scattered
12/11/13 quasi
12/11/13 fom
12/11/13 fom
12/11/13 quasi
12/11/13 fom
12/11/13 Richard Tobin
12/11/13 Richard Tobin
12/12/13 quasi
12/12/13 Richard Tobin
12/12/13 Richard Tobin
12/12/13 quasi
12/12/13 Brian Q. Hutchings
12/13/13 quasi
12/13/13 Brian Q. Hutchings
12/12/13 Thomas Nordhaus
12/12/13 Richard Tobin
12/12/13 quasi
12/12/13 Richard Tobin
12/12/13 quasi
12/12/13 quasi
12/13/13 Richard Tobin
12/13/13 Richard Tobin
12/13/13 quasi
12/13/13 Richard Tobin
12/13/13 quasi
12/13/13 Richard Tobin
12/13/13 quasi
12/13/13 quasi
12/12/13 Richard Tobin
12/13/13 quasi
12/13/13 Richard Tobin
12/13/13 quasi
12/14/13 quasi
12/14/13 quasi
12/14/13 quasi
12/14/13 quasi
12/14/13 Richard Tobin
12/15/13 quasi
12/15/13 quasi
12/15/13 Richard Tobin
12/15/13 David Bernier
12/15/13 quasi
12/18/13 Richard Tobin
12/18/13 ross.finlayson@gmail.com
12/19/13 quasi
12/14/13 Richard Tobin
12/14/13 quasi
12/14/13 Richard Tobin
12/14/13 ross.finlayson@gmail.com
12/15/13 Brian Q. Hutchings