Smart questions
Smart people
 Find A ForumFind An Expert
INTELLIGENT WORK FORUMS
FOR COMPUTER PROFESSIONALS

Remember Me

Are you a
Computer / IT professional?
Join Tek-Tips now!
• Talk With Other Members
• Be Notified Of Responses
• Keyword Search
Favorite Forums
• Automated Signatures
• 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.

#### LINK TO THIS FORUM!

Add Stickiness To Your Site By Linking To This Professionally Managed Technical Forum.
Just copy and paste the
code below into your site.

#### Partner With Us!

"Best Of Breed" Forums Add Stickiness To Your Site

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

# Lenticular Circles

 Forum Search FAQs Links Jobs Whitepapers MVPs
 CajunCenturion (Programmer) 31 Aug 10 10:21
 Problem link:  http://projecteuler.net/index.php?section=problems&id=295Circle one is centered on (0, 0) with radius r1Circle two is centered on (x2, y2) with radius r2The equations of our two circles are:x2 + y2 = r12(x - x2)2 + (y - y2)2 = r22The distance between (x1, y1) and (x2, y2) isD = SQR( (x2 - x1)2 + (y2 - y1)2 )There are no solutions ifD = 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(x3, y3)(x4, y4)Once we have those two pairs, we know that eitherABS(x3 - x4) = 1 orABS(y3 - y4) = 1And of course, all point coordinates are integers.It's a start.  --------------Good LuckTo get the most from your Tek-Tips experience, please readFAQ181-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,02+102= 10062+82= 100This 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. RegardsT
 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,02+102= 10062+82= 100This 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 radius10 (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. RegardsT
 CajunCenturion (Programmer) 31 Aug 10 11:30
 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.
 CajunCenturion (Programmer) 31 Aug 10 12:30
 CajunCenturion (Programmer) 31 Aug 10 12:34
 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 LuckTo get the most from your Tek-Tips experience, please readFAQ181-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
 OlafDoschke (Programmer) 31 Aug 10 13:56
 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
 Since the center must be at a lattice point and the circumference must pass through lattice points, there is a finite number of circles to consider. For the case of N=10, there are 43 possible circles you can use.http://www.box.net/files/0/f/23930418#/files/0/f/23930418/1/f_498548246
 brigmar (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 0radius of 5 = (5,0),(4,3),(3,4), and (0,5). Works because of 5 and 4radius 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.
 OlafDoschke (Programmer) 31 Aug 10 16:09
 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
 OlafDoschke (Programmer) 31 Aug 10 16:45
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.
 OlafDoschke (Programmer) 1 Sep 10 6:13
 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)etcfor 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.16227766016840etcWe 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).
 CajunCenturion (Programmer) 1 Sep 10 13:43
 I think you can use the slope for that.For exampleslope = Δy / Δxdo case   case slope = 1      Δy = 1  and  Δx = 1   case slope > 1      Δx = 1   case slope < 1      Δy = 1endcaseI think we can use ABS to manage the sign for this.  --------------Good LuckTo get the most from your Tek-Tips experience, please readFAQ181-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
 Excellent observation.
 CajunCenturion (Programmer) 1 Sep 10 16:49
 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 LuckTo get the most from your Tek-Tips experience, please readFAQ181-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 ?
 CajunCenturion (Programmer) 1 Sep 10 18:11
 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 LuckTo get the most from your Tek-Tips experience, please readFAQ181-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) 1 Sep 10 18:49
 CC - How fine are you cutting it. Does your lenticular area "touch" more than 2 lattice points? Again, might be a stupid question as it might not be possible to have an area that touches more than 2 (4 in fact) without enclosing and meeting the rest of the requiremetns. **********************************************What's most important is that you realise ...  There is no spoon.
 CajunCenturion (Programmer) 2 Sep 10 7:19
 ==> 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 LuckTo get the most from your Tek-Tips experience, please readFAQ181-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
 OlafDoschke (Programmer) 2 Sep 10 11:40
 The slope is not sufficient, two circles can match and intersect, if they have the same Δx and Δy in the lattice points they go through.Indeed, the second circle can only be one of the circles we already determined (see jges illustration), of course the chord length are good candidates for a match, so you could sort circles by such chord lengths to find matches, also remember r2>=r1.Also circles having more than 4 lattice points can be easily determined by being the ones which are constructed by different lattice points in the first place, but having the same radius.Bye, Olaf.
 CajunCenturion (Programmer) 2 Sep 10 12:03
 Δx and Δy give you both slope and distance.  --------------Good LuckTo get the most from your Tek-Tips experience, please readFAQ181-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
 CajunCenturion (Programmer) 2 Sep 10 12:57
 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 LuckTo get the most from your Tek-Tips experience, please readFAQ181-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.
 CajunCenturion (Programmer) 2 Sep 10 13:00
 Yep, those are gone in the first pass. --------------Good LuckTo get the most from your Tek-Tips experience, please readFAQ181-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 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.
 kwbMitel (TechnicalUser) 2 Sep 10 14:45
 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.
 CajunCenturion (Programmer) 2 Sep 10 16:15
 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 LuckTo get the most from your Tek-Tips experience, please readFAQ181-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.
 kwbMitel (TechnicalUser) 2 Sep 10 16:55
 Oh well then, that being the case, ignore my last. I definitely did not consider them distinct. Ok, rotational symmetry allowed.   **********************************************What's most important is that you realise ...  There is no spoon.
 kwbMitel (TechnicalUser) 2 Sep 10 17:37
 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)1The 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.
 kwbMitel (TechnicalUser) 2 Sep 10 18:12
 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!
 kwbMitel (TechnicalUser) 3 Sep 10 0:23
 You mean I actually said something meaningful? Intelligible?Cool! **********************************************What's most important is that you realise ...  There is no spoon.
 OlafDoschke (Programmer) 3 Sep 10 2:09

