INTELLIGENT WORK FORUMS
FOR COMPUTER PROFESSIONALS
Come Join Us!
Are you a
Computer / IT professional?
Join Tek-Tips now!
- Talk With Other Members
- Be Notified Of Responses
To Your Posts
- Keyword Search
- One-Click Access To Your
Favorite Forums
- Automated Signatures
On Your Posts
- Best Of All, It's Free!
*Tek-Tips's functionality depends on members receiving e-mail. By joining you are opting in to receive e-mail.
Partner With Us!
"Best Of Breed" Forums Add Stickiness To Your Site
(Download This Button Today!)
Feedback
"...I have been a grateful member of this site for several years. I love this site and refer everyone to it!..."
Geography
Where in the world do Tek-Tips members come from?
|
|
Problem link: http://projecteuler.net/index.php?section=problems&id=295Circle one is centered on (0, 0) with radius r 1Circle two is centered on (x 2, y 2) with radius r 2The equations of our two circles are: x 2 + y 2 = r 12(x - x 2) 2 + (y - y 2) 2 = r 22The distance between (x 1, y 1) and (x 2, y 2) is D = SQR( (x 2 - x 1) 2 + (y 2 - y 1) 2 ) There are no solutions if D = 0 - the circles are coincidentD > r1 + r2 - the circles do not intersect.D < ABS( r1 + r2) - one circle is inside of the other and they do not intersect.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 3, y 3) (x 4, y 4) Once we have those two pairs, we know that either ABS(x 3 - x 4) = 1 or ABS(y 3 - y 4) = 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: How can I maximize my chances of getting an answer?
As a circle of light increases so does the circumference of darkness around it. - Albert Einstein |
|
|
Thargy (TechnicalUser) |
31 Aug 10 10:46 |
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 2+10 2= 100 6 2+8 2= 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 (TechnicalUser) |
31 Aug 10 11:16 |
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 2+10 2= 100 6 2+8 2= 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 |
|
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 1, r 2) for which 0 < r 1 ≤ r 1 ≤ 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: How can I maximize my chances of getting an answer?
As a circle of light increases so does the circumference of darkness around it. - Albert Einstein |
|
|
kwbMitel (TechnicalUser) |
31 Aug 10 11:54 |
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. |
|
==> [/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 √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, √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: How can I maximize my chances of getting an answer?
As a circle of light increases so does the circumference of darkness around it. - Albert Einstein |
|
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: How can I maximize my chances of getting an answer?
As a circle of light increases so does the circumference of darkness around it. - Albert Einstein |
|
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 (TechnicalUser) |
31 Aug 10 15:01 |
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 (TechnicalUser) |
31 Aug 10 15:33 |
|
|
brigmar (Programmer) |
31 Aug 10 15:36 |
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 (Programmer) |
31 Aug 10 15:37 |
Fix for that last post.
The SQUARE OF THE radii must be the sum of two squared integers (including zero). |
|
|
brigmar (Programmer) |
31 Aug 10 15:50 |
I'm disappearing down a rabbithole. Don't mind me.
|
|
|
brigmar (Programmer) |
31 Aug 10 15:59 |
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. |
|
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 (TechnicalUser) |
31 Aug 10 16:24 |
Quote: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 |
|
jges, thank you, looks good. Quote (brigmar):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 (Programmer) |
31 Aug 10 17:53 |
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.
|
|
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 (TechnicalUser) |
1 Sep 10 13:01 |
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). |
|
I think you can use the slope for that. For example slope = Δy / Δx do case case slope = 1 Δy = 1 and Δx = 1 case slope > 1 Δx = 1 case slope < 1 Δ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: How can I maximize my chances of getting an answer?
As a circle of light increases so does the circumference of darkness around it. - Albert Einstein |
|
|
jges (TechnicalUser) |
1 Sep 10 14:18 |
|
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: How can I maximize my chances of getting an answer?
As a circle of light increases so does the circumference of darkness around it. - Albert Einstein |
|
|
brigmar (Programmer) |
1 Sep 10 17:13 |
Errors in calculations, or duplicate entries ?
|
|
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: How can I maximize my chances of getting an answer?
As a circle of light increases so does the circumference of darkness around it. - Albert Einstein |
|
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. |
|
==> 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 (±a, ±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: How can I maximize my chances of getting an answer?
As a circle of light increases so does the circumference of darkness around it. - Albert Einstein |
|
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. |
|
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: How can I maximize my chances of getting an answer?
As a circle of light increases so does the circumference of darkness around it. - Albert Einstein |
|
|
jges (TechnicalUser) |
2 Sep 10 12:59 |
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. |
|
|
jges (TechnicalUser) |
2 Sep 10 14:28 |
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. |
|
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 (TechnicalUser) |
2 Sep 10 15:32 |
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. |
|
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: How can I maximize my chances of getting an answer?
As a circle of light increases so does the circumference of darkness around it. - Albert Einstein |
|
|
jges (TechnicalUser) |
2 Sep 10 16:36 |
So for L(10), these 7 circles account for 21 of the 30 possible solutions. |
|
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. |
|
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 (TechnicalUser) |
2 Sep 10 17:52 |
kwbMitel, I'm not sure we are on the same page. Perhaps this will help: http://www.box.net/shared/jt32zt7jgaThis 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. |
|
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 (TechnicalUser) |
2 Sep 10 19:59 |
Quote:I'm looking for chords in excess of length Root 2 between the points
My next goal as well! |
|
You mean I actually said something meaningful? Intelligible? Cool! **********************************************
What's most important is that you realise ... There is no spoon. |
|
Quote (CajunCenturion):Δ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. |
|
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. |
|
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. |
|
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. |
|
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 Δx2+Δy2 <= 2r2 within both circles. Still the same results.
Bye, Olaf. |
|
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.
|
|
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:
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 xI'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. |
|
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. |
|
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. |
|
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 x2+y2 < r2.
There are (|Δx|, |Δy|) with |Δx|>1 and |Δy|>1, eg for N=100 pairs like (3,7) (for r2 in 5249,6409,7685,9077 among others) and (5,7) (for r2 in 6697,8177 and 9805) so the condition |Δx|=1 or |Δy|=1 is eliminating solutions.
Bye, Olaf |
|
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. |
|
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.
|
|
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. |
|
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. |
|
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. |
|
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. |
|
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. |
|
What I did was simply using SQL, creating the circles by scanning lattice points: CODE#Define N 10
Ns=N^2
Create Table LatticePoints (Rs Int, X Int, Y Int)
For j=0 to N
For i=Max(1,j) to N
rs = i^2+j^2
If rs<=Ns
Insert Into LatticePoints Values (rs, i, j)
EndIf
EndFor
EndFor Each record then stands for up to 8 coordinates (i,j),(i,-j),(-i,j) and (-i,-j), (j,i).... intersection points of the circle. There can of course be more than one record per radius. I then determine chords by matching records with same rs and computing variants of dx,dy via x and y of both records (including self matches), only storing chords with dx>0 and dy>=x. That brute force way I don't miss anything. In fact I limit the usage of the stored i,j to compute positve dx and dy, which reduces computing time, but that's not so important. This results in a table Chords with R,dx,dy,x,y, which are radius, dx and dy of the chord and starting point x,y of the chord. Chords define half lenticlar hole areas between the chords themselve and the circle arc. These are then filtered by checking lattice points along the chord line on the side towards the arc in a "line draw" algorithm. If any of those lattice points other than start and end point has a distance < r towards the center (0,0), the chord disqualifies. I then match two circles by their chords by matching equal dx and dy via CODESelect c1.R as R1, c2.*
from Chords c1
left join Chords c2 on c1.R<=c2.R
and c1.dx=c2.dx and c1.dy=c2.dy And afterwards Select distinct r1,r to determine the number of lenticular holes. All this takes 0.3 seconds for N=100. But for N=100000 I fail due to table size limits, I'll change towards MySQL or SQL Server and then should be good. Bye, Olaf. |
|
Quote (kwbMitel):Olaf, I feel you have already eliminated some circles by some process.
Yes, indeed those chords are what remains after eliminating chords belonging to lenticular holes enclosing lattice points. In conjunction with the radius of the circle a chord belongs to, you can eliminate a chord without knowing the second circle in advance, as you can split a lenticular whole in it's two halves, but you need the combination of chord length and radius, with chords alone you can only eliminate those having a lattice point on them. Before the elimination I get 794 chord lengths of which many eliminate fully. root106 for example has 9 circles, but does only work within one radius, I assume the largest one. Bye, Olaf. |
|
L(100,000) is not being as difficult as I thought. Much fewer valid chord lengths than I first thought. I'm Grouping my Chord Lengths by family according to the difference in coordinates on the Y (Horizontal) Axis The X and Y axis coordinates are always odd integers in separation from 1 another. Family 1 (Y+1) is root(2,10,26,50,82,122,170,226,290,362,442,530,626) These circles all combine with each other and have no minimum size. Total Combinations = 34204 Family 2 (Y+3) is root (34,58,130,178) Minimum size applies Total combinations = 2098 I haven't yet checked for duplicates between these. More to come. **********************************************
What's most important is that you realise ... There is no spoon. |
|
Family 1 = 34204 Holes From 552 Circles
Family 2 = 2098 Holes From 110 Circles
Family 3 = 954 Holes From 74 Circles
More details as follows:
Family 1 breakdown on request
Family 2 (Y+3) is root (34,58,130,178)
Minimum Radius size applies (root of)
34 = 697 (50 Circles, 1275 Holes)
58 = 2465 (36 Circles, 666 Holes)
130 = 31265 (13 Circles, 91 Holes)
178 = 31432 (11 Circles, 66 Holes)
Total Holes = 2098
Family 3 (Y+5) is root (74,106,146,194)
Minimum Radius size applies (root of)
74 = 2257 (32 circles, 528 Holes)
106 = 5989 (24 Circles, 300 Holes)
146 = 19345 (15 Circles, 120 Holes)
194 = 81040 ( 3 Circles, 6 Holes)
Total Holes = 954
Total Holes so far = 37256
Total Duplicate Circles = 34
Grand total so far = 37222
Unfortunately, got to call it a day, work to do **********************************************
What's most important is that you realise ... There is no spoon. |
|
Going faster now, less to check Family 4 (Y+7) is root (130,170,218,274) Minimum Radius size applies (root of) 130 = 12 (32 circles, 78 Holes) 170 = 7 (24 Circles, 28 Holes) 218 = 7 (15 Circles, 28 Holes) 274 = 3 ( 3 Circles, 6 Holes) Total Holes = 140 20 More duplicate circles (54 duplicates total) Total holes now:34150 **********************************************
What's most important is that you realise ... There is no spoon. |
|
Sorry for wasting space. I just realized I set my limit at R = Root(100000) not R = 100000 %#&!#$&#$&^#%!!!! **********************************************
What's most important is that you realise ... There is no spoon. |
|
Reset - Now set my limit correctly. Family 1 = 3087148000 Holes The longest Chord is 199810 (447 X 1) Total Circles = 312060 Without having a way to calculate the minimum radius for the other chord length families, I think I'm back to observation. I can provide the chord lengths, any takers? **********************************************
What's most important is that you realise ... There is no spoon. |
|
I'm still working on this but at the rate I'm going I'm 1 to 2 weeks away from completing. I'm noticing some unusual patterns in the minimum radius length as my chord length and angle increases. For example. - Chord length 99 X 17 - Smallest R = root 125126 - Minimum R = 13425375625 (too big) The next increment is 101 X 17 - Smallest R = Root 131125 - Minimum R = 903634825 (an order of magnitude smaller) Just a heads up, If your using chord lengths as your guide, don't stop incrementing when you reach the first circle length that fails. 97 X 17 is the first one that fails 137 X 17 is the last one that succeeds. The difference between the 2 is how far from the chord end points is the nearest lattice point proximity to the chord. If it is near the center of the chord the circle needs to be bigger than if it is nearer 1 end. **********************************************
What's most important is that you realise ... There is no spoon. |
|
|
jges (TechnicalUser) |
9 Sep 10 11:21 |
I'm glad you posted yesterday, I was afraid everyone had cracked this nut and moved on except me! I haven't had much spare time to give this problem, I'm slowly catching up to you guys. One thing I have found is an equation to find the minimum radius circle for a chord length of the form sqrt(k^2 + 1^2) where k can be an odd integer >= 1. These are the chords of the form delta x = 1 (the ones we know contain no lattice points).
The equation is: r = (k^2 + 1)/2
So instead of finding chord lengths, I'm asserting a chord length and finding circles. For example, if k = 3 (chord length sqrt(10)) the minimum radius = 5. This circle (centered at (0,0) passes through point (5,0). To find the next circle with the same chord length add k to the x coordinate and 1 to the y coordinate. So the next circles that have the same chord length pass through (8,1), (11,2), (14,3), etc
If k = 5 (chord length sqrt(26)), the minimum radius is 13 and the circle passes through (13,0). The next circles pass through (18,1), (23,2), (28,3), etc. You can keep incrementing the circle size until the radius is larger than the specified maximum.
I'm looking for a general form of the chord length / minimum radius equation, but no luck so far. But if you know a circle a chord passes through you can add the chord delta x, delta y to get the next circle. For instance: the chord with length sqrt(7^2 + 3^2) passes through the circle (centered at (0,0)) that passes through (12,1) (not useful since it contains lattice points). The next circles with the same chord length passes through (19,4) [(12+7, 1+3)], (26,7), etc. The first one that doesn't contain lattice points passes through (47,16).
I still don't have a way to calculate if the chord contains lattice points. |
|
I'm also not finished with this. Had little time to optimize my approach. I needed to stop my brute force approach as the initial collection of (i,j,radius^2) with j<i<N would grow to about 200 GB. Doable, but would take some time, while many of the circles will not work anyway.
Bye, Olaf.
|
|
Jgres - Definitely still working on it. Getting more efficient but still way too much manual work. With respect to the minimum circle size. For all chords where the y axis offset is 1, All circles that can contain that chord can be counted (no minimum). I am not looking for the "Smallest" circle but I am looking for the minimum circle from all valid circles that will not contain a lattice point. This is very hard for me without a formula. So far I've calculated all of the circles for Y offset of 1, 3, 5, 7...23. It appears that the upper cutoff for Y offset is around 130's (139 is the highest X value found so far) It may actually be much less than the X value (Around 100) but I won't know until I get there. I can provide my values for minimum circle sizes for each Chord length if anyone want to help me find a formula. In the mean time, the patterns I'm finding are self correcting and I need to spot check less and less the further I go Hopefully I'll have a breakthru soon. I figure I have about 20 hours before I'll have a number **********************************************
What's most important is that you realise ... There is no spoon. |
|
Got 25, 27 and 29 done. And I finally have the beginnings of a pattern in determining the Minimum Circle size within a range. Should start going faster again. Largest X Axis offset so far is 173 **********************************************
What's most important is that you realise ... There is no spoon. |
|
|
jges (TechnicalUser) |
10 Sep 10 13:52 |
I have some code that will determine the minimum radius for a given chord length. It is by no means elegant but seems to work. My method is to determine the closest lattice point to the chord (brute force loop, could be optimized a bit), then calculate the circle that passes through the chord end points and the closest point. Note that this minimum radius circle returned is most likely not a candidate for a solution since it's center point will most likely not coincide with a lattice point (the next candidate circle larger than this one will not contain any lattice points). Here is the code for those interested (in VBScript form so anyone on Windows XP or later can run it; copy it to notepad, save it and change the extension from .txt to .vbs). You will need to enter chordX and chordY (near the top of the file) for your chord of interest. CODESet objFSO = CreateObject("scripting.filesystemobject")
'Set objDistances = objFSO.CreateTextFile("distances.log", True)
''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
' enter values for chord length. Length = sqrt(chordX^2 + chordY^2)
' for chord length sqrt(106) chordX = 5, chordY = 9
chordX = 5
chordY = 9
''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
minX = 1000
minY = 1000
minDistance = 1000
For i = 0 to chordX
For j = 0 to chordY
distance = DistToSegment(i, j, chordX, 0, 0, chordY)
'objDistances.WriteLine(i & "," & j & vbtab & distance)
if distance < minDistance and distance <> 0 then
minX = i
minY = j
minDistance = distance
end if
next
next
'objDistances.WriteLine()
'objDistances.WriteLine(chordX & ",0" & vbtab & "0," & chordY & vbtab & minX & "," & minY)
'objDistances.close
'wscript.echo("minX: " & minX & vbcrlf & "minY: " & minY)
p1X = chordX
p1Y = 0
p2X = 0
p2Y = chordY
p3X = minX
p3Y = minY
ma = (p2Y - p1Y)/(p2X - p1X)
mb = (p3Y - p2Y)/(p3X - p2X)
centerX = (ma * mb * (p1Y - p3Y) + mb * (p1X + p2X) - ma * (p2X + p3X))/(2 * (mb - ma))
centerY = - (1/ma)*(centerX - (p1X + p2X)/2)+(p1Y + p2Y)/2
radius = sqr((p1X - centerX)^2 + (p1Y - centerY)^2)
wscript.echo("minimum radius: " & radius)
'**************************************************************************************************
Function DistToSegment(px, py, X1, Y1, X2, Y2)
Dim dx
Dim dy
Dim t
dx = X2 - X1
dy = Y2 - Y1
If dx = 0 And dy = 0 Then
' It's a point not a line segment.
dx = px - X1
dy = py - Y1
near_x = X1
near_y = Y1
DistToSegment = Sqr(dx * dx + dy * dy)
Exit Function
End If
' Calculate the t that minimizes the distance.
t = ((px - X1) * dx + (py - Y1) * dy) / (dx * dx + dy * dy)
' See if this represents one of the segment's
' end points or a point in the middle.
If t < 0 Then
dx = px - X1
dy = py - Y1
near_x = X1
near_y = Y1
ElseIf t > 1 Then
dx = px - X2
dy = py - Y2
near_x = X2
near_y = Y2
Else
near_x = X1 + t * dx
near_y = Y1 + t * dy
dx = px - near_x
dy = py - near_y
End If
DistToSegment = Sqr(dx * dx + dy * dy)
End Function |
|
|
kwbMitel (TechnicalUser) |
10 Sep 10 23:24 |
jgres - Very good. That helps a bit. Now, if it could output a range of numbers based on incementing either the x or y axis in a format that I can cut and paste then we might have something really useful. One problem. It outputs values for chord lengths that do not work. E.g. X= 5, Y = 25. This is a multiple of X=1, Y=5 and as such cannot have a valid Circle as the chord passes directly thru multiple lattice points. **********************************************
What's most important is that you realise ... There is no spoon. |
|
I have done another approach on finding lattice points within half lenticular holes. Taking a circle with center (0,0) and two intersection points. Let (sx,sy) be one of the intersection points, dx and dy the difference so that (sx+dx,sy+dy) is the endpoint of the chord. Of course sx 2+sy 2 = r 2 and (sx+dx) 2+(sy+dy) 2 = r 2. Because of the symmetry you can always rotate the points, so that dy>0 and dx>=dy, so the slope 0<dy/dx<1 is between 0 and 1 and also the arc of the circle is below the chord. The starting point is below and left of the end point and more left than below. Because the arc should be below the chord interesting lattice points to check are also below the chord, at extreme they could be exactly on the chord line. If that's the case or those lattice points are within the circle radius the half lenticular hole is not a lenticular hole. I compute these lattice points by a very simplistic line algorithm: CODERsquare = sx^2+sy^2
slope = dy/dx
For x=1 to dx-1
y = Floor(x*slope)
If (sx+x)^2+(sy+y)^2<Rsquare
' latice point found within area
' exit loop, chord is no candidate
End If
Next Bye, Olaf. |
|
I've now completed all the chord lengths up to X=63 and Y=157 It's starting to go much faster as most circles are only valid if the closest approach of a lattice point is within 5 of each end. I feel I very close to the end of calulating and will soon be sorting, comparing and adding. **********************************************
What's most important is that you realise ... There is no spoon. |
|
|
jges (TechnicalUser) |
12 Sep 10 13:01 |
Thanks Olaf, that looks like a much simpler approach! |
|
Yes, it is very simple, but needs a little preprocessing, as it has some prerequisites (as said dx>=dy>0) If I imagine this correctly the sx,sy for which this works will rather be in the 4th quadrant (sy<0,sx>0).
Even though the code is short it's not an anylytical approach but an algorithmic. It needs to loop all lattice points along the chord before confirming it to be a half of a lenticular hole, it's faster for detecting nonlenticualar holes and chords not working than chords working.
You may modify it to rather determine the minimum R or R[super]2[/super], for which some dx,dy would work and go the route of kwbMitel solving the problem from the point of view of chords instead of checking all sx,sy.
Bye, Olaf. |
|
I'm burning out on this one. I've got my Y axis offset into the 90's with no clear end in site. I'm starting to make mistakes that are consuming hugh amounts of time to correct. I need a program that will return the x/y coordinates of the nearest lattice point to a chord defined by two other coordinates. I lack the skill. I can no longer plot the coordinates manually for those I cannot predict as it is starting to exceed the resolution of my monitor. I can predict about 80% but a pattern eludes me for the rest which is why things are taking so long. **********************************************
What's most important is that you realise ... There is no spoon. |
|
About 10 minutes after I wrote the last I took another shot at spotting the pattern and got it. I can now predict 100% of the lattice points closest approach to the chord. Don't ask me how I spotted it, I'm kindof crazy that way. I don't know if I'm just tired but I can't even explain it it terms I understand. I just know it works as it is giving me the same values I have manually plotted. **********************************************
What's most important is that you realise ... There is no spoon. |
|
What a difference a formula makes! I've found what I believe to be the upper limit for L(100,000) The Chord Length is Root(88978) The chord end points are at (267,0) and (0,133) The nearest Lattice point to the chord is at (265,1) The minimum valid Circle size is the first of the following 4 R = Root(9778014865) R = Root(9837096257) R = Root(9896355605) R = Root(9955792909) Now that I have all the circles, I need to compare for duplicates. This may take more time than it sounds. I currently have them stored in 65 separate spreadsheets and they total by my estimate around 500,000. **********************************************
What's most important is that you realise ... There is no spoon. |
|
|
kwbMitel (TechnicalUser) |
17 Sep 10 12:41 |
So here I am, I have all the circles plotted and all of their combinations calculated. The last element is to look for duplicate circles that appear in more than 1 family of chord lengths. Currently I have about 67 separate excel spreadsheets that contain these circles. Every 3rd column contains the valid circle radii. there are approximately 500,000 circles. I am more than a little intimidated about manually copting and pasting these circles to another spreadsheet for comparison purposes. Any direction anyone can give me would be appreciated. **********************************************
What's most important is that you realise ... There is no spoon. |
|
Counting away. My estimate of 500,000 circles seems to have been a little low. Well above 600,000 and still counting. Should have an answer tomorrow I think. Whether or not it is the right one is another question altogether. **********************************************
What's most important is that you realise ... There is no spoon. |
|
Well, you'll see when submitting your answer to project euler, if it's correct or not.
I'm still with you, but have to pause on the Euler Project until October.
Bye, Olaf. |
|
|
jges (TechnicalUser) |
20 Sep 10 9:45 |
I'm also in pause mode, but still thinking about it. |
|
I think my chances are about 50/50. Too many areas in my method where a mistake can be made. We'll see soon enough I suppose. **********************************************
What's most important is that you realise ... There is no spoon. |
|
|
kwbMitel (TechnicalUser) |
20 Sep 10 18:03 |
Answer by today was overly optimistic. I've found some errors in my spreadsheets that needed correcting before proceeding. I'm now at 1.1 million circles, but I am nearing the point where there is a large drop off due to the length of the chords. Still working. **********************************************
What's most important is that you realise ... There is no spoon. |
|
|
kwbMitel (TechnicalUser) |
23 Sep 10 15:16 |
Well I've finally got an answer. Not the right one apparently but an answer none the less. I've got all my data stored and when you guys get going maybe we can compare results and I'll see where I went wrong. I have a simple method for calculating the smallest R of a circle that will pass thru a chord of defined size AND not contain a lattice point between the arc and the chord. I'm not sure how to express it mathematically as it requires repeating functions until an integer result is found. Maybe someone can help me with how to express it clearly. **********************************************
What's most important is that you realise ... There is no spoon. |
|
|
jges (TechnicalUser) |
23 Sep 10 15:49 |
I have an important deadline on the 28th, after which I can spend more time on this. If you can describe your method, I'd be glad to try to help. |
|
|
kwbMitel (TechnicalUser) |
24 Sep 10 12:06 |
Here are some of my assumptions that I have used for this puzzle. Does anyone see any issues with these? List of assumptions that have yet to be disproven. 1) - All valid circles than contain a specific chord length will combine with all other circles with the same chord length. 10 circles will combine 55 times using X * (X+1)/2 formula 2) - Valid chord lengths when the end points are plotted on the X=0 and y=0 axis will always have an odd 2nd coordinate of a larger value. If x = 5, the smallest Y value for the other end point will be 7. the end points in this example would be at (5,0) and (0,7) 3) - Some circles will be found with more than 1 chord length. R=5 being an example of a root(2) and Root(10) chord length. These circles must only be counted once for combining with the same size circle. The count determined by #1 assumption above must be reduced by 1 for every duplicate circle found. 4) - For Y axis offset 3 or greater, there will be some valid circles that will contain lattice points. I am assuming that the lattice point that is found nearest the chord will determine the minimum radius that must be used from the set of valid circles. This is my biggest assumption and has had the least scrutiny. My biggest concern is with #4. My confidence level in the others is quite high as they were used to determine the L(100) solution of 3442. Any feedback on the above? **********************************************
What's most important is that you realise ... There is no spoon. |
|
|
jges (TechnicalUser) |
18 Oct 10 14:34 |
Ok, I've picked this back up. When I left off, I was working on generating circles based on valid chord lengths. This looks like it has some promise.
kwbMitel,
1) agree
2) agree. My working theory is both chord length X and Y components must be odd and coprime.
3) mostly agree. What you wrote is true, but to generalize further you have to reduce count for each duplicate combination of circles.
4) agree |
|
|
kwbMitel (TechnicalUser) |
18 Oct 10 20:39 |
Jgres Re: 3) Mostly agree. I may have been unclear in what I meant. To use the L(100) as an example. There were 13 circles that appeared in more than 1 category. 1 circle r=root(1105) appeared in 3. These circles would only be counted once for combining with themselves and reduce the calculated values from step 1 by 14. Re: 4) I am not comfortable with this one at all. Especially when the closest point is near one end or the other. My gut says this one is OK but your agreement helps. **********************************************
What's most important is that you realise ... There is no spoon. |
|
|
jges (TechnicalUser) |
19 Oct 10 15:43 |
Ok, I get correct answers for the L(10) and L(100) cases. I can generate what I think are all the circles for the L(100,000) case in a little over 3 minutes, but I don't think my counting technique is up to the task of L(100,000). It ran for hours and gave an incorrect result. Looks like some brainstorming and bug hunting is in order. |
|
|
jges (TechnicalUser) |
19 Oct 10 21:18 |
I think I found my error. Here's my overall strategy that seems to work: divide each family of circles into its own list (chord length = sqrt(2) in a list, chord length = sqrt(10) in a list, etc etc). CODEfunction ASum(x)
ASum = (x * (x+1))/2
End Function For 1 list, the total number of combinations are ASum(ListCount). For the 2nd list add ASum(List#2Count) and subtract ASum(#Duplicates between list 1 and 2). List 3 and above get a bit trickier as I have to keep track of which duplicates I have already seen. Here's some test code: http://www.box.net/shared/pu1djau5tbIf you run the script, it will create a text file in the folder the script is in named: DictionaryTest.log that steps through what happens. It works well for a small number of lists, it only takes a few seconds for the L(100) case. But it is a brute force type approach that doesn't scale up well. Any suggestions for improvement are welcome! |
|
|
kwbMitel (TechnicalUser) |
19 Oct 10 21:59 |
jgres - Care to share your incorrect answer? I would like to see how close we are to each other. No need to hide the answer as it is incorrect. P.S. I can provide total circles for each Chord Length. P.P.S. I can provide every single circle as well. I'll post my answer tomorrow when I have access to my home PC **********************************************
What's most important is that you realise ... There is no spoon. |
|
|
jges (TechnicalUser) |
19 Oct 10 22:53 |
For what it's worth: 4850255504. |
|
|
jges (TechnicalUser) |
19 Oct 10 22:54 |
Also, I ended up with 922 families of circles. |
|
|
kwbMitel (TechnicalUser) |
20 Oct 10 21:59 |
So my totals are not as high as yours but are still in the same region. Total Combinations = 4582451728 Total Circles = 1454232 Total Duplicate circles = 279433 Total Holes = Combinations - Duplicates = 4582172295 I grouped my circles differently than you so I don't immediately have a total of all the different chord lengths (What you call families I assume) 922 sounds about right but I'll count them shortly and post again. **********************************************
What's most important is that you realise ... There is no spoon. |
|
|
jges (TechnicalUser) |
20 Oct 10 22:44 |
Yes, by families I meant chord lengths.
I had another run at it today. Another number in the same ballpark, but still incorrect. I have a feeling that I'm not catching all the chord lengths for the 100,000 case. Also, I'm still suspicious of my counting technique.
I'm curious of your counting technique, but it's getting late here. I'll post a more specific question/example tomorrow if I find time. |
|
|
kwbMitel (TechnicalUser) |
20 Oct 10 23:34 |
I tallied my Chord Lengths and it is much higher than yours. 1302 My technique is very basic (And unusual). I have 67 excel spreadsheets grouping the chord lengths by the Y axis offset. The smallest y axis offset is 1 and this yields 224 chord lengths from X=1 to X=447. This grouping does not have any minimum circle sizes. Y Axis offset = 3 by comparison only has 31 Chord Lengths starting with X = 5 and maxing out at X = 101. Every 3rd one in this group is a multiple of Y=1 and is invalid. Also this group has minimims for circle radius within each length as some combinations of smaller circles contain lattice points. The largest y offset is 133 and only yields 2 chord lengths and 12 circles that combine for 46 holes I can provide complete data on each and every chord length that I consider valid. Obviously I've missed something but by comparing data maybe we can come to a concensus **********************************************
What's most important is that you realise ... There is no spoon. |
|
|
jges (TechnicalUser) |
21 Oct 10 9:08 |
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 (TechnicalUser) |
21 Oct 10 10:46 |
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 (TechnicalUser) |
21 Oct 10 19:47 |
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
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 **********************************************
What's most important is that you realise ... There is no spoon. |
|
|
jges (TechnicalUser) |
21 Oct 10 20:57 |
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 (TechnicalUser) |
22 Oct 10 14:58 |
Quote (kwbMitel):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 (TechnicalUser) |
22 Oct 10 19:40 |
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. |
|
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.
X Minimum Radius Total Circles
99 Root(6171283169) 217
101 Root(6750760369) 177To 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?
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 **********************************************
What's most important is that you realise ... There is no spoon. |
|
|
jges (TechnicalUser) |
23 Oct 10 19:05 |
Quote (kwbMitel):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 (TechnicalUser) |
23 Oct 10 20:36 |
Here's my data: CODEChord 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
|
|
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 (TechnicalUser) |
24 Oct 10 12:40 |
Quote (kwbMitel):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 (TechnicalUser) |
24 Oct 10 13:48 |
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)
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)
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. |
|
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 (TechnicalUser) |
27 Oct 10 9:58 |
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 (TechnicalUser) |
27 Oct 10 11:02 |
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 (TechnicalUser) |
27 Oct 10 22:12 |
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 (TechnicalUser) |
28 Oct 10 11:38 |
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 (TechnicalUser) |
28 Oct 10 12:20 |
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 (TechnicalUser) |
28 Oct 10 12:54 |
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 (TechnicalUser) |
28 Oct 10 15:59 |
I found another subset list. This should speed up the process as I eliminate entire lists. |
|
I'm still having difficulty cross referencing. I can confirm that all 8755 of X=7 Y=9 are duplicates but I can't confirm as yet that they are duplicates of a single other list (but it looks likely) There are quite a few of the duplicates that come from the X=7 family. I'm still working on it but the way I have my data organised is not condusive to this type of comparison. **********************************************
What's most important is that you realise ... There is no spoon. |
|
|
kwbMitel (TechnicalUser) |
30 Oct 10 11:34 |
Here are some more chord lengths that can be eliminated
X=11 Y=13 5836 Circles Contained entirely in X=1 X=17
X=09 y=19 4736 Circles Contained entirely in X=1 X=21
X=13 y=19 4309 Circles Contained entirely in X=1 X=23
X=17 y=21 3635 Circles Contained entirely in X=1 X=27
X=11 y=29 3128 Circles Contained entirely in X=1 X=31 **********************************************
What's most important is that you realise ... There is no spoon. |
|
|
kwbMitel (TechnicalUser) |
30 Oct 10 15:52 |
More eliminations - Chords defined by:
Duplicate Original
X Y X Y
19 27 1 33
23 29 1 37
13 41 1 43
19 43 1 47
31 43 1 53
25 49 1 55
21 53 1 57
37 51 1 63
41 53 1 67
17 71 1 73
51 55 1 75
47 61 1 77
39 71 1 81
31 77 1 83
**********************************************
What's most important is that you realise ... There is no spoon. |
|
|
kwbMitel (TechnicalUser) |
31 Oct 10 16:29 |
I'm starting to find chord lengths where all but a few a completely cancelled out. 3334 of 3337 for example. I've found 10 of these so far. I've also found 13 more completely cancelled out. I think I'll work though finding all of the complete eliminations before moving on to the partials. So far I've eliminated in excess of 50,000 circles. **********************************************
What's most important is that you realise ... There is no spoon. |
|
|
kwbMitel (TechnicalUser) |
31 Oct 10 19:08 |
Interesting development. I'm now finding complete chord lengths that are eliminated by higher Y Offset values. Example X=11 Y =47 is contained within X=31 Y=37. Not sure what this might mean to your method but I thought I'd give you a heads up. **********************************************
What's most important is that you realise ... There is no spoon. |
|
|
jges (TechnicalUser) |
1 Nov 10 10:20 |
I found 240 lists that could be completely eliminated (using the grouping method I've described earlier in the thread).
I let it run over the weekend, it ran for 10 hours most of which was just comparing lists but it did complete. |
|
|
jges (TechnicalUser) |
1 Nov 10 10:22 |
|
|
IPGuru (TechnicalUser) |
1 Nov 10 10:33 |
Congratulations, I have been following this thread with mild interest, but never actualy tried to produce any code myself all you need to do now is speed the process up to fit the 3 minute expectation good luck I do not Have A.D.D. im just easily, Hey look a Squirrel! |
|
jgres - Success? Does this mean you've submitted your answer and it is correct? If so Congrats. I've eliminated over 100 lists so far but my process is manual so I expect it to take much longer. Olaf - I think the 3 minute expectation in this case is out to lunch. The description was probably written before this puzzle was added. I suspect many of the newer puzzles cannot be solved in 3 minutes or less. **********************************************
What's most important is that you realise ... There is no spoon. |
|
|
jges (TechnicalUser) |
1 Nov 10 11:29 |
I had a quick look at the project euler forum to see what others had to say and a number post code that claims to solve the problem in less than 1 minute (I have not taken a good look or run any of the code, so I have to take their word at this point). The creator of the problem posted and claims to be able to solve the L(1,000,000) case in less than 8 seconds, L(100,000) in less than 1 second. When I have time, I'm going to look more closely at what they did as I'm sure I'll learn something that will help in the future (both project euler problems and more importantly, real world problems). |
|
|
jges (TechnicalUser) |
1 Nov 10 11:50 |
Quote (kwbMitel):...Congrats
Thank you for your help. I'm not sure I would have got there without the exchange of ideas in this thread. And keep at it, now you know you are on the right track, you will be the next one submitting an answer! |
|
Jgres - I can probably go a little faster now as I was recording all the eliminated lists and where they were found in case you needed them. Now I'll just concentrate on eliminating and not cross referencing. It also helps to know how many to expect, thanks for that. **********************************************
What's most important is that you realise ... There is no spoon. |
|
Jges Please confirm 240 Chords eliminated. I only found 239. **********************************************
What's most important is that you realise ... There is no spoon. |
|
|
jges (TechnicalUser) |
2 Nov 10 17:58 |
In my bookkeeping method there were 240 chords with unique dx, dy that were subsets of other chords.
I can compile a list if you like, but it will take some cross referencing so it wouldn't be until tomorrow afternoon at best. |
|
Don't put yourself out yet. Let me double Check some things first. **********************************************
What's most important is that you realise ... There is no spoon. |
|
|
jges (TechnicalUser) |
2 Nov 10 21:19 |
I don't think this is really a spoiler, but if you don't want a hint it I'll put it in a spoiler tag: Spoiler:focus your search on chords that are the same length but have different dx dy values |
|
Thanks for the hint. That will actually be very helpful. I had not yet tried to figure out what the common factor was for these chords. I had been assuming it was some multiple but hadn't gotten around to checking. At this point where I've already discovered 239 (possibly 240 if I miscounted), its more a method of verification. Actually, if you had given it to me earlier, I might have saved me about 6 hours work. **********************************************
What's most important is that you realise ... There is no spoon. |
|
|
 |
|
Talk To Other Members
Read More Threads Like This One