Lenticular Circles

[CajunCenturion]

Problem link:

http://projecteuler.net/index.php?section=problems&id=295

Circle one is centered on (0, 0) with radius r[sub]1[/sub]
Circle two is centered on (x[sub]2[/sub], y[sub]2[/sub]) with radius r[sub]2[/sub]
The equations of our two circles are:
x[sup]2[/sup] + y[sup]2[/sup] = r[sub]1[/sub][sup]2[/sup]
(x - x[sub]2[/sub])[sup]2[/sup] + (y - y[sub]2[/sub])[sup]2[/sup] = r[sub]2[/sub][sup]2[/sup]

The distance between (x[sub]1[/sub], y[sub]1[/sub]) and (x[sub]2[/sub], y[sub]2[/sub]) is
D = SQR( (x[sub]2[/sub] - x[sub]1[/sub])[sup]2[/sup] + (y[sub]2[/sub] - y[sub]1[/sub])[sup]2[/sup] )
There are no solutions if
[li]D = 0 - the circles are coincident[/li]
[li]D > r[sub]1[/sub] + r[sub]2[/sub] - the circles do not intersect.[/li]
[li]D < ABS( r[sub]1[/sub] + r[sub]2[/sub]) - one circle is inside of the other and they do not intersect.[/li]

Next step is to find the two intersection of the two circles. We have the two circle equations and two unknowns, and this is going to get messy, but we can solve them simultaneously and we'll get out two intersection points
(x[sub]3[/sub], y[sub]3[/sub])
(x[sub]4[/sub], y[sub]4[/sub])

Once we have those two pairs, we know that either
ABS(x[sub]3[/sub] - x[sub]4[/sub]) = 1
or
ABS(y[sub]3[/sub] - y[sub]4[/sub]) = 1

And of course, all point coordinates are integers.
It's a start.




--------------
Good Luck
To get the most from your Tek-Tips experience, please read
FAQ181-2886
As a circle of light increases so does the circumference of darkness around it. - Albert Einstein

 

[Thargy]

cc,

I'm trying to deduce the algorithm by working on L(10) to start with.

Right now, I'm thinking that my original assertion about integer points can be used to reduce the number of combinations.

For example the biggest circle is radius 10,
0[sup]2[/sup]+10[sup]2[/sup]= 100
6[sup]2[/sup]+8[sup]2[/sup]= 100

This means that the digit zero has a highly restricted use, in that it can only be used for circles whose radius is also an integer. That means that there are only ever 10 possibilities using zero. So my original calculation of 11x10x9x9 was wrong, the maximum is (10x9x8) + 10 = 730 possible circles.

Regards

T

 

[Thargy]

cc,

I'm trying to deduce the algorithm by working on L(10) to start with.

Right now, I'm thinking that my original assertion about integer points can be used to reduce the number of combinations.

For example the biggest circle is radius 10,
0[sup]2[/sup]+10[sup]2[/sup]= 100
6[sup]2[/sup]+8[sup]2[/sup]= 100

This means that the digit zero has a highly restricted use, in that it can only be used for circles whose radius is also an integer. That means that there are only ever 10 possibilities using zero. So my original calculation of 11x10x9x9 was wrong, the maximum is (10x9x8x7) + zero as a factor circles.

The only such circles are radius
10 (10,0) and (8,6)
9 -- no factors
8 -- no factors
7 -- no factors
6 -- no factors
5 (5,0) and (3,4)
4 -- no factors
3 -- no factors
2 -- no factors
1 -- no factors.

Still thinking.

Regards

T

 

[CajunCenturion]

I don't think the zero radius circle works because in order for two circles to form a lenticular region, they must intersect at exactly two points. The circle radius circle wouldn't meet that criteria, so I think we can disregard zero as one of the circle radii.

I agree that being able to take advantage of the integer restrictions will substantially reduce the solution space, which we do want to do.

If I understand the problem, it states that
Let L(N) be the number of distinct lenticular pairs (r[sub]1[/sub], r[sub]2[/sub]) for which 0 < r[sub]1[/sub] ? r[sub]1[/sub] ? N.
We can verify that L(10) = 30 and L(100) = 3442.

I interpret that (L(10) = 30) to mean there are 30 lenticular pairs where the two circles have radii of less of then ten. Whereas the pairs are integers, the radii of the circles are not. The radius of SQR(65) is certainly not an integer, even though it forms a lenticular pair with radius five.