#### 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.
 kwbMitel (TechnicalUser) 4 Sep 10 0:54
 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,0R2=5 circles can be either at 12,4 or 4,12.I do not consider these "Distinct" and would only count 1.Is this correct? **********************************************What's most important is that you realise ...  There is no spoon.
 kwbMitel (TechnicalUser) 4 Sep 10 1:29
 Ignore that, I've finally got my count of 30 and the answer is now self explained. (Count only 1) **********************************************What's most important is that you realise ...  There is no spoon.
 kwbMitel (TechnicalUser) 4 Sep 10 1:49
 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.
 OlafDoschke (Programmer) 4 Sep 10 3:13
 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.
 OlafDoschke (Programmer) 4 Sep 10 6:46
 Ah, I see. Drawing the circles with chords helps seeing the condition is not sufficient. Of course the larger circles get, the shorter the chords have to be. And it's sufficient to examine half the lenticular holes of course, if half the hole contains a lattice point that chord is out for matching with other circles.I still lack a way of checking the condition of no lattice point within the lenticualar hole.Bye, Olaf.
 kwbMitel (TechnicalUser) 4 Sep 10 10:42
 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 Root85Root1  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.
 kwbMitel (TechnicalUser) 4 Sep 10 11:21
 I've got to walk away for a time. Head spinning. With my 144 circles I get a count of 3430 (14 short) **********************************************What's most important is that you realise ...  There is no spoon.
 kwbMitel (TechnicalUser) 4 Sep 10 11:27
 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.
 OlafDoschke (Programmer) 4 Sep 10 11:47
 Got it. Still not for N=100000, a table of circles I create and insert into get's too large.L(10)=30L(100)=3442L(1000)=393451I 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
 kwbMitel (TechnicalUser) 4 Sep 10 12:14
 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, root170root2  Chord circles = 71  Combine 2556 timesroot10 Chord circles = 31  Combine 496 timesroot26 Chord circles = 18  Combine 171 timesroot50 Chord circles = 11  Combine 66 timesroot82 Chord circles = 7  Combine 28 timesroot122 Chord circles = 4  Combine 10 timesroot170 Chord circles = 2  Combine 3 timesSome circles apply to 2 categories such as the R=5 circle. It can also combine with the root10 Chords >= R=5Root2 R=root25 combines with 31 Root10'sRoot2 R=Root1105 combines with 22 root10'sRoot2 R=Root1105 combines with 14 root26'sRoot2 R=Root3445 combines with 9 root26'sRoot2 R=Root7565 combines with 5 root10'sRoot2 R=Root8845 combines with 1 root122Root10 R=Root1105 combines with 14 root26'sRoot10 R=Root5525 combines with 4 root50'sThis 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.
 OlafDoschke (Programmer) 4 Sep 10 14:45
 kwbMitel,if I compute the chord lengths, aditional to you I get 13 circels with root34, 7 with root58 and 3 with root74 and 1 with root106.That should help you already.Bye, Olaf.
 kwbMitel (TechnicalUser) 4 Sep 10 15:25
 Yes thanks, I'll try and see how I missed those and fit them in.The additional 100 I was counting earlier a red herring. I was simple counting things twice.You additions may give me the 112 more I need **********************************************What's most important is that you realise ...  There is no spoon.
 kwbMitel (TechnicalUser) 4 Sep 10 16:22
 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 getRoot34 chords = 16 CirclesRoot58 chords = 12 CirclesRoot74 chords = 11 CirclesRoot106 chords = 9 circlesIt seems obvious that not all will combine with each other. Need to start graphing again to determine a formula. **********************************************What's most important is that you realise ...  There is no spoon.
 kwbMitel (TechnicalUser) 4 Sep 10 18:45
 Got it , Sort ofRoot34 Chords minimum R=Root697 = 13 CirclesRoot58 Chords Minimum R=Root2465 = 7 CirclesRoot74 Chords Minimum R=Root6697 = 3 CirclesRoot106 Chords Minimum R=Root9593 = 1 CirclesUnfortunately, these would add 126 Combinations not 112 like I needed.Now I'm 14 over.Help? **********************************************What's most important is that you realise ...  There is no spoon.
 kwbMitel (TechnicalUser) 4 Sep 10 20:43
 Re:L(100)Correction found 10 where I was counting combinations twiceI'm now 4 over.159 Distinct Circles, so close now...Has anyone yet got the 3442 number for L(100)? **********************************************What's most important is that you realise ...  There is no spoon.
 kwbMitel (TechnicalUser) 5 Sep 10 0:53
 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.
 OlafDoschke (Programmer) 5 Sep 10 4:34
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

