Well ... I'm off to run the finals ... results to follow shortly (Monday) depending on how close the leaders are. In the meantime, I thought I'd send around the squares I'll be using so you can play with them yourself! There are several in this mail, the ones I'm using for the final are the most devious and tricky and tough I could find: THE EQUALIZER, CORNERS, HOT DOG, BEST 741, and HOLY.FACTORY Special thanks to the folks who contributed squares ... better than half the participants helped me out with squares - and a couple were fantastic enough to use for the finals! I am sure I could not have found these tricky squares without your help - in many ways finding interesting squares was harder than writing programs to solve easy ones! Stay tuned for the results .... coming soon to a /usr/mail near you! =Fred ========================================================================== There appear to be some different types of "tough" squares: 1) Those that force the program to "extract" large numbers of 9 digit composites from the square for primality testing ; 2) Those where the extracted 9 digit numbers have large factors, forcing the primality testing to go through large numbers of operations to test for primality ; 3) Sneaky squares, like those with a single digit solution, or the "all 1's" square, or the 7-4-1 class of squares which are recognizable as special cases; . 4) Special solution squares ... like the largest possible 9 digit solution or the smallest possible 9 digit solution or an 8 digit solution from a non-741 square - in general a square constructed very specifically to achieve a particular result. I tried to choose the five final squares to stress all aspects of the problem .... for the most part I depended on the participants - THANK YOU ALL for sending in those tough squares .... So, here they are: THE EQUALIZER Mr. Vincent Goffin, previous POTM winner and squaremaker extraordinaire contributed this gem. 4 0 0 0 9 Note that the vast majority of 9 digit numbers 0 0 0 6 9 are divisible by THREE. In fact, you go through over 0 0 0 6 3 60,000 9-digit numbers before you finally get around 6 0 6 0 3 to testing 600400663 (the solution). Bob Hall 3 3 9 9 0 and Palith Balakrishnabati contributed squares which were similar, but nothing approaching Vince's!!! This one really helps to spread out the timing - thank goodness that SOMETHING did! HOLY FACTORY Nothing smells about this one ... get it? Olefactory, holy factory, lots of factoring, oh well .... 5 0 7 3 5 Another beauty from Vince Goffin. You eventually 4 7 1 5 4 come out with 959545537 ... and along the way you 6 2 4 4 0 extract only 285 9 digit numbers ... BUT, 30 of 1 5 1 5 4 these have smallest factors of more than 1000, and 7 6 2 4 9 6 of them have a smallest factor of more than 20,000! So, if you're checking primes using "%", By the time you're done you've done this over 350,000 times! HOT DOG Well, hot dogs come in "eights", so I had to have a square with an EIGHT digit solution - and there 7 4 7 4 7 appear NOT to be too many around. In fact, aside 4 4 4 4 4 from squares containing ONLY (1,4,7) as in the 7 4 4 4 4 next square, this one is the ONLY one I could 4 4 4 4 4 construct! I hoped that someone may get tripped 7 4 4 4 0 up by this one. The solution is 74447447, which (as the more observant will notice) is 8 digits long. This is MY prize ... found after a vigorous search! For some reason, many entries seemed to overlook the actual solution and come up with 44404447 - also a prime number but not the largest! This was a completely unexpected side effect perhaps due to a mis-application of the 741 test to 8-digit numbers??). Allan Wilks came up with something similar, but with a 9 digit answer ... I'm just SO proud of this square!!! TWO ROWS David Roe held this one back until the 14th, but it's another example of an eight digit solution of the 8 8 8 8 8 non-standard ilk and most worthy of inclusion (darn, 0 0 0 0 0 I thought HOT DOG was SOOO cool). This one doesn't 0 0 0 0 0 even have any 4s or 1s ... and even has eights! 0 0 0 0 0 I expect this one, like many of the others submitted, 7 0 7 0 7 took some time to search out .... either that, or David just happened to notice that 700080007 is not prime and worked from there! BEST 741 Bob Hall was the first to point out that "any grid made up of only 1s, 4s, and 7s (except all of any one) 7 1 4 1 7 will have an eight digit solution. Why? 1, 4, and 7 4 4 7 4 1 are all congruent to 1 mod 3. Thus, nine of them sum 7 1 4 7 7 to 0 mod 3 - and the number is divisible by 3 and cannot 1 7 7 4 4 be a prime. Consequently, the largest solution can have 7 1 4 1 7 no more than 8 digits. This particular square forces a large number of iterations for those folks who didn't realize this little fact and neglected to put in a specific check for this case! CORNERS Bob Ashenfelter inspired this gem ... it turns out that the solution is "7". What makes it neat is that 0 4 0 4 0 there isn't an obvious check for the "short" solution. 0 0 0 0 0 So how come such a short solution? Well - the only 0 0 0 0 0 possible ENDING is a "7". A solution with only zeroes 0 0 0 0 0 and 7s will be divisible by 7 so any solution with 7 0 7 0 7 more than one digit must contain at least one 4. Now, a solution beginning with 7, ending with 7, and having a 4 in it must be 700040007 - a non-prime - so the only set left to examine are those beginning with 4 and ending in 7: it just so happens that valid numbers from 40007 to 404040007 are composite. Thanks to Bob for sending it (even if he DID cleverly wait until 1/12!) NO END Is simply a collection of digits (0,2,4,5,6,8) that cannot end a prime number .... the obvious result is 2 8 5 6 2 that any multi-digit prime could not be contained 4 4 2 4 8 in the square and the largest possible result is 2 8 4 2 5 therefore "5" (since 6 and 8 are composite). Rewards 8 2 2 8 4 those competitors who took the time to recognize and 5 8 4 6 2 respond to these special cases. The FAQ practically gave everyone the code to do this anyhow! BIG SOL Nothing real tricky about this one ... except that the solution is 999999937, the largest prime less 9 4 9 6 7 than the maximum. Unfortunately, it's way too 5 9 5 8 1 easy to consider using for the finals and there 8 7 7 3 7 probably a gazillion squares that could be made 2 6 9 8 3 to yield this result. 1 8 9 4 1 ONES The only square with a two digit solution (??). Unfortunately, I promised not to use this one in 1 1 1 1 1 one of the FAQs - but it is interesting! 1 1 1 1 1 The solution (of course) is 11. Would this extend 1 1 1 1 1 beyond 9 digits? All numbers with an even number 1 1 1 1 1 of "ones" are divisible by 11, and those with a number 1 1 1 1 1 of "ones" divisible by 3 are divisible by 3! As for all the others???? Any way to PROVE that this is the only square with a two digit solution? ========= wanna run them yourself? ... this should make it a bit easier: 4 0 0 0 9 0 0 0 6 9 0 0 0 6 3 6 0 6 0 3 3 3 9 9 0 5 0 7 3 5 4 7 1 5 4 6 2 4 4 0 1 5 1 5 4 7 6 2 4 9 7 4 7 4 7 4 4 4 4 4 7 4 4 4 4 4 4 4 4 4 7 4 4 4 0 0 4 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 0 7 0 7 8 8 8 8 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 0 7 0 7 7 1 4 1 7 4 4 7 4 1 7 1 4 7 7 1 7 7 4 4 7 1 4 1 7 2 8 5 6 2 4 4 2 4 8 2 8 4 2 5 8 2 2 8 4 5 8 4 6 2 9 4 9 6 7 5 9 5 8 1 8 7 7 3 7 2 6 9 8 3 1 8 9 4 1