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

 

[kwbMitel]

I'll see if I can graph the first 30. Your latest diagram helps a bit but I'm looking for chords in excess of length Root 2 between the points. I'll stop bugging you now.

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

 

[jges]

I'm looking for chords in excess of length Root 2 between the points

My next goal as well!

 

[kwbMitel]

You mean I actually said something meaningful? Intelligible?
Cool!

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

 

[Olaf Doschke]

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

Yes, but the slope is only ?y/?x and this is not sufficient to match two circles, they need the exact same tuple of (?x, ?y) like you later wrote.

Bye, Olaf.

 

[kwbMitel]

jgres (et al) - I obviously did not understand your description before. So here is my clarification question. With the 2 circles R1=Root65 and R2=5 there are 2 places that the lenticular hole can be positioned in a single quadrant.

R1=root65 circle center on 0,0

R2=5 circles can be either at 12,4 or 4,12.

I do not consider these "Distinct" and would only count 1.

Is this correct?

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

 

[kwbMitel]

Ignore that, I've finally got my count of 30 and the answer is now self explained. (Count only 1)

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

 

[kwbMitel]

And just like that I have a good start on the L(100)

There are 71 circles that can form lenticular holes with the 1X1 circle each of which fit within one another. This adds up to 2556 holes(Chord Length = root2). Now for the Chord lengths > root2, but that is for another day.

For the Chord length = root2 holes for L(100,000) there are 70711 circles and 2,500,058,116 holes.

Please let me know if my statements above are wrong.

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

 

[Olaf Doschke]

I'm at a point with my program, where L(10) results in 32 and L(100) in 3599.

Both despite the fact I apply the criterion that either |?x| = 1 or |?y| = 1. I think that is even too strict. And I also account for holes, that span more than 90 degrees ans eg rather would span almost through the middle of a circle than at it's edge.

To ensure that I also limit ?x[sup]2[/sup]+?y[sup]2[/sup] <= 2r[sup]2[/sup] within both circles. Still the same results.

Bye, Olaf.

 

[Olaf Doschke]

Ah, I see. Drawing the circles with chords helps seeing the condition is not sufficient. Of course the larger circles get, the shorter the chords have to be.

And it's sufficient to examine half the lenticular holes of course, if half the hole contains a lattice point that chord is out for matching with other circles.

I still lack a way of checking the condition of no lattice point within the lenticualar hole.

Bye, Olaf.

 

[kwbMitel]

I think I have a good start on L(100) and have identified 144 circles that meet the requirements. If I'm right, this might be easier than I thought.

For L(10) I've found 8 Circles and they combine as follows:

[tt]
Radius Root1 root5 Root13 Root25 Root41 Root61 Root65 Root85
Root1 x
root5 x x
Root13 x x x
Root25 x x x x
Root41 x x x x x
Root61 x x x x x x
Root65 x x
Root85 x x x x x x x[/tt]

I'm not using math for this (well not much anyway, just pattern seeking.

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

 

[kwbMitel]

I've got to walk away for a time. Head spinning. With my 144 circles I get a count of 3430 (14 short)

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

 

[kwbMitel]

Actually 12 short.

I'll post my method later and maybe someone else can find them.

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

 

[Olaf Doschke]

Got it. Still not for N=100000, a table of circles I create and insert into get's too large.

L(10)=30
L(100)=3442
L(1000)=393451

I solved the detection of lattice points detection inside lenticular holes by checking lattice points near the chord, if their x[sup]2[/sup]+y[sup]2[/sup] < r[sup]2[/sup].

There are (|?x|, |?y|) with |?x|>1 and |?y|>1, eg for N=100 pairs like (3,7) (for r[sup]2[/sup] in 5249,6409,7685,9077 among others) and (5,7) (for r[sup]2[/sup] in 6697,8177 and 9805) so the condition |?x|=1 or |?y|=1 is eliminating solutions.

Bye, Olaf

 

[kwbMitel]

Ok here's my theory and how I'm applying it. My issue will be communicating it, my confidence level in the method is high.

For L(100)
- I focus on Chord Lengths.
- Chord limits 1 lattice point horizontal and 1,3,5,7,9,11, and 13 lattice points vertical.
- This defines 7 chord lengths
root2, root10, root26, root50, root82, root122, root170

root2 Chord circles = 71 Combine 2556 times
root10 Chord circles = 31 Combine 496 times
root26 Chord circles = 18 Combine 171 times
root50 Chord circles = 11 Combine 66 times
root82 Chord circles = 7 Combine 28 times
root122 Chord circles = 4 Combine 10 times
root170 Chord circles = 2 Combine 3 times

Some circles apply to 2 categories such as the R=5 circle. It can also combine with the root10 Chords >= R=5

Root2 R=root25 combines with 31 Root10's
Root2 R=Root1105 combines with 22 root10's
Root2 R=Root1105 combines with 14 root26's
Root2 R=Root3445 combines with 9 root26's
Root2 R=Root7565 combines with 5 root10's
Root2 R=Root8845 combines with 1 root122
Root10 R=Root1105 combines with 14 root26's
Root10 R=Root5525 combines with 4 root50's

This accounts for 100 more combinations.

3430 total.

So, if I've presented that in a coherent way. Maybe you can help me to find the lost 12.

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

 

[Olaf Doschke]

kwbMitel,

if I compute the chord lengths, aditional to you I get 13 circels with root34, 7 with root58 and 3 with root74 and 1 with root106.

That should help you already.

Bye, Olaf.

 

[kwbMitel]

Yes thanks, I'll try and see how I missed those and fit them in.

The additional 100 I was counting earlier a red herring. I was simple counting things twice.

You additions may give me the 112 more I need

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

 

[kwbMitel]

Olaf, I feel you have already eliminated some circles by some process. I'm assuming the additional chord lengths you've provided do not combine as efficiently as my previous due to the proximity of lattice points.

In total quantities I get

Root34 chords = 16 Circles
Root58 chords = 12 Circles
Root74 chords = 11 Circles
Root106 chords = 9 circles

It seems obvious that not all will combine with each other. Need to start graphing again to determine a formula.

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

 

[kwbMitel]

Got it , Sort of
Root34 Chords minimum R=Root697 = 13 Circles
Root58 Chords Minimum R=Root2465 = 7 Circles
Root74 Chords Minimum R=Root6697 = 3 Circles
Root106 Chords Minimum R=Root9593 = 1 Circles

Unfortunately, these would add 126 Combinations not 112 like I needed.

Now I'm 14 over.

Help?

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

 

[kwbMitel]

Re:L(100)
Correction found 10 where I was counting combinations twice
I'm now 4 over.
159 Distinct Circles, so close now...

Has anyone yet got the 3442 number for L(100)?

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

 

[kwbMitel]

There were actually 14 duplicate circles in separate categories. Something went wrong with my formula for comparison. Manually looking found 14. It was the only thing that made sense.

I now match 3442 using my Chord method.

L(100,000) intimidates me after how long it took me to get L(100)

Here is what I need to tackle that one.

- Method to Identify valid chord lengths
* Might already have this as it appears that the end points just need to be odd integer lengths separation on the x,y coordinates

- Method to identify minimum circle radius where chord of given length is present. My method so far is manual

- Method to Identify minimum circle radius for given Chord Lengths that can combine without enclosing a lattice point.

- Method to look for duplicate circles (fairly easy relatively speaking.

Any takers on some formula's to help me?

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