#### CODE

Select 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.
 OlafDoschke (Programmer) 5 Sep 10 5:33

#### 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.
 kwbMitel (TechnicalUser) 5 Sep 10 12:06
 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) AxisThe 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 = 34204Family 2 (Y+3) is root (34,58,130,178)Minimum size appliesTotal combinations = 2098I haven't yet checked for duplicates between these.More to come. **********************************************What's most important is that you realise ...  There is no spoon.
 kwbMitel (TechnicalUser) 5 Sep 10 13:32
 Family 1 = 34204 Holes From 552 CirclesFamily 2 =  2098 Holes From 110 CirclesFamily 3 =   954 Holes From  74 CirclesMore details as follows:Family 1 breakdown on requestFamily 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 = 2098Family 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 = 954Total Holes so far = 37256Total Duplicate Circles = 34Grand total so far = 37222Unfortunately, got to call it a day, work to do **********************************************What's most important is that you realise ...  There is no spoon.
 kwbMitel (TechnicalUser) 5 Sep 10 17:17
 Going faster now, less to checkFamily 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 = 14020 More duplicate circles (54 duplicates total)Total holes now:34150 **********************************************What's most important is that you realise ...  There is no spoon.
 kwbMitel (TechnicalUser) 5 Sep 10 17:29
 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.
 kwbMitel (TechnicalUser) 6 Sep 10 10:25
 Reset - Now set my limit correctly.Family 1 = 3087148000 HolesThe longest Chord is 199810 (447 X 1)Total Circles = 312060Without 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.
 kwbMitel (TechnicalUser) 8 Sep 10 19:18
 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 fails137 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
 OlafDoschke (Programmer) 9 Sep 10 12:14
 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
 kwbMitel (TechnicalUser) 9 Sep 10 17:06
 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.
 kwbMitel (TechnicalUser) 10 Sep 10 1:53
 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.

#### CODE

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

'**************************************************************************************************
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.
 OlafDoschke (Programmer) 11 Sep 10 5:09
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 sx2+sy2 = r2 and (sx+dx)2+(sy+dy)2 = r2.

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:

#### CODE

Rsquare = 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.
 kwbMitel (TechnicalUser) 12 Sep 10 2:20
 I've now completed all the chord lengths up to X=63 and Y=157It'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!
 OlafDoschke (Programmer) 13 Sep 10 7:48
 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.
 kwbMitel (TechnicalUser) 15 Sep 10 0:57
 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.
 kwbMitel (TechnicalUser) 15 Sep 10 1:49
 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.
 kwbMitel (TechnicalUser) 16 Sep 10 1:47
 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 4R = 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.
 kwbMitel (TechnicalUser) 20 Sep 10 1:23
 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.
 OlafDoschke (Programmer) 20 Sep 10 4:42
 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.
 kwbMitel (TechnicalUser) 20 Sep 10 9:57
 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 formula2) - 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) agree2) 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
 JgresRe: 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).

#### CODE

function 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/pu1djau5tb

