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

 

[jges]

I'm sure that I'm missing some chord lengths. I found an error with my calculation of when to stop and it was stopping early. I'll try it again today and see how many families I get this time.

 

[jges]

For Y offset of 3, the largest X I get is 95. For X = 101, the minimum radius that would contain no lattice points goes to somewhere around 115000.

But I wasn't getting all the way to a Y offset of 133, so I know I missed some.

 

[kwbMitel]

Jgres - You are correct. For Y = 3 the largest X is 95. I misread my spreadsheet. X=101 is there, but with zero circles. The exact minimum circle size for 101 is Root(13280560505)

Considering we agree on this, here is some more information to compare. These totals DO NOT factor in duplicate circles. Those are removed later.

My totals for all chords with Y=3
[tt]
X Minimum Radius Total Circles Total Holes
5 Root(697) 17146 147001231
7 Root(2465) 13125 86139375
11 Root(31265) 8756 38338146
13 Root(67729) 7476 27949026
17 Root(354769) 5759 16585920
19 Root(606985) 5159 13310220
23 Root(2034985) 4250 9033375
25 Root(3062537) 3903 7618656
29 Root(7915625) 3334 5559445
31 Root(11002225) 3105 4822065
35 Root(24014257) 2708 3667986
37 Root(31628545) 2543 3234696
41 Root(61330945) 2243 2516646
43 Root(77702489) 2116 2239786
47 Root(138071609) 1874 1756875
49 Root(169882105) 1772 1570878
53 Root(282286105) 1568 1230096
55 Root(339475777) 1481 1097421
59 Root(534921025) 1302 848253
61 Root(631610225) 1226 752151
65 Root(953287217) 1063 565516
67 Root(1108813225) 995 495510
71 Root(1614942025) 842 354903
73 Root(1855011049) 780 304590
77 Root(2621986249) 634 201295
79 Root(2979940625) 575 165600
83 Root(4105775825) 433 93961
85 Root(4623976417) 377 71253
89 Root(6232048225) 237 28203
91 Root(6963372025) 182 16653
95 Root(9206463577) 43 946
97 Root(10215916505) 0 0[/tt]

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

 

[jges]

I agree with those.
I'll go next. I'll not list #holes since those are easy to calculate if we are not considering duplicates yet.

My totals for all chords with Y=5

X Minimum Radius Total Circles
7 Root(6697) 11616
9 Root(9593) 9704
11 Root(19345) 8265
13 Root(107185) 7157
17 Root(465505) 5605
19 Root(407809) 5058
21 Root(620945) 4596
23 Root(2450065) 4183
27 Root(6312865) 3551
29 Root(4427425) 3327
31 Root(5922409) 3108
33 Root(19854265) 2863
37 Root(39579145) 2510
39 Root(24739865) 2417
41 Root(30862393) 2287
43 Root(94450537) 2086
47 Root(162256537) 1847
49 Root(94629769) 1833
51 Root(113066369) 1744
53 Root(326648257) 1539
57 Root(509534257) 1354
59 Root(283777393) 1405
61 Root(283777393) 1338
63 Root(914476225) 1104
67 Root(1333401745) 945
69 Root(718649009) 1058
71 Root(816651865) 1004
73 Root(2203291465) 726
77 Root(3056619865) 580
79 Root(1607495305) 757
81 Root(1798020809) 710
83 Root(4745856025) 375
87 Root(6337060105) 235
89 Root(3269957785) 481
91 Root(3612615793) 438
93 Root(9372781777) 35

 

[jges]

I tallied my Chord Lengths and it is much higher than yours.

1302

I made some changes and reran my code. Now I get 1304 different chord lengths, but I agree with 133 being the largest offset yielding 2 chord lengths and 12 circles.

 

[kwbMitel]

Interesting - So we appear to be generating very close to the same data.

My 1302 number may not be entirely accurate. I'll double check. (About 4 hours after this posting)

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

 

[kwbMitel]

My recount of my chord lengths is 1304. Used different method that was much more reliable. The interesting thing is that I have 2 more chord lengths than you on the Y=5