--------------
Good Luck
To get the most from your Tek-Tips experience, please read
FAQ181-2886
As a circle of light increases so does the circumference of darkness around it. - Albert Einstein

 

[kwbMitel]

I'm following this thread an an observer and as such I have a couple of observations. These might be redundant and already considered in your calculations but....

1) - I'm curious as to why the word distinct is bolded. This leads me to believe there are equivelent pairs that need to be elimiminated.

2) - I am not seeing you guys considering the aspect of the lenticular hole whereby the enclosed area does not contain any lattice points. This may be another source of potential eliminations.

 

[CajunCenturion]

==> [/i]I'm curious as to why the word distinct is bolded.[/i]
There are an infinite number of lenticular holes created by a circle of radius five and a circle of radius [&radic;]65. Think about rotating one circle around the other keeping the distance between the centers constant. Within that, there is a finite subset where the boundaries of the hole are integers. But we're only counting one of them because we're only dealing with one pair of radii, i.e. (5, [&radic;]65)

-----

Realizing that the radii are not integers, in fact, may actually be irrational, we cannot attack the problem from the point of the radii. We have to find points first, and then determine the circle radii.

--------------
Good Luck
To get the most from your Tek-Tips experience, please read
FAQ181-2886
As a circle of light increases so does the circumference of darkness around it. - Albert Einstein

 

[CajunCenturion]

Oops, not an infinite number of holes because the circle centers have to be integers as well. But I still think that's the call for distinct, so that you're not counting the number of lenticular holes, but counting the number of distinct radii pair that generate those holes, given that one pair of radii can generate more than one set of lenticular holes.

--------------
Good Luck
To get the most from your Tek-Tips experience, please read
FAQ181-2886
As a circle of light increases so does the circumference of darkness around it. - Albert Einstein

 

[Olaf Doschke]

I haven't read through all your ideas, but I thought along other lines as far as I oversee your thoughts.

I though especially about the lattice points and how the three conditions can be met:

* The centres of both circles are on lattice points.
* The two circles intersect at two distinct lattice points.
* The interior of the convex area enclosed by both circles does not contain any lattice points.

First of all one circle can always be positioned at (0,0). then the intersection points of the two circles must be on lattice points, which can be done by constructing the circels that way. Third the radii must be somewhat equal, but it's hard to put that mathematical. If the lenticular holes can't get too "bellied", so the convex area does not contain any lattice point.

I'd start with a single circle and see what circles can be constructed at all with the given limitation of 0<=r1<=r2<=N.

Let the circle on the origin be the smaller one always, then nevertheless it's radius can go from 0 to 10 and that limits the number of lattice points that inner circle can go through to all the lattice points inside a circle with radis 10.

Also you can easily construct a circle going through any of these lattice points by defining the circle via a lattice point (n,m), which gives a circle of radius r1^2=n^2+m^2.

Due to the symmetry that circle will at least go through mirrored lattice points and that's where you can construct lenticualar holes. via a line between two such points on the first circle.

The second circle needs to have it's center at an intersection point (i,j) of the axis perpendicular to that lenticular hole axis to go through the same intersection point as the first circle, and the condition about the hole not being too "bellied" then limits the possible points (i,j), also the condition r2>=r1 and r2<=N of course do limit the possible secondary circles for each first circle.

Bye, Olaf.

 

[kwbMitel]

Another observation. Maybe valid, maybe not. It occurs to me that the circumference of the circle must pass thru at least 2 lattice points. At these points, the radii may not be integers but the 2 sides of the right triangle formed with the radius as the hypotenuse to each of the lattice points must be integers and that both triangles thus formed would be equivelent. Not sure if this helps (or is even entirely correct).

There is also a right triangle formed with integer sides using the circle centers as endpoints for the hypotenuse. This Hypotenuse would bisect the 2 lattice points refered to above. Again, unsure if this is useful.

 

[jges]

Since the center must be at a lattice point and the circumference must pass through lattice points, there is a finite number of circles to consider. For the case of N=10, there are 43 possible circles you can use.

http://www.box.net/files/0/f/23930418#/files/0/f/23930418/1/f_498548246

 

[brigmar]