If 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 = 4582451728Total Circles = 1454232Total Duplicate circles = 279433Total Holes = Combinations - Duplicates = 4582172295I 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.1302My 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 holesI 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=3X    Minimum Radius    Total Circles   Total Holes5    Root(697)             17146       1470012317    Root(2465)            13125       8613937511   Root(31265)           8756        38338146        13   Root(67729)           7476        2794902617   Root(354769)          5759        1658592019   Root(606985)          5159        1331022023   Root(2034985)         4250        903337525   Root(3062537)         3903        761865629   Root(7915625)         3334        555944531   Root(11002225)        3105        482206535   Root(24014257)        2708        366798637   Root(31628545)        2543        323469641   Root(61330945)        2243        251664643   Root(77702489)        2116        223978647   Root(138071609)       1874        175687549   Root(169882105)       1772        157087853   Root(282286105)       1568        123009655   Root(339475777)       1481        109742159   Root(534921025)       1302        84825361   Root(631610225)       1226        75215165   Root(953287217)       1063        56551667   Root(1108813225)      995         49551071   Root(1614942025)      842         35490373   Root(1855011049)      780         30459077   Root(2621986249)      634         20129579   Root(2979940625)      575         16560083   Root(4105775825)      433         9396185   Root(4623976417)      377         7125389   Root(6232048225)      237         2820391   Root(6963372025)      182         1665395   Root(9206463577)      43          94697   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=5X    Minimum Radius    Total Circles7    Root(6697)            116169    Root(9593)            970411   Root(19345)           826513   Root(107185)          715717   Root(465505)          560519   Root(407809)          505821   Root(620945)          459623   Root(2450065)         418327   Root(6312865)         355129   Root(4427425)         332731   Root(5922409)         310833   Root(19854265)        286337   Root(39579145)        251039   Root(24739865)        241741   Root(30862393)        228743   Root(94450537)        208647   Root(162256537)       184749   Root(94629769)        183351   Root(113066369)       174453   Root(326648257)       153957   Root(509534257)       135459   Root(283777393)       140561   Root(283777393)       133863   Root(914476225)       110467   Root(1333401745)       94569   Root(718649009)       105871   Root(816651865)       100473   Root(2203291465)       72677   Root(3056619865)       58079   Root(1607495305)       75781   Root(1798020809)       71083   Root(4745856025)       37587   Root(6337060105)       23589   Root(3269957785)       48191   Root(3612615793)       43893   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.
 kwbMitel (TechnicalUser) 23 Oct 10 0:07
 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=5For the ones you listed we match exactly but I also have these.X    Minimum Radius    Total Circles99   Root(6171283169)    217101  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 CirclesOffset   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:

#### CODE

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 (TechnicalUser) 24 Oct 10 1:19
 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 = 1454232I get total holes of 4582451728 before duplicate checkingI find 279433 Duplicate circlesFinal 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=1If(((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 loopThe result is an integer - X!=12.  Y! = X!+Z or 13The 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=1Y=23  i=5  z=3  (7,10)Y=23  i=6  z=1  (2,3)Y=23  i=7  z=1  Not integerY=23  i=7  z=3  (5,8)Y=23  i=8  z=1  Not integerY=23  i=8  z=3  Not integerY=23  i=8  z=5  Not integerY=23  i=8  z=7  Not integerY=23  i=8  z=9  (13,22)Y=23  i=9  z=1  Not integerY=23  i=9  z=3  Not integerY=23  i=9  z=5  Not integerY=23  i=9  z=7  (9,16)Y=23  i=10  z=1  Not integerY=23  i=10  z=3  Not integerY=23  i=10  z=5  Not integerY=23  i=10  z=7  Not integerY=23  i=10  z=9  Not integerY=23  i=10  z=11 Not integerY=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.
 OlafDoschke (Programmer) 27 Oct 10 6:44
 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.
 kwbMitel (TechnicalUser) 29 Oct 10 1:17
 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 eliminatedX=11 Y=13  5836 Circles Contained entirely in X=1 X=17X=09 y=19  4736 Circles Contained entirely in X=1 X=21X=13 y=19  4309 Circles Contained entirely in X=1 X=23X=17 y=21  3635 Circles Contained entirely in X=1 X=27X=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       OriginalX     Y         X    Y19    27        1    3323    29        1    3713    41        1    4319    43        1    4731    43        1    5325    49        1    5521    53        1    5737    51        1    6341    53        1    6717    71        1    7351    55        1    7547    61        1    7739    71        1    8131    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
 Success!!
 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 myselfall you need to do now is speed the process up to fit the 3 minute expectationgood luck  I do not Have A.D.D. im just easily, Hey look a Squirrel!
 kwbMitel (TechnicalUser) 1 Nov 10 11:17
 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!
 kwbMitel (TechnicalUser) 1 Nov 10 12:20
 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.
 kwbMitel (TechnicalUser) 2 Nov 10 17:23
 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.
 kwbMitel (TechnicalUser) 2 Nov 10 18:40
 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
 kwbMitel (TechnicalUser) 3 Nov 10 10:46
 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.

#### Posting in the Tek-Tips forums is a member-only feature.

Click Here to join Tek-Tips and talk with other members!

Close Box

# Join Tek-Tips® Today!

Join your peers on the Internet's largest technical computer professional community.
It's easy to join and it's free.

Here's Why Members Love Tek-Tips Forums:

• Talk To Other Members
• Notification Of Responses To Questions
• Favorite Forums One Click Access
• Keyword Search Of All Posts, And More...

Register now while it's still free!