For the ones you listed we match exactly but I also have these.[tt]
X Minimum Radius Total Circles
99 Root(6171283169) 217
101 Root(6750760369) 177[/tt]

To speed things up I'm going to see if we can isolate our differences. Let's try this method. How many of these do you agree with?[tt]

Y Chord Highest Total Circles
Offset Lengths X for group
1 224 447 312060
3 31 95 97007
5 38 101 98235
7 42 113 92042
9 33 125 64940
11 44 133 78346
13 43 131 72207
15 25 121 40029
17 42 137 61449
19 43 153 56625
21 25 127 33070
23 41 139 48007
25 34 151 37712
27 30 163 29085
29 38 175 37525
31 36 139 34740
33 23 133 20900
35 25 141 21732
37 34 149 26128
39 22 157 16585
41 33 165 21506
43 30 173 19813
45 19 181 11075
47 24 189 15162
49 23 197 11883[/tt]

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

 

[jges]

I have 2 more chord lengths than you on the Y=5

I agree with your count, I accidentally used my old list of data when I posted.

When I get my data summarized, I'll double check with your latest post.

 

[jges]

Here's my data:

Chord dX:  1 Chord dY: 1 to 447 (224 chord lengths)		312060
Chord dX:  3	Chord dY: 5 to 95 (31 chord lengths)		97007
Chord dX:  5	Chord dY: 7 to 101 (38 chord lengths)		98235
Chord dX:  7	Chord dY: 9 to 113 (42 chord lengths)		92042
Chord dX:  9	Chord dY: 11 to 125 (33 chord lengths)		64940
Chord dX: 11	Chord dY: 13 to 133 (44 chord lengths)		78346
Chord dX: 13	Chord dY: 15 to 131 (43 chord lengths)		72207
Chord dX: 15	Chord dY: 17 to 121 (25 chord lengths)		40029
Chord dX: 17	Chord dY: 19 to 137 (42 chord lengths)		61449
Chord dX: 19	Chord dY: 21 to 153 (43 chord lengths)		56625
Chord dX: 21	Chord dY: 23 to 127 (25 chord lengths)		33070
Chord dX: 23	Chord dY: 25 to 139 (41 chord lengths)		48007
Chord dX: 25	Chord dY: 27 to 151 (34 chord lengths)		37712
Chord dX: 27	Chord dY: 29 to 163 (30 chord lengths)		29085
Chord dX: 29	Chord dY: 31 to 175 (38 chord lengths)		37525
Chord dX: 31	Chord dY: 33 to 139 (36 chord lengths)		34740
Chord dX: 33	Chord dY: 35 to 133 (23 chord lengths)		20900
Chord dX: 35	Chord dY: 37 to 141 (25 chord lengths)		21732
Chord dX: 37	Chord dY: 39 to 149 (34 chord lengths)		26128
Chord dX: 39	Chord dY: 41 to 157 (22 chord lengths)		16585
Chord dX: 41	Chord dY: 43 to 165 (33 chord lengths)		21506
Chord dX: 43	Chord dY: 45 to 173 (30 chord lengths)		19813
Chord dX: 45	Chord dY: 47 to 181 (19 chord lengths)		11075
Chord dX: 47	Chord dY: 49 to 189 (24 chord lengths)		15162
Chord dX: 49	Chord dY: 51 to 197 (23 chord lengths)		11883
Chord dX: 51	Chord dY: 53 to 205 (18 chord lengths)		9074
Chord dX: 53	Chord dY: 55 to 213 (25 chord lengths)		11169
Chord dX: 55	Chord dY: 57 to 147 (17 chord lengths)		7646
Chord dX: 57	Chord dY: 59 to 143 (13 chord lengths)		6065
Chord dX: 59	Chord dY: 61 to 147 (17 chord lengths)		7345
Chord dX: 61	Chord dY: 63 to 153 (17 chord lengths)		6535
Chord dX: 63	Chord dY: 65 to 157 (10 chord lengths)		3927
Chord dX: 65	Chord dY: 69 to 163 (11 chord lengths)		4605
Chord dX: 67	Chord dY: 71 to 167 (10 chord lengths)		3410
Chord dX: 69	Chord dY: 73 to 173 (9 chord lengths)		2977
Chord dX: 71	Chord dY: 77 to 177 (11 chord lengths)		4451
Chord dX: 73	Chord dY: 79 to 147 (9 chord lengths)		3381
Chord dX: 75	Chord dY: 103 to 151 (6 chord lengths)		1460
Chord dX: 77	Chord dY: 103 to 155 (6 chord lengths)		1829
Chord dX: 79	Chord dY: 87 to 159 (8 chord lengths)		2682
Chord dX: 81	Chord dY: 89 to 163 (7 chord lengths)		2048
Chord dX: 83	Chord dY: 95 to 167 (6 chord lengths)		1872
Chord dX: 85	Chord dY: 97 to 171 (6 chord lengths)		1737
Chord dX: 87	Chord dY: 109 to 175 (4 chord lengths)		1248
Chord dX: 89	Chord dY: 107 to 179 (6 chord lengths)		1696
Chord dX: 91	Chord dY: 109 to 183 (5 chord lengths)		1326
Chord dX: 93	Chord dY: 139 to 187 (3 chord lengths)		805
Chord dX: 95	Chord dY: 111 to 191 (6 chord lengths)		1241
Chord dX: 97	Chord dY: 113 to 195 (6 chord lengths)		1132
Chord dX: 99	Chord dY: 119 to 199 (4 chord lengths)		729
Chord dX: 101	Chord dY: 121 to 203 (5 chord lengths)		848
Chord dX: 103	Chord dY: 129 to 207 (5 chord lengths)		832
Chord dX: 105	Chord dY: 131 to 211 (4 chord lengths)		606
Chord dX: 107	Chord dY: 143 to 215 (4 chord lengths)		607
Chord dX: 109	Chord dY: 145 to 219 (4 chord lengths)		554
Chord dX: 111	Chord dY: 139 to 223 (4 chord lengths)		412
Chord dX: 113	Chord dY: 151 to 227 (4 chord lengths)		434
Chord dX: 115	Chord dY: 153 to 231 (4 chord lengths)		377
Chord dX: 117	Chord dY: 175 to 235 (3 chord lengths)		287
Chord dX: 119	Chord dY: 159 to 239 (4 chord lengths)		266
Chord dX: 121	Chord dY: 161 to 243 (4 chord lengths)		218
Chord dX: 123	Chord dY: 185 to 247 (3 chord lengths)		173
Chord dX: 125	Chord dY: 187 to 251 (3 chord lengths)		142
Chord dX: 127	Chord dY: 191 to 255 (3 chord lengths)		103
Chord dX: 129	Chord dY: 193 to 259 (3 chord lengths)		73
Chord dX: 131	Chord dY: 197 to 263 (3 chord lengths)		35
Chord dX: 133	Chord dY: 265 to 267 (2 chord lengths)		12

 