It helps.
The radii must be the sum of two squared integers (including zero).
There must be a minimum of 2 integer intersections in 90 degrees of the circle.
There must be a difference of 1 in the x or y axis (doesn't matter, they are paired), otherwise there would be a lattice point in the intersection.

radius of 1 = (0,1) and (1,0). Works because 1 and 0
radius of 5 = (5,0),(4,3),(3,4), and (0,5). Works because of 5 and 4
radius of root 65 = (8,1),(7,4),(4,7), and (1,8). Works because of 8 and 7

 

[brigmar]

Fix for that last post.
The SQUARE OF THE radii must be the sum of two squared integers (including zero).

 

[brigmar]

I'm disappearing down a rabbithole. Don't mind me.

 

[brigmar]

Basically, what I'm trying to get at is that I believe the answer is less to do with circles and more to do with pythagorean triangles.

 

[Olaf Doschke]

jges, unfortunately I get to a login page only when following your link. 43 is a good count for N=10. I get the same result.

As the circle can be assumed at origin (0,0) a second point (n,m) defines a circle and due to symmetry we can limit (n,m) to be n>=m>=0. with n^2+m^2<=N^2, excluding n=m=0 of course.

Several points (n,m) result in the same radius, eg (8,6) and (10,0) are both on the circle with radius 10. There are 43 distinct circles for N=10, but only 30 of them form a lenticualar hole with a secondary circle. It may be even less, if some of them can be combined with more than one second circle.

One thing you don't need to care for, though: That a circle goes through at least two lattice points. Due to symmetry it goes through at least 4 lattice points if it goes through one, which defines it, eg eve a circle with radius 1 has 4 lattice points it intersects and can be combied with another circle at (1,1) with radius 1 for example.

Next step to me would be to create the one side of the lenticualar hole by finding two intersection lattice points and creating the lenticualar hole axis with them, which is the base for finding one or more centers of a secondary circle.

Bye, Olaf.

 

[jges]

jges, unfortunately I get to a login page only when following your link

whoops, I forgot to mark it as public. Try this link, I think it will work.

http://www.box.net/shared/cd3lqme7tr

 

[Olaf Doschke]

jges,

thank you, looks good.

There must be a difference of 1 in the x or y axis (doesn't matter, they are paired), otherwise there would be a lattice point in the intersection.

I thought so myself, but there is a contradicting example. take a line from eg (2,0) to (0,5) - a line from the one to the other points don't crosses a lattice point itself, thus you can expand from this to a convex area also not including any lattice point.

In fact, if the axis formed by the two end points of a lenticular hole does not cross any lattice point there can be a lenticular hole not including a lattice point too, it just needs to be slim enough, that's a good criterion I think.

For example a circle with radius 2 crosses (0,2) and (2,0). Taking these points as the axis of a lenticular hole, the hole includes point (1,1) on the axis and therefore this circle with radius 2 has no solution.

Bye, Olaf.

 

[brigmar]

You're right. Once the circles become large enough, there's the possibility of extremely thin lenses not containing lattice points.
As you added, the mid-line of the lens cannot pass through a lattice point.
Therefore dX and dY of the lens endpoints must be coprime; If there is a common denominator greater than 1 between them, the line passes through a lattice point.

 

[Olaf Doschke]

On the other side you can think of big intersections of circles, where there are lattice points within the intersection not being on the axis of the intersection.

So my condition is obviously valid, but not a necessary and whats worse, I fear it's not a sufficient condition for no lattice points within the intersection. But your condition is too strong and may exclude solutions.

I wonder if there is a rule like, if the area of the intersection is larger than 1, it will include one lattice point. I faintly remember something like that would be true for such a geometric form as a convex lense, even if the arcs are not symmetrical. Could that hold true?

Bye, Olaf.

 

[jges]

When we determine the lattice points that a circle passes through, we can calculate chord lengths between those lattice points. If 2 circles of different radius have a chord of the same length, they are a candidate for a lenticular pair.

For example: a circle of radius 5 has chords that pass through lattice points:
(4,-3)(4,3) length: 6 [this chord does not contain lattice points, but it would if paired with another circle]
(5,0)(4,3) length: 3.16227766016840
(5,0)(3,4) length: 4.47213595499960
(4,3)(3,4) length: 1.41421356237310
(3,4)(0,5) length: 3.16227766016840
(5,0)(0,5) length: 7.07106781186550 (disqualified because it contains lattice points)
etc

for the circle of radius sqrt(65):
(8,-1)(8,1) length: 2
(8,1)(7,4) length: 3.16227766016840
(7,4)(4,7) length: 4.24264068711930
(4,7)(1,8) length: 3.16227766016840
etc

We can see these 2 circles have a chord length in common (3.16...). It remains to be determined that they don't create a hole that would contain lattice points (we know they don't since these are from the example).