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

 

[CajunCenturion]

I think you can use the slope for that.

For example
slope = [&Delta;]y / [&Delta;]x
do case
case slope = 1
[&Delta;]y = 1 and [&Delta;]x = 1
case slope > 1
[&Delta;]x = 1
case slope < 1
[&Delta;]y = 1
endcase

I think we can use ABS to manage the sign for this.


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

 

[jges]

Excellent observation.

 

[CajunCenturion]

My algorithm yields the current result for L(10) = 30, but I'm a little off for L(100). I'm showing 3593, but should only have 3442. Close, but I have a logic error somewhere.

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

 

[brigmar]

Errors in calculations, or duplicate entries ?

 

[CajunCenturion]

I know that I don't have any duplicate entries and I know that I do not have any lattice points encompassed by a lenticular area. Beyond that, I don't know where the additional 151 area are being generated.

--------------
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]

CC - How fine are you cutting it. Does your lenticular area "touch" more than 2 lattice points? Again, might be a stupid question as it might not be possible to have an area that touches more than 2 (4 in fact) without enclosing and meeting the rest of the requiremetns.

**********************************************
What's most important is that you realise ... There is no spoon.

 

[CajunCenturion]

==> Does your lenticular area "touch" more than 2 lattice points?
No. All areas meet the conditions of |?x| = 1 or |?y| = 1, and since the shape is lenticular, only the two endpoints are in play.

With my current approach, the only real calculations are those to determine the radii of the circles which have integer intersections, and the slope and distance of the line segment between each set of two intersection points. Since we're dealing strictly with integers, except for the radii themselves, it's not necessary to determine any intersections between two circles. Again, what matters is the line segment between two integer intersection points, and I'm defining them in terms of ?x and ?y, or you could just as easily define them in terms of slope and distance. But again, ?x and ?y are integers while slope and distance are not, and integer arithmetic is faster then floating point.

Because of the symmetry of a circle, if you have a segment where ?x = 1 and ?y = 2, you also have three others, (?x = 1, ?y = -2), (?x = -1, ?y = 2), and (?x = -1, ?y = -2). Due to the symmetry and to the distinct requirement of the problem, all we need for each radii is the set of unique (|?x|, |?y|) segments, where depending on the slope of the segment, either |?x| = 1 or |?y| = 1 to ensure that we'll enclose no lattice points.

Given that, and again, since we're dealing strictly with integers, we can move any circle center ([&plusmn;]a, [&plusmn;]b), which allows us to align one circle with every other circle which has the same (|?x|, |?y|) to form a lenticular area.

My logic problem, I believe, has to do with a lenticular area that spans quadrants. I think that's where the extra areas are creeping in, really as duplicates, but not recognized as such. At least that's the current line of investigation.

Nevertheless, I'm going to change the approach because while L(100) takes an average of roughly eight seconds, L(100000) will take double digit hours. Once I've figured out the current bug, I'll attack the calculations to determine the radii of the circles involved. That's what's taking up the bulk of the time.

--------------
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]

The slope is not sufficient, two circles can match and intersect, if they have the same ?x and ?y in the lattice points they go through.

Indeed, the second circle can only be one of the circles we already determined (see jges illustration), of course the chord length are good candidates for a match, so you could sort circles by such chord lengths to find matches, also remember r2>=r1.

Also circles having more than 4 lattice points can be easily determined by being the ones which are constructed by different lattice points in the first place, but having the same radius.

Bye, Olaf.

 

[CajunCenturion]

?x and ?y give you both slope and distance.


--------------
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]

I have discovered the problem. In the very large circles, you can a very long area and even though |?x| = 1 (or ?y) and capture an unwanted lattice point. I'll need to develop a function based to radius and chord length to know which areas to throw out.


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

 

[jges]

To help reduce the problem, we can throw out the circles that have a radius that is a multiple of sqrt(2) (those that pass through a lattice point (k,k)). These circles circumscribe a square. They only have 4 chords (2 horizontal, 2 vertical) and you will not be able to combine them with another circle to create a lenticular hole without including a lattice point.

 

[CajunCenturion]

Yep, those are gone in the first pass.

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

 

[jges]

Circles that pass through point (k,k-1) will also pass through (k-1,k), giving a |?x| = 1 AND |?y| = 1 and therefore will form a lenticular hole with each other (and with a circle of radius 1).

The circle that passes through (6,5) also passes through (5,6) and will form a hole with the circle that passes through (5,4), or (4,3), or (3,2) and the circle with radius 1.

 

[kwbMitel]

jges, accepting what you say to be true. I would only count 1 of those as a "Distinct" solution as the circles involved are the same size and the shape/size of the hole is identical in each case. Although the relative positions appear distinct they are the same when viewed via rotational symmetry.

**********************************************
What's most important is that you realise ... There is no spoon.

 

[jges]

Let me expound on my previous post a bit:

The circle with radius sqrt(61) [when centered on (0,0) passes through points (6,5) and (5,6)] giving a chord that has |?x| = 1 AND |?y| = 1.

The circle with radius sqrt(41) [when centered on (0,0) will pass through points (5,4) and (4,5)] also has a chord with |?x| = 1 AND |?y| = 1.

The circle with radius sqrt(25) [when centered on (0,0) will pass through points (4,3) and (3,4)] also has a chord with |?x| = 1 AND |?y| = 1.

The circle with radius sqrt(13) [when centered on (0,0) will pass through points (3,2) and (2,3)] also has a chord with |?x| = 1 AND |?y| = 1.

The circle with radius 1 has a chord with |?x| = 1 AND |?y| = 1.

These 5 circles can be moved around relative to each other to line up the chords, giving us 10 unique circle pairs that create lenticular holes which contain no lattice points.

 

[CajunCenturion]

For L(10), there are seven circles which have a |?x| = 1 AND |?y| = 1 chord. In addition to the four listed above, there is also the circle with radius 1, SQRT(5), and SQRT(85).

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

 

[jges]

So for L(10), these 7 circles account for 21 of the 30 possible solutions.

 

[kwbMitel]

Oh well then, that being the case, ignore my last. I definitely did not consider them distinct. Ok, rotational symmetry allowed.

**********************************************
What's most important is that you realise ... There is no spoon.

 

[kwbMitel]

As you've probably figured out, so far I'm only just observing and thinking. I believe the math to be beyond my skills but maybe I can discover a shortcut or pattern.

So now that I've discovered that I am/was eliminationg valid options. Can I limit my choices to those found within a 90 degree quadrant of the circle. The others appear to be just mirror images to me.

**********************************************
What's most important is that you realise ... There is no spoon.

 

[jges]

kwbMitel,
I'm not sure we are on the same page. Perhaps this will help:

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

This diagram shows the circle with radius sqrt(85) and its solutions with circles of radius:
sqrt(61)
sqrt(41)
sqrt(25)
sqrt(13)
sqrt(5)
1

The diagram shows 6 solutions. Replace the largest circle with the next largest circle and you get 5 more solutions, next largest circle = 4 more solutions, etc etc.