[kwbMitel]

Amazing!!!! Line for line value for value - Perfect match.

Some might say that it is obvious that this would be so if we are both doing this correctly, but I say unconditionally, AMAZING!.

So total Circles = 1454232

I get total holes of 4582451728 before duplicate checking

I find 279433 Duplicate circles

Final answer 4582172295 But unfortunately the wrong answer.

What do you get now that you've tweaked your algorithm?

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

 

[jges]

What do you get now that you've tweaked your algorithm?

I kicked it off on my work computer Friday evening (it has more resources than this one). I'll have either an answer or an error on Monday morning.

 

[kwbMitel]

Considering that your method and mine appear to be identical (mathematically speaking at least) I'll give you a method to determine how to calculate the nearest lattice point to the chord quickly and (somewhat) easily.

Variable 1 = Y Axis Offset (Y)
Variable 2 = Incremental Chord lengths (1st, 2nd, 3rd etc) (i)
Variable 3 = Incremental odd numbers (Z)
(Variable 3 becomes the difference between the (X,Y) coordinates)

I will use Y = 23 to demonstrate (this was the one that revealed the pattern to me so that I could reverse engineer the formula)

Y=23 i=1 Z=1

If(((Y*Z+1)/i/2) = integer((Y*Z+1)/i/2)) then X!=((Y*Z+1)/i/2)and Y!=X!+Z else increment Z by 2 and loop
The result is an integer - X!=12. Y! = X!+Z or 13
The first nearest lattice point for Y=23 is (12,13)
[tt]
Y=23 i=2 z=1 The second is (6,7)

Y=23 i=3 z=1 The 3rd is (4,5)

Y=23 i=4 z=1 The fourth is (3,4)

Y=23 i=5 z=1 The fifth is not integer with z=1
Y=23 i=5 z=3 (7,10)

Y=23 i=6 z=1 (2,3)

Y=23 i=7 z=1 Not integer
Y=23 i=7 z=3 (5,8)

Y=23 i=8 z=1 Not integer
Y=23 i=8 z=3 Not integer
Y=23 i=8 z=5 Not integer
Y=23 i=8 z=7 Not integer
Y=23 i=8 z=9 (13,22)

Y=23 i=9 z=1 Not integer
Y=23 i=9 z=3 Not integer
Y=23 i=9 z=5 Not integer
Y=23 i=9 z=7 (9,16)

Y=23 i=10 z=1 Not integer
Y=23 i=10 z=3 Not integer
Y=23 i=10 z=5 Not integer
Y=23 i=10 z=7 Not integer
Y=23 i=10 z=9 Not integer
Y=23 i=10 z=11 Not integer
Y=23 i=10 z=13 (15,28)
[/tt]
etc.....

If no integer values are found before Z=199 then the chord length is invalid.

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

 

[Olaf Doschke]

I'm back on the topic again, too. I think I should change to the strategy focussing on chord length and the circle radiusses they exist in. Let me read first, what you posted in my absence.

What I tried yesterday is still taking too much time, solutions L(10) and L(100) are in the range of seconds, but L(100000) is another league.

Bye, Olaf.

 

[jges]

The IT department updated and restarted all the computers, so my code run got cut short. It is just as well, I was logging the output and got some funny numbers that would have led to an incorrect result. I made a few adjustments to my code and it is off and running again.

 

[jges]

kwbMitel, I've been rereading some posts and I'm still not sure if we agree on counting circle combinations. In the following example, I count 14 unique combinations; what say you?

List1 List2 List3
1 2 1
2 4 2
3 6 8

 

[kwbMitel]

Jges - very insightful question. We definitely are not counting the same way. My first answer would have been 15.

14 is definitely correct. It had not occured to me that multiple duplicates could appear in multiple lists. I was only comparing single intances.

I would not have eliminated the 1-2 combination in the 3rd list as a duplicate of the 1-2 combination in the 1st list.

Here is where my thinking takes a sideways turn. Just speculating as I know these duplicates MUST be removed to get the 3442 count for L(100). Realistically speaking the 1-1 combination in list 1 IS unique from the 1-1 combination is list 3. They combine using different chord lengths and as such the lenticular holes thus formed are different and unique. This might be an argument for another day as I am convinced they must be removed regardless of whether I agree with the reasons.

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

 

[kwbMitel]

jgres - I'm having difficulty formulating a method to eliminate more duplicate pairings from my data. I'm sure a method exists but I havent found it yet.

The numbers I quoted 24 Oct 10 1:19 for duplicates I expect to increase which will reduce my overall total.

If you are counting correctly, I would expect your total to come in under my previous total of 4582172295.

Have you got a number to compare with?

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

 

[jges]

I've grouped the circles into lists based on chord length, my total so far is 4230816335; but I'm only on list 293 of 1304. List 294 (dX: 7 dY: 9, I think) is a real roadblock right now. It has 8755 circles all of which by themselves are duplicates, checking previous lists for duplicate combinations may be proving impractical.

Looking for alternatives, suggestions welcome.

 

[jges]

Update: apparently list 294 (dX: 7 dY: 9) is completely contained in list 227 (dX: 3 dY: 11). I'm going to add a check to skip that list and see what the next roadblock is.

 

[jges]

I found another subset list. This should speed up the process as I eliminate entire lists.