Beware of long mail .... but there ARE gems buried! Even if you don't study the whole thing, you might want to check out the first four or five writeups! The attached mail is the collection of write-ups I received. As usual they are mostly unedited (only personal POTM-master insults were removed). They are provided in order of SPEED (more or less). There are also other files available on request via email or uuto: 1. A cpio containing primeval.c, wookin_po_nubbas.c, and pringle.c (these were the three fastest - their authors have been kind enough to extensively comment their code for us all!) 2. A cpio with 160 squares I considered for the finals 3. The derivation of the digit rules for 7, 11, 13 (in MATH stuff) 4. Other entries are available, but I have not asked them to be commented - some are/some are not - please request by name (I won't just "ship them all"!) This, together with the consolation prize mail, will be the last you hear of prime numbers ... hope it was fun (complaints >/dev/null)! I'm off to think up the NEXT one, coming within a few weeks with luck! =Fred ---()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--- -()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()- ---()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--()--- ======================================= primeval ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer primeval 410 90 90 70 80 80 ================= primeval was submitted by Allan Wilks at allan@research.att.com ================= HOW DID primeval CHOOSE CANDIDATES FROM THE SQUARE ? o breadth-first search o use bit-vectors to keep track of neighbors o watch out for grids that are almost trivial (and hence deadly) HOW DID primeval TEST A CANDIDATE FOR PRIMALITY ? o trial division by small primes (40 of them) o Miller tests to the bases 2 and 3 ANY OTHER COMMENTS, TRICKS, WHATEVER? o many thanks to Jim Roche for a great collaboration on primality testing WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? o statsitics research; specialty is statistical computing ANY IDEAS FOR THE NEXT POTM? o POTM should be short; about 2 or 3 weeks max I would say; otherwise lots of time gets wasted and a lot of that is spent pursuing tiny optimizations; also, in the real world no one ever gets three months to work on such a well-defined, small problem ================================================================= ======================================= =wookin_po_nubbas ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer =wookin_po_nubbas 430 90 80 80 80 100 ================= wookin_po_nubbas was submitted by Jim Roche at roche@ccr-p.ida.org ================= HOW DID wookin_po_nubbas CHOOSE CANDIDATES FROM THE SQUARE ? Gradually built up each candidate from the highest order digit to the lowest, searching first over 9-digit numbers, then over 8-digit numbers, etc., all in descending order. The most important thing to notice (as most people probably did) is that in order to decide where to go to pick up the next digit, you need only keep track of your current _state_, which consists solely of the location of the last digit chosen. (If returns to the same grid location had been disallowed, this trick would not have worked, and the problem would probably have been much harder, at least for the nastiest grids.) In fact, in order to prevent an exponential explosion in the number of paths searched for grids with lots of repeated digits, the thing to do is to keep track of the SET of all grid locations that you can occupy and have whatever part of the candidate you've constructed so far. Thus we actually let our state consist of the part of the number we've constructed so far, together with the set of all grid locations that we could occupy at the moment (given the sequence of digits so far). This state is also easy to update quickly, especially if one uses bit maps. Thus we can search many paths simultaneously, and the total time depends only on the number of candidates that we have to test for primality (and upon the difficulty of testing them, of course). The search phase takes very little time for most grids. However, some grids have special properties modulo 2,3, and/or 5. These grids can require tens of thousands of primality tests for the unwary contestant, so we give the search routine enough intelligence to recognize when it can lop of huge portions of the search tree (before building up complete 9-digit numbers). It's also helpful to use some simple tricks so that we never have to do a general divisibility test on any number that's a multiple of 2,3, or 5. HOW DID wookin_po_nubbas TEST A CANDIDATE FOR PRIMALITY ? This is where the fun really begins. Allan Wilks and I worked together on this aspect (but not on the search) and used every trick in the book to speed things up. The basic idea was to quickly build a small table containing the first 40 or 50 primes (up to about 200) at the beginning of the program, then use this table to do trial division of candidates. Candidates that survived were subjected to a modified Miller test, which is based on Fermat's Little Theorem. We found that because of constraints imposed by the grid, many numbers would never be tested for primality, because if one of these numbers appeared in the grid, necessarily some larger prime (which we would have already found) would also be in the grid. As a simple example, we would never have to test 17 for primality, because we would have already found the prime 71. As a result, we found that the number of basic pseudoprime tests we had to do could be reduced from 4 (as in the ordinary Miller test for primality of numbers less than 10^9) to 2, because most of the pseudoprimes would never be handed to our primality test in the first place. We wound up doing both the trial division and the Miller tests using a combination of integer and floating point arithmetic. These routines are probably the most cryptic, but perhaps the most interesting, parts of the program (at least of _my_ program). ANY OTHER COMMENTS, TRICKS, WHATEVER? It's scary how much time has gone into this contest. As Fred warned me after a previous contest, there's a real danger of winding up in the Betty Ford Clinic after participating in a POTM. The program name "wookin_po_nubbas" is a take-off on the song "Wookin' po Nub," which was comedian Eddie Murphy's version of the country-western song "Lookin' for Love (in all the wrong places)." Murphy used to put on a huge unruly wig and speak very indistinctly, pretending to be the character Buckwheat from the Little Rascals. He made one phony commercial (much like the real commercials that one sometimes sees on late-night TV) advertising a record of Buckwheat's Greatest Hits, in which his Buckwheat character was shown singing snippets of dozens of popular songs as the phonetically spelled titles (e.g., "Wookin' po Nub") scrolled down the screen. My program name is admittedly a pretty bad (and obscure) pun, but with the above paragraph as background, I imagine that it will be easy enough to decipher. Maybe I should have chosen "the_indivisible_man" as a program name instead. WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? Used to be a postdoc at Bell Labs in Murray Hill, which is where I did my first POTM. Now I'm working at the Center or Communications Research in Princeton. Like to play volleyball, softball, and touch football (though not simultaneously), juggle, read, sing, and do recreational math. ANY IDEAS FOR THE NEXT POTM? Probably only allow a month or so instead of three months. This should allow enough time for people to write pretty good programs without going off the deep end. ================================================================= ======================================= =pringle ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer =pringle 370 70 90 70 60 80 ================= pringle was submitted by Palith Balakrishnabati at pb@toucan.att.com ================= HOW DID pringle CHOOSE CANDIDATES FROM THE SQUARE ? 1) Search control via (nondeterministic) FSM simulation: build a FSM that accepts strings of digits in the grid. Each state of the FSM corresponds to one of the 25 grid positions; a set of states can be stored in a 32-bit machine word. Thus, pringle never has to muck around in the actual grid itself once the FSM is built. (FSM==Finite State Machine) HOW DID pringle TEST A CANDIDATE FOR PRIMALITY ? 2) Prime testing via: a) checks for trivial factors (2,3,5) "built into" FSM traversal b) checks for "small" factors (primes < 200) accomplished in batches via GCD c) checks for large factors by Miller-Rabin strong-psuedo prime testing to bases 2, 3, and 7 3) Loop unrolling and other garden-variety eficiency hacks. SIMPLIFIED SEARCH CONTROL OUTLINE: ========================================================== read grid and build FSM /* map[i] = set of grid positions containing the digit i * for (n = 9; n > 0; --n) { search (fullboard, 0, n) /* search for an n-digit prime in the grid * / if found print and halt } search (states, number, depth) { if (depth == 0) { test number for primality; if prime, we're done return } neighbors = bits adjacent to 1-bits in states /* easily found by a little SHIFTing and ORing * / for (i = 9; i >= 0; --i) { newstates = neighbors & map[i]; if (newstates) search (newstates, number * 10 + i, depth - 1) } ========================================================== This reduces search contol to a small percentage of the overall time. Repeated paths in the grid that form the same number do not slow down the search at all, and I visit candidate primes in strictly decreasing orders, so I can stop when I find the first one. PRIME TESTING The search control is just a small fraction of the time, so I worked at making the prime testing efficient. I build an array mask[n][k] which gives the set of squares from which there is an n-step path through the grid ending in a 1, 3, 7, or 9, with residue -k mod 3. By keeping track of number mod 3 as I go and ANDing in with the mask[][] values, I am assured that I am always going to find at least one number not divisible by 2, 3, or 5 in the current branch of the search tree, and that I never end up at number divisible by 2, 3, or 5. This helps in tricky squares such as the "all 1, 4, 7". To test for divisiblity by 5 > p > 200, I compute GCDs. On a SPARC, where integer division is slow as dogmeat, a well-coded GCD (using, say, the binary algorithm) is about as fast as one divide. But in a single GCD, we can test for divisibility by many primes at once: GCD (n, 7 * 11 * 13 * 17 * 23 * 29) for example, will be 1 unless n is divisible by one of these primes. By multiplying sets of primes less than 200, I can "pack" a set of test integers and do a bunch of divisibility tests with a single GCD. The value 200 was detemined empirically as a point where returns diminished. This table of packed prime products is computed just once before the search begins. For large divisors, I use the probablistic strong pseudo-prime test. Using bases 2, 3, and 7, there is only one SPP less than a billion, and it cannot be the largest prime in the grid: this is because any grid containing this number also contains a larger prime. For example, the number 789201803 can never be the largest prime in the grid, because any grid containing that number also contains the prime 989898989. Almost all of the work is in multiplying x * y mod m. I use a simple by-hand bit-at-a-time multiplication algorithm, with a fully unrolled loop and a few tricks to make it efficient on a SPARC (e.g. testing (x&512) is much cheaper than testing (x&1024). That's about it. There's special-case code to take care of the "funny" grids where all the digits have a common prime divisor. Unfortunately, the version of pringle I submitted got the wrong answer on the test "HOT DOG" because I bungled the code to make sure that I start from only nonzero digits. Rats. This version has that bug fixed. ================================================================= ======================================= fermata ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer fermata 540 60 80 90 60 250 ================= fermata was submitted by Doug McIlroy at doug@research.att.com ================= HOW DID fermata CHOOSE CANDIDATES FROM THE SQUARE ? Paths of length 9 are enumerated recursively in lexicographically decreasing order, then paths of length 8, and so on. No attempt is made to learn anything about shorter paths during the search for longer ones: that was deemed difficult and wasteful. The input to each level of the recursion is a list of all prefixes of a given length and value. Prefixes of the next longer length are considered in decreasing order of their last digit. Prefixes of equal value ending at the same cell are identified, so there cannot be more than 25 prefixes alive at any stage of the recursion. Preprocessing tricks allow paths to be pruned early: (1) Since multidigit primes can't end in any of 0,2,4,5,6,8, no cell needs to be considered from which one of 1,3,7,9 cannot be reached in the right number of steps. A simple dynamic program is run initially to determine for every cell which suffix lengths are possible. Paths are pruned according to that criterion. (2) Nine-digit numbers are divisible by 3 if every digit has the same value mod 3. More generally a path can be pruned if every valid suffix has the same value mod 3 and the prefix has the complementary value mod 3. A simple dynamic program determines what path lengths from each cell have single values mod 3 and what those values are. In the most dramatic instance that I have seen this reduces the number of candidates from 13125 to 3. If the gcd of all entries is not 1, then the problem has a 1-digit answer, which condition is checked early. HOW DID fermata TEST A CANDIDATE FOR PRIMALITY ? First the candidate is tested for divisibility by 3,7,11 by looking up the value mod 3*7*11 in a precomputed characterisitic table of multiples of 3,7,11. A division has to be done only for the first of successive candidates that fall in the same 3*7*11 range. If a number survives this simple test, Fermat's test (if p is prime, then a^(p-1) mod p = 1) is used to cast out composite numbers. For a, I use 2, because the high digits of the first few powers of 2 are 0, which speeds the multiprecise calculation described in the next section. Since the only square eoots of 1 mod p are 1 and p-1, we can first cast out powers of 2 from p-1, sacrificing a tiny bit of discriminating power for speed. Raising to the p'th power is done by the usual log p algorithm. If a number is not identified as composite, it could be a pseudoprime mod p, i.e. a composite that passes. Try again using a different a; four random, pairwise relatively prime, a's are deemed to give strong enough confidence. In fact no pseudoprime candidates have arisen in any system test. ANY OTHER COMMENTS, TRICKS, WHATEVER? Quotients and remainders are computed in 53-bit floating point, which is adequate to handle products of 30 bits (9 digits) times 15 bits, but not 30 bits times 30 bits. One operand of multiplications is thus kept in two 15-bit parts. Even fixed-point mod is calculated in floating point, because the sparc doesn't have a machine divide. Fortunately we never have to find a more than 30-bit integer part of a floating-point number; conversion to int and back is vastly faster than the floor() function. To speed navigation, with each cell is kept lists of neighbor cells classified by value. In one version of the program, "neighbor" was taken to mean a canonical representative of the neighbor cell's equivalence class under the symmetry of the pattern. In the best case this can reduce the number of live prefixes from 25 to 6. Nevertheless I decided to omit this feature because the symmetry-preprocessing code was big (a 1/3 increase in source) and hard to test thoroughly. Even the best-case speedup was modest because the major time-eater -- prime testing -- was unaffected. If The contest features a lot of symmetric problems and I lose by a few percent I'll be sorry. The trick I didn't find was how to overcome the enormous startup cost (about 70 ms) that Solaris apparently imposes on top of the few milliseconds that my program actually takes on most problems. Whoever knows such a trick will get the prize. WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? 1. I program interesting things. 2. I program interesting things. (My interestingly programmed Christmas card is available on request.) 3. I love to program interesting things. ANY IDEAS FOR THE NEXT POTM? crossword puzzles? in particular, word squares are a nice challenge. various flavors: how quickly can you find a square that can be made with a given vocabulary? how many squares can you find in a given time? perhaps with scrabble scoring. perhaps with holes, prizes for minimizing the number of holes, or maximizing lexicgraphically the list of distinct numbers of words of each length. ================================================================= ======================================= totient ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer totient 550 100 140 90 110 110 ================= totient was submitted by Bob Hall at hall@research.att.com ================= HOW DID totient CHOOSE CANDIDATES FROM THE SQUARE ? It first exhaustively computed the set of all length 5 (or less) numbers present in the square. It then iterated through them (greatest to least), and for each, iterated through all those length-5 guys whose first digit is the same as the last digit of the outer guy. For each of these, it "pasted" them together, checked for primality and then finally checked to see if the pasted number was actually in the grid. Of course, for the inner iterations, we skip all 5-digit guys ending in 0, 2, 4, 5, 6, 8, because these can't result in pasted primes. HOW DID totient TEST A CANDIDATE FOR PRIMALITY ? To test n for primality, it first divides it by all primes less than 257 (which it generates initially using the Sieve of Eratosthenes). Since most ns are in the 9 digit range, we need to do more than this. For all numbers surviving that test, totient then tested n for primality by computing w=(2^(n-1) modulo n). If that is not 1, then n is not prime. When a number passed that test (i.e. produced w=1), it computed v=(3234^(n-1) modulo n). If v=1, then my program concluded that n is prime. (This is a variantion on the Miller-Rabin primality test (cf the writeup I submitted separately). You can also look it up in the Cormen/Rivest/Leiserson algorithms book.) Note that in general, this does not guarantee that n is prime, just pretty likely. In fact, I have run some exhaustive searches to show that this is good enough (i.e. it is a guarantee) for all cases that come up in this contest. ANY OTHER COMMENTS, TRICKS, WHATEVER? Of course, totient special-cases the grids having 2,3,5,7,or 11 as their answer. I really wanted to special case the 9-8 and 9-7 grids as well, but Fred disallowed that. I also figured out a really fast way to test whether a number is divisible by 7. It is way cool, running on the order of log log 2^32 ~ 5 operations, compared to log 2^32 ~ 32 operations for actual division. WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? Software agent research (more generally, software engineering and artificial intelligence research). Innermost secret (shhh): AI is dead, long live software agents! ANY IDEAS FOR THE NEXT POTM? How about symbolic algebra? Solving for x, doing integrals, finding closed forms for recurrences, roots of polynomials, stuff like that. ================================================================= ======================================= primetime ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer primetime 560 80 130 90 110 150 ================= primetime was submitted by David Korn at dgk@research.att.com ================= HOW DID primetime CHOOSE CANDIDATES FROM THE SQUARE ? I did a depth first search to compute all 4-digit prefixes. I kept track of paths that I had already computed and pruned. I saved a bit map of for each four digit number indicating which locations the paths terminated. I inverted these 4-digit numbers, and filtered numbers ending in 2,4,5,6,and 8 to get a list of all 4 digit suffixes that were possible. Then I went down the prefixes in order, and found for each digit that connected to a suffix, I tested for primes. HOW DID primetime TEST A CANDIDATE FOR PRIMALITY ? I handled 3's separately by keeping a suffix map. I handled 7-31 by using a gcd algorithm. I used Algorithm P on page 379 of Knuth volume 2 which uses Fermats test to eliminate most other primes. ANY OTHER COMMENTS, TRICKS, WHATEVER? I looked at the input to eliminate boards that only had single digit solutions. I handled the case that all digits where of the form 1mod3 by starting my search at 8 digit numbers. Finally, it looked as if the largest amount of time for most problems was for program invocation and termination. I used system calls directly and called _exit() rather than exit() to speed linking. I ran my ANSI-C program through the program "proto" to get a C++ program since tests indicated that it used cc rather than acc, and my tests indicated about 5% less startup overhead. WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? Techncal Manager of a software reasearch group. Ever heard of ksh? ANY IDEAS FOR THE NEXT POTM? It would be good to find a problem whose solution might be useful if embedded in a library. An example might be something such as audio and/or video compression. It might be useful to define a more complex metric for best solution; for example something that takes both speed and size into consideration. ================================================================= ======================================= =primanujan ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer =primanujan 660 140 100 80 80 260 ================= primanujan was submitted by Vincent Goffin at vjg@mozart.att.com ================= HOW DID primanujan CHOOSE CANDIDATES FROM THE SQUARE ? It starts from 999,999,999 and checks all lesser odd numbers in turn. It finds how many different sequences on the grid can represent the current odd number. This is easier than it sounds because only the end point of a sequence needs to be tracked (if two sequences cross, they only count as one from then on). The end point is where the next digit will attach and that's all we need to know. For efficiency, the pattern of end points on the grid is represented as a 25 bit pattern (stored as an int): each bit is a grid position and a bit is lit if it is an end point, otherwise not. As long as the pattern is > 0, there is at least one legal sequence that generates the number -- and in the lowest level of looping can often be done in a single bit-logical operation between ints. The sequence grows using recursive calls so that if we hit a snag and the end point pattern evaluates to zero, we simply pop one level of recursion and continue from there. For the last two digits the algorithm changes gear and uses a sieve to skip multiples of 2, 3, 5, and 7. Matching the two gears is a bit tricky. Once the last digit is reached, the number is odd, not a multiple of 3, 5 or 7, is represented by a legal sequence (mostly unknown), and is the largest one remaining. It then gets tested for primality. HOW DID primanujan TEST A CANDIDATE FOR PRIMALITY ? I started with the only method I knew: dividing by all primes less than the square root of the number. Profiling (using quantify) the code showed most time spent in remainder calculations. Even with clever short cuts this remained the bottleneck. An inspired trip to Barnes & Noble got me a copy of Neal Koblitz' "A Course in Number Theory and Cryptography" and I learned that there are better ways to determine primality. I used his "strong pseudo-prime algorithm". ANY OTHER COMMENTS, TRICKS, WHATEVER? I learned more about arithmetic in a few weeks than I had in many years! WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? I work in product support in the Software Technology Center (BL-5911). For fun? but of course, the POTM! ANY IDEAS FOR THE NEXT POTM? How about packing same size spheres in a given volume of n-dimensional space? It's a well known problem (Kepler problem in 3d) and unsolved for even moderate n, I think. The program with the most spheres, or the best packing ratio, wins. It would print out the sphere center coordinates and a "verifier program" could check that the spheres do not overlap. ================================================================= ======================================= =quickprime ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer =quickprime 710 90 120 90 120 290 ================= quickprime was submitted by Bill Tanenbaum at tan@intgp1.att.com ================= HOW DID quickprime CHOOSE CANDIDATES FROM THE SQUARE ? Except for special cases, it simply chose all numbers, largest first, except it demanded that they end in 1, 3, 7, or 9. It was careful to focus on the numbers rather than the paths through the grid to find them. By setting up all sorts of adjacency matrices, I was able to loop through all possible numbers, largest first, rather quickly. It took a LOT of work to set this up. Special cases covered with special code: All 0, 2, 4, 6, and 8, print 2 All 0, 2, 4, 6, 8, and 5, print 5 All 0 and 7, print 7 All 0, 3, 6, and 9, print 3 All 1's (prime test only 1111111, 11111, and 11) Special cases covered with minor modifications to the general algorithm. All 1, 4, and 7 : start with eight digits (no 9 digit solutions) No 1's or 7's : (number must end in 3 or 9, (both 0 mod 3), so can determine at second to last digit if candidates must be multiple of 3. No 3's or 9's : (number must end in 1 or 7, (both 1 mod 3), so can determine at second to last digit if candidates must be multiple of 3. HOW DID quickprime TEST A CANDIDATE FOR PRIMALITY ? Explicitly checked for divisibility by primes up to 120 (except 2 and 5) (derived, of course). After that, used Fermat's theorem to base 2 only! 2^p == 2 mod p. This is actually faster than just using Fermat's theorem directly, as you find composites with small factors quickly. A pseudoprime to base 2 without a prime factor of less than 120 would have tripped me up! I deliberately took that risk to try to win! ANY OTHER COMMENTS, TRICKS, WHATEVER? Too bad I missed getting 7 on this case: 04040 00000 00000 00000 70707 The bug was, that the general algorithm (excluding the obvious special cases above) failed to search one digit candidates. I did not realize this, and was surprised to discover this bug. This was a bug, not a deliberate omission. WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? Write software, mostly. ================================================================= ======================================= vprime ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer vprime 940 80 100 140 90 530 ================= vprime was submitted by Phong Vo at kpv@research.att.com ================= HOW DID vprime CHOOSE CANDIDATES FROM THE SQUARE ? Vprime checks all possible values in a square starting from the largest value. The basic strategy is to compute all values that can be prefices of length 5, 4, 3, 2, 1 and where they end on the board. Similarly, compute all values that can be suffices of length 4 and where they start. Then values are generated by matching proper prefix and suffix values. A (prefix,suffix) pair of values match if some ending digit of the prefix value is adjacent to some starting digit of a suffix value. Due to the small board size 5x5, a 32-bit mask is enough to keep track of all ending (starting) positions for each prefix (suffix) value. Adjacency can then be tested by an & operation. To focus the search, prefix values are generated in groups where all members of a group share the same first two digits. Two different strategies are used to generate suffix values. If there are many repeated digits, then all suffices of length 4 are generated at once. Otherwise, they are generated as needed. HOW DID vprime TEST A CANDIDATE FOR PRIMALITY ? Suffices divisible by 2 and 5 are rejected early. Then values are rejected by divisibility by 3. Divisibility by small primes in the range [7,29] is checked using a binary GCD algorithm (Knuth Vol. 3). After that, the Miller-Rabin probabilistic prime testing method with witnesses 3, 5 and 7 is used to test for compositeness (Intro to Algorithms by Cormen, Leiserson and Rivest). ANY OTHER COMMENTS, TRICKS, WHATEVER? WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? I am in the Software Engineering Research department in MH. Some of the popular software packages that I am either fully or partially responsible for are the malloc and curses libraries in System V, sfio, the Safe/Fast IO library to replace stdio, IFS/Easel, a language for writing menu and form systems, and DAG/DOT, a program to draw directed graphs. For fun, I do landscaping, read science fictions, and sometimes play around with algorithms and data structures, ANY IDEAS FOR THE NEXT POTM? Dave Korn and I talked a little about this. It looks like potm is a good way to attract good programmers to solve interesting problems but it's unfortunate that much of this effort is not usable in any practical software. It would be nice if you can find some problems that would result in some interesting software that we can benefit from later. Just so that this is not just a vacuous statement, the sfio library has a pair of functions sfgetd/sfputd that read and write double values in a (semi-)portable form. This is important for applications that run on a network of heterogeneous hardwares and need to communicate values across machines. I wrote this based on the frexp/ldexp/modf routines but I am unhappy because they are not quite portable (different mantissa problems) and they can be slow. So a problem is to find a way to encode/decode such double values using a minimal number of bytes and such that the encoded bytes can be transported across machine boundaries without loss of accuracy or minimal loss of accuracy in the case when sizeof and mantissa are different. This problem may be a little boring but it sure has great practical value for me. Maybe you could also solicite similar practical problems on the net. ================================================================= ======================================= primal_scream ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer primal_scream 1040 120 400 190 180 150 ================= primal_scream was submitted by David Roe at roe@hogpb.att.com ================= HOW DID primal_scream CHOOSE CANDIDATES FROM THE SQUARE ? 1) Set up a table of pointers to adjacent cells in the square 2) Create a stack of partial integers of length up to 9, starting from strings of length 1 3) Find the largest integer, regardless of primality, first. Sort the stack by size of the partial integers 4) Add digits from adjacent cells to the end of the largest integer on the stack 5) (speed) Trash the partial integer if it cannot get to 1, 3, 7, or 9 by the 9th digit. 6) (speed) Keep track of parity (mod 3). Trash the partial integer if parity will be a problem, and it can't get to 1, 3, 7, or 9 with a change in parity (mod 3) by the 9th digit. HOW DID primal_scream TEST A CANDIDATE FOR PRIMALITY ? 1) sieve to find all primes less than 31623. 2) divide candidate primes by list of primes in the sieve. It turns out not much CPU time was spent actually evaluating primes. Repeatedly sorting the stack took more CPU time. ANY OTHER COMMENTS, TRICKS, WHATEVER? By testing on many computer generated squares, I found some interesting pathological cases. Then I tried to speed up those cases. Tricks 5) and 6) above helped a lot. Test for special cases by getting a histogram of digits present in the square. Re-writing the qsort() to find only instances of the largest integer on the stack as needed, might have saved time, but I didn't do it. WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? Speech recognition. ANY IDEAS FOR THE NEXT POTM? Anything, as long as the tiebreaker is NOT the number of characters. ================================================================= ======================================= prime8 ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer prime8 1040 90 120 80 90 660 ================= prime8 was submitted by Stephan Zdancewic at sz24+@andrew.cmu.edu ================= HOW DID prime8 CHOOSE CANDIDATES FROM THE SQUARE ? prime8 generates numbers from the square starting with the largest and counting backwards by maintaining a bit vector that represents all of the possible neighbors from the current square(s). It then ANDs this vector with the locations of the next largest digit (calculated once at the beginning of the program) to determine the next set of squares. This is done recursively, and the value of the number currently being generated is kept. In this way, all possible routes through the square that can form a number are checked simultaneosly. HOW DID prime8 TEST A CANDIDATE FOR PRIMALITY ? I used Fermat's little theorem with several bases to determine whether a number was probably prime. Sufficient bases were used to make it very unlikely that the number was a strong pseudoprime. No deterministic prime test was done (ie prime8 will fail if a pseudoprime is the largest number found) ANY OTHER COMMENTS, TRICKS, WHATEVER? WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? I'm a Junior at Carnegie Mellon University ================================================================= ======================================= ptime ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer ptime 1080 180 220 90 110 480 ================= ptime was submitted by Bob Ashenfelter at ash@hotlg.att.com ================= HOW DID ptime CHOOSE CANDIDATES FROM THE SQUARE ? Candidates are generated in decreasing order from the digits in the square. To limit the number of bogus candidates, lists of all digits neighboring each digit are generated beforehand. Lists of all digits neighboring pairs of digits are generated as needed. The first and last digits are diff- erent. The first can be any digit found in the square except 0. The last can be only chosen from 1, 3, 7, 9 (if in the square); more lists of neigh- bors are generated containing only these digits. So, the procedure is as follows. The most significant digit is chosen from all the digits in the square, largest first. For each most-signifi- cant digit, the second digit is chosen from those that are neighbors of the first somewhere in the square, again largest first. Each subsequent digit is chosen similarly, but considering the previous two digits. The least significant digit is chosen considering only one previous digit using the special lists that exclude even digits and 5. If no 9-digit candidate is accepted, then 8, 7, ..., 1-digit candidates are generated. The candidates are generated using the digits in the square rather than the positions in the square because there are fewer digits (<=10) than positions (25) and this ratio is compounded by the number of significant digits in the answer. However, depending on the square, it may generate a lot of bogus candidates that are not actually in the square. Therefore a second procedure is used to weed out the candidates that are not in the square. This procedure generates lists of valid square positions for each significant digit of the candidate. Starting with the most significant digit, all positions which contain the correct digit and are neighbors of a valid previous position are put in the valid list for the next most significant digit. If at any level there are no valid positions then the candidate is rejected. The two procedures communicate with each other to avoid doing useless work. For example, if the validity check fails after considering the three most significant digits, the candidate generator is told to skip all remaining candidates with these three significant digits. Likewise, if after a candidate has been rejected, the next candidate shares some most signif- cant digits with the previous one, the validity check jumps into the middle knowing that the previous work still applies to the upper digits. HOW DID ptime TEST A CANDIDATE FOR PRIMALITY ? This is a multistep process. The first step is to avoid generating any candidates which are divisible by 2 or 5. This is described above. The second step is to make a "quickie" check between the candidate generator and the validity checker. This tests only factors 3 and 7 and the next several prime factors. (I think I left this at 12 more--the average run time is extremely unsensitive to how many.) The quickie prime check weeds out a lot of candidates. For the tougher squares there may be thousands or tens of thousands of candidates larger than the true answer but only a few hundred get by this step. The final prime check is performed on those few (maybe a dozen) candidates that get past both the quickie prime test and the square validity test. It uses an array of 48 differences between numbers that are not divisible by 2, 3, 5, or 7 to generate and test possible factors up to the square root of the number being tested. This procedure was distilled from the source code for the UNIX utility "factor". For a 9-digit number, about half the possible factors are non-prime and thus superfluous, but the cost to generate a more efficient list rapidly exceeds the benefit. In fact, the full prime check is used so sparingly that all odd numbers up to the square root could be used as possible factors (multiplying the number of trial factors by another 2-1/2). Of course, the array of 48 factor differences looks suspiciously like a list of prime differences and thus can't be explicitly initialized as it is in factor.c. I checked with the POTM-Meister and he disallowed it even though it contains no entry greater than 10 and is based only on primes less than 11: "Sounds like a weasel to me...". It's no big deal to compute it. The first candidate to get past the quickie prime test and the square validity test and the final prime test is the answer. ANY OTHER COMMENTS, TRICKS, WHATEVER? Although the problem inherently involves only integers, numerical calc- ulations (such as testing prime factors) should be done with double- precision floating point numbers rather than integers. I was surprised to find that floating point arithmetic executes twice as fast as integer arithmetic! Of course, its all done in hardware. It may seem that all squares have either a 9-digit answer or a 1-digit answer (or the answer is 11, but this won't be used) and all the 1-digit cases can be detected and treated separately so the main procedure needs only to be capable of finding 9-digit answers. But how do you know that there isn't some obscure square with a smaller answer? If our problem had been to find the largest prime of no more than 7 digits, there are squares with a 3-digit answer. Therefore it is important that the pro- cedure be able to find answers of all lengths (including 1), and to check that it does it should be tested with the special cases turned off. In fact, there IS a square with a 1-digit answer which is not readily detect- able as a special case. When I found it, just a few days before the deadline, ptime put out an answer that was both not prime and not in the square! I sent the square to Fred along with my corrected program and he said that he "really" liked it... WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? Circuit design. Bicycling, grow orchids, travel. Are you kidding??? That's an oxymoron! If I tell, it's not a secret. ANY IDEAS FOR THE NEXT POTM? Well, yes. Many years ago I came across a problem about putting pieces on a chessboard which I couldn't solve so I wrote a computer program to do it (there were lots of solutions!). Although the resulting program was quite small, the logic was very tricky, or should I say sticky, and the program took a couple of hours to execute (late at night on a VAX). ================================================================= ======================================= primary ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer primary 1400 250 180 90 100 780 ================= primary was submitted by Warren Montgomery at warren@iwrmv1.ih.att.com ================= HOW DID primary CHOOSE CANDIDATES FROM THE SQUARE: A recursive search, looking for the biggest numbers first digit by digit. Primary used a bitmap to represent all points in the square where a sequence ending in the current digit could be found, and then tried to find the next digit adjacent to each, thus finding each candidate only once. HOW DID primary TEST A CANDIDATE FOR PRIMALITY Built a table of primes less than the square root of 999999999 using standard methods and tested by exhaustive division (over 3000 candidates to try). ANY OTHER COMMENTS, TRICKS, WHATEVER? Other than the bitmap strategy, which was my biggest breakthrough, being careful in building the prime map (e.g. exploiting the fact that of each 6 integers, only 2 are potential primes), and realizing that Sparcs don't have integer divide (so the prime test was done with floating point divisions to avoid an expensive software emulation of the % operator). I also test explicitly for cases where all digits are even, all are multiples or 3, or all multiples of 5. WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? I'm a technical manager of a systems engineering group, for fun, I get as far from technology as possible (ski slopes, coral reefs, golf courses, back country travel, etc. ================================================================= ======================================= the_pump ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer the_pump 1430 230 360 110 140 590 ================= the_pump was submitted by Michael Chin at mchin@bubba.att.com ================= HOW DID the_pump CHOOSE CANDIDATES FROM THE SQUARE ? Candidates were chosen by making up a set of legal three digit numbers and marking where their heads and tails were in bit fields. Making a nine digit number was performed by concatenating the four three digit numbers (they included three one-digit overlaps) whenever their heads and tails matched. This generates additional cases where the entire nine digit number is not reachable. After checking for primality, a separate algorithm is used to determine whether the entire number was reachable. HOW DID the_pump TEST A CANDIDATE FOR PRIMALITY ? Prime numbers were calculated using the sieve method. Additional speed was obtained by noting the fact that prime numbers form rings as long as the numbers are prime w.r.t each other (given true). Therefore, I made a list of all the odd numbers, determined the prime numbers in the first (3 * 5 * 7) odd numbers. I then memcopy'd that initial pattern over all the prime number. All succeeding numbers were then eliminated by taking the next prime and marking every multiple of that prime starting from that prime squared. ANY OTHER COMMENTS, TRICKS, WHATEVER? It was fun playing with operator overloading in C++. For me, it was fun just to fool around with C++. WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? I spent way too much time on this. ANY IDEAS FOR THE NEXT POTM? MIT's Technology Review has a neat little puzzle every year. (Actually every issue has a short puzzle section). Anyway, the objective is to take the digits of the next year (i.e. 1995) and generate all the nubmers from 1 to 100 from them using only the operations (+, -, *, /, ^). Grouping is allowed (i.e. 99 - 15 is legal). Parentheses are allowed. Additional points are awarded when you get the digits in the right order (i.e. 1 + 9 + 9 + 5). Also points are awarded for using the fewest number of operators. ================================================================= ======================================= squambulator ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer squambulator 1510 80 140 80 90 1120 ================= squambulator was submitted by Lew Mammel at lew@uscbu.ih.att.com ================= HOW DID squambulator CHOOSE CANDIDATES FROM THE SQUARE ? It used a bit mask to find all digits ( or positions ) which could be the next digit of the largest untried number. This way the possible numbers were tested in strictly descending order - an optimal strategy. HOW DID squambulator TEST A CANDIDATE FOR PRIMALITY ? It used Fermat's "little theorem" I got the hint because someone named their program "fermata", but I programed my test pretty much from scratch. I did browse a little in the book store in some book on algorithms to see if I was on the right track. I wrote my own modular exponentiation routine, which looks like a kindergartner wrote it. ANY OTHER COMMENTS, TRICKS, WHATEVER? As usual, I dropped the ball. I was a few lines of code away from picking up the diablolical "7" , but when I thought about these possiblities I decided .... "Naaaaaaaaaaaahhhhhh". I coulda been a contender. WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? I'll never tell how many hours I spent on this! ( I don't even wnat to know myself. ) ANY IDEAS FOR THE NEXT POTM? Half serious - same puzzle with 10 digits and 6 by 6. ================================================================= ======================================= primal_duck ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer primal_duck 1700 300 330 100 150 820 ================= primal_duck was submitted by Mike Gagle at bl_indpls!gagle@inuxs.att.com ================= HOW DID primal_duck CHOOSE CANDIDATES FROM THE SQUARE ? For starters, I represented the square using a 10 element vector and a 9 by 25 element array. Elements of the vector corresponded to the digits 0 - 9 and each element of the vector was a bitmap with a bit set for each cell in the original square which contained that digit. The array contained bitmaps for each of the 25 cells in the square for each of the nine digits of the number being generated. These bitmaps had bits set for each possible neighbor of that cell. For the last digit generated, the 'neighbor' bit was only set for cells which really were neighbors and which could be the last digit of a prime (1,3,7,9). This information was then propogated into the neighbors list for the fourth- through second-last digits of the number being generated to limit the trial space (given the nature of the problem, the first five elements of the array didn't vary and were initialized at compile time). Given these data structure, the routine started with the bitmask corresponding the all cells with 9s and examined all of their neighbors. All neighbors with 9s (then 8s, 7s ... 0s) were recursively examined. When a number of the correct length had been generated it was tested to see if it was a prime. HOW DID primal_duck TEST A CANDIDATE FOR PRIMALITY ? Nothing very special here. I did a Seive of Erastothenes (sp?) to find the primes less than 31622 (which is roughly the square root of 9,999,999). ANY OTHER COMMENTS, TRICKS, WHATEVER? I created a bitmask of the input digits and checked for only even numbers, only {0, 3, 6, 9} and only {0, 7} for fast tests of semi-degenerate squares. I orginally had code to look for patterns of digits which couldn't be primes (such as <0,x,y,x,y,x,y,x,y> or but it seemed like this violated the Prime Directive on A-Priori Knowledge of primes greater than 11 so it took it back out. WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? To earn an income, I'm a contractor for the labs. I have worked on data communications things like an ISDN home controller project and salvaging the data comm part of the VideoPhone 2500 while at the Labs and have done database and full text retrieval work when not working for AT&T. ================================================================= ======================================= enterprise ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer enterprise 1760 400 310 260 200 590 ================= enterprise was submitted by Marc Unangst Amy McGovern at mju+@cmu.edu ================= HOW DID enterprise CHOOSE CANDIDATES FROM THE SQUARE ? We used a fairly simple iterative algorithm. We first found the largest number by finding the largest digit in the square, finding its largest neighbor, etc., and storing the digits in an array. This number was then tested for primality. If it wasn't prime, then our algorithm backed off and found the next-largest digit for the least-significant place. If it couldn't find a smaller number there, it backed off another place and found the next-largest digit for that place, followed by the largest neighbor in the next place, etc. This algorithm continues, trying successively smaller numbers, until it finds a prime. There was also special-case code in the program that tested for a square solely consisting of multiples of 2, multiples of 3, multiples of 5, or multiples of 7, and immediately printed the correct result for these squares. HOW DID enterprise TEST A CANDIDATE FOR PRIMALITY ? We used Miller's probabilistic test, with up to 10 randomly-generated witness numbers. To ensure accurate results we probably should have backed this up with a deterministic test if Miller's test indicated that the number was probably prime, but we've yet to see a number which passes our implementation of Miller's test but isn't actually prime. ANY OTHER COMMENTS, TRICKS, WHATEVER? Not really. I think our program is faster than Daroohahaha, so even if we don't win the contest I'll still feel good, since Daroohahaha was written by our professor. :-) WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? For a living: I'm a sophomore ECE (electrical & computer engineering) student at Carnegie Mellon, with a CS minor. My partner, Amy McGovern, is a junior Math/CS major at Carnegie Mellon. I also work part-time as a systems programmer for the School of Computer Science. Amy works part-time as a programmer for a user-interface research group at CMU, the Amulet Group. For fun: Volleyball. Star Trek. (Yes, both of us.) ANY IDEAS FOR THE NEXT POTM? Optimal solutions for the Towers of Hanoi problem, with a number of pegs greater than 3. ================================================================= ======================================= prime ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer primeval 410 90 90 70 80 80 vprime 940 80 100 140 90 530 primer 3700 560 330 100 110 2600 potm_prime 15730 4110 1200 120 310 9990 goodprimes 70300 30710 17440 4150 7370 10630 primetime 560 80 130 90 110 150 =quickprime 710 90 120 90 120 290 prime8 1040 90 120 80 90 660 prime 1890 330 410 250 230 670 primeRib 20400 410 1470 1480 1600 15440 =usdaprime 22040 6690 240 150 190 14770 primecut 40200 14870 670 200 960 23500 gr_primes_id 51640 13050 8020 1110 800 28660 primevil 153230 140 810 40710 48740 62830 primesquare 412400 225780 230 19220 109210 57960 ================================================================= ======================================= square-nt ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer square-nt 2000 110 100 170 150 1470 ================= square-nt was submitted by Brian Beuning at bgb@psp.att.com ================= HOW DID square-nt CHOOSE CANDIDATES FROM THE SQUARE ? It does a depth first search, selecting the largest digits first. At the top level, it just does for( k = 9; k >= 1; k-- ) and finds all squares with a value of 'k'. Then it does the depth first search on that square, picking the largest neighbors of each square first. To make it easier to find the largest neighor, square-nt makes a data structure for each square that for each square includes a list of neighbors sorted by value. It also does a couple of types of pruning of the search. The simplest is if we have found a prime, if we are looking down a leg of the search tree that is less that the answer we found we don't need to search this leg any more. It uses an array max_at_depth[10] which is subscripted by the level of the search. This array starts out with 0, and is filled in when we find an answer. Then the search checks the value for the level the search is presently at to decide if this leg of the search can not find an answer bigger that the answer we already have. (This is one area I thought could be improved, if the code always only looked at the biggest number possible first it wouldn't need to above pruning and could not waste time looking down search legs that might find an answer that is not the largest.) The second type of pruning I called "been here before", consider this partial input square 9 0 1 0 0 0 2 0 3 starting at the '9', there are two ways to get to 900, the first way is by going right then down, the second way is by going down then right. The depth first search by itself would blindly search both of these legs even though they will find (or not find) all of the same results. The "been here before" check looks for this case and prunes the search to save this redundant work. HOW DID square-nt TEST A CANDIDATE FOR PRIMALITY ? The Sparc does not have a divide instruction, so square-nt goes to great lengths to do very few divisions. The tests for multiples of 2 and 5 are handled by checking the last digit in the number. The test for multiples of 3 are handled by keeping a sum of the digits, and check if this sum is a multiple of three (by a simple table lookup). For the numbers that are not multiples of 2, 3, 5, it does trial division for the primes up to 50. This eliminates lots of numbers. If a number passes all of these tests, then I use a "strong pseudo prime" test on it. The strong pseudo prime test is very similar to the fermat test which uses ( a^n % n == 1 ). The trick is that since 'n' is close to being a 32 bit number, the intermediate results can overflow so it can not use C operators. It turns out that the same number can get tested for primality more than once during a depth first search. So square-nt has a hash table to keep track of what number have been tested for primality, and will only do the above (expensive) test once for any given number. ANY OTHER COMMENTS, TRICKS, WHATEVER? The tools on the sun for tuning performance are limited to the PC-smapling type tools. Since the entries are ran pretty fast, PC-sampling isn't much help for tuning. I ended up using a MIPS machine with its pixie tool for some tuning. The pixie tool rewrites an object file after running this new object file, it gives precise instruction counts for every block of code (and function). WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? For a living, I work on the A-I-Net products. Mainly working with making a programming language used by our customers to defined services for running on the SCN and SCP. For fun, I got a copy of Civilization as a present. It is lots of fun. Also one of the reasons I jumped into this POTM, is I have done some fooling around with finding factors of Mersenne primes. ANY IDEAS FOR THE NEXT POTM? How about something where the programs compete against each other. One makes a move, an arbiter tells the first move to the second contestant, it makes a reply, the arbiter tells the first program the reply, and so on until a winner is found. Like corewars, or there was something a while back about programs that showed that cooperation was a winning strategy. ================================================================= ======================================= priem ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer priem 2110 90 340 360 130 1190 ================= priem was submitted by Stan Peijffers at hvgtw!hvssa01!speijffe@attmail.att.com ================= HOW DID priem CHOOSE CANDIDATES FROM THE SQUARE ? *************************************************************** The search algorithm is a recursive one by expanding a set of square nodes. It generates the candidate primes in decreasing order (highest first). There is no sorting and expansions are only executed when needed. This is how it works : Before beginning the recursive expansion algorithm, the square information is represented as a 2-dimensional array (10 x 10), with the first dimension representing a "from" digit value and the second dimension representing a "to" digit value. Every element in this array contains a set of bitmap pairs (integers), where each bit represents a node in the square (nodes 1 to 25). There is a set of bitmap pair for every digit in the square (with a bitmap pair for every adjacent value) : -the first bitmap contains one bit showing the node in the square for this digit (with the "from" digit value). -the second bitmap contains a set of bits, each bit showing the nodes in the square for the "to" digit values. The search algoritm starts off by constructing a bitmap representing the nodes of the digits with the highest value digit. This bitmap is fed to the recursive expansion algoritm. Each expansion consists in accessing the above constructed array with the value of the digit and successively map the current bitmap onto the "first" bitmaps. When there is a match, the bits of the "second" bitmap are retained in a newly constructed bitmap, which is passed on to the next level of recursion. The recursive function "expand" has the following parameters : expand (level, bitmap, digit, val) where - level : the current level of recursion - bitmap : the current bitmap showing all nodes which are being expanded - digit : the current digit value. - val : the current value of the number. HOW DID priem TEST A CANDIDATE FOR PRIMALITY ? *************************************************************** - Execute the "mod" operation with all possible divisors up to sqrt of the prime candidate, skipping all multiples of 2,3 and 5. - The result of the mod operation (z = x % y) is marked in a large array (or rather a set of arrays). Indeed, x-z is a multiple of y, therefore it is not necessary to check a later candidate prime with this value. (Before invoking the prime testing algorithm this array is checked). NOTE : I have considered marking all values x - z -n.y but this turned out to be too much overhead. ANY OTHER COMMENTS, TRICKS, WHATEVER? *************************************************************** I had what I believed to be a rather nice algoritm to perform the modulo operation only with prime numbers. And this effectively increased the speed of the algorithm with about 20-30% on my PC (where I initially developed the algoritm). Unfortunately the same "improvment" on the SUN slowed it down with about 20-30%. So I left it out. Anyway this was the algorithm : An array should be maintained with an entry for each divisor (1 -> 32K). A "0" entry means that this is a prime number. A non-zero entry means that this is a non-prime number and the value is the value of the lowest prime that divides this non-prime. This array is constructed while looping thru the divisors and performing the modulo operations. It makes use of an auxiliary array in which for each prime 2 pieces of information are maintained : the next prime, and the increment to reach the next prime. As we loop thru the divisors (say "y") the following actions are performed : - if y is a prime, then mark y*y as a non-prime in the array (with value y). Update the entry in the auxiliary array for the previous prime (next and increment to this new prime). Perform the mod operation. - if y is a non-prime (with value z which is a prime) then get the increment to the next prime from the auxiliary array (say value d), and mark y + z*d as a non-prime. Update the auxiliary array to have the prime z now point to the next higher prime in the chain (next and increment). Do not perform the mod operation. In doing so mod operations are only performed on primes. A high-water mark on the y values covered so far should be maintained, because clearly this should be done only once per y value. ================================================================= ======================================= symphony ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer symphony 2250 80 230 80 120 1740 ================= symphony was submitted by Gerie Alards at galards@intgp1.att.com ================= HOW DID symphony CHOOSE CANDIDATES FROM THE SQUARE ? HOW DID symphony TEST A CANDIDATE FOR PRIMALITY ? Instead of using the expensive % operator the / operator was used. Its 50% less expensive! if (n % i == 0) { no prime } can be replaced by: m = (double) n; if ((long) t == (t= (double) m / i)) { no prime } (refer to symphony.c) ANY OTHER COMMENTS, TRICKS, WHATEVER? WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? I joined AT&T Network Systems Netherlands in '89 as software engineer. My areas of interest are software development automation and neural networks. ANY IDEAS FOR THE NEXT POTM? Neural networks can be a good next candidate. ================================================================= ======================================= =primate ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer =primate 2520 130 330 110 130 1820 ================= primate was submitted by Debbie Brown at dwb@arch4.att.com ================= HOW DID primate CHOOSE CANDIDATES FROM THE SQUARE ? My original approach: I had a data structure constructed at initialization time that stored the "next moves" from each location in the square. Each invocation of the procedure is called with a value computed so far and a list of positions in the square at which that val can terminate. At each call to the procedure, I check each digit (in decreasing order from 9, ..., 0) to see if that digit can be reached from any of the positions in my list. If so, I add this digit to the right-hand side of the previous val, and recalculate the list of positions. When I've generated a 9-digit value, I check to see if it is prime. I repeat this procedure for 8-digits, 7-digits, etc. Unfortunately, instead of strictly sticking to this general approach, I tried to put in some special cases - which did me in. tried to take into account some special cases - which did me in HOW DID primate TEST A CANDIDATE FOR PRIMALITY ? At initialization, I used the sieve of Erasthothenes (is that how you spell it), to generate all the primes less than or equal to the square root of one billion. When I had a candidate from the square, I kept checking to see if one it was divisible by one of the primes I had generated. ================================================================= ======================================= odd ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer odd 3390 90 490 100 120 2590 ================================================================= ======================================= primer ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer primer 3700 560 330 100 110 2600 ================================================================= ======================================= goldbach ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer goldbach 7320 1100 250 140 150 5680 ================= goldbach was submitted by Dave Lynch at dfl@esun.att.com ================= HOW DID goldbach CHOOSE CANDIDATES FROM THE SQUARE ? Created a matrix indicating which digits are adjacent to each digit. Used this matrix to generate a decreasing list of possible candidates. At each step, checked whether the candidate could actually be constructed from the original 5x5 grid. HOW DID goldbach TEST A CANDIDATE FOR PRIMALITY ? Constructed a list of prime numbers <= sqrt(largest candidate), using Sieve of Eratosthenes. Divided candidate by each prime and checked whether the integer quotient equaled the floating point quotient. ANY OTHER COMMENTS, TRICKS, WHATEVER? Screened out trivial cases up front. A conjecture concerning prime numbers was proposed by Christian Goldbach during the 18th century and (as far as I know) still remains unsolved. WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? Develop private data network design software. ================================================================= ======================================= primoggle ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer primoggle 7400 4210 470 250 780 1690 ================= primoggle was submitted by Ravi Sharma at sharma@mozart.att.com ================= HOW DID primoggle CHOOSE CANDIDATES FROM THE SQUARE ? primoggle built from the input matrix a scan-list for each (i,j) which is a depth-first generation of numbers, but only 3-levels deep. After sorting the scan-list (delayed sorting as much as possible), it then performs a concatenation function by repeatedly joining numbers from the scan-list to generate a 9-digit number which is tested for primality. The tail section of the concatenation comes from a separate scanned-list which is filtered for prime-digits in the final position (i.e., only 1, 3, 7, 9 were allowed), so obvious composites were eliminated (evens, and multiples of 5). HOW DID primoggle TEST A CANDIDATE FOR PRIMALITY ? A sieve algorithm was used to precompute primes up to 31623 (which is sqrt(10^9)). The sieve only need to compute multiples of up to 177 (sqrt(31623)). The test for primality did the standard thing by attempting to divide primes (less than the sqrt of the candidate) into the candidate. A sqrt table was used to avoid making the call to the sqrt function. ANY OTHER COMMENTS, TRICKS, WHATEVER? Attempted performance tweaks were to filter the scanned-list to eliminate duplicates. Bit arrays were used to keep track of the precomputed primes, duplicates in the scanned-list, and previously tested candidates in primality testing. WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? In my normal life, I work for the Software Technology Center in building the SDE (Software Development Environment). As a current life, I'm supporting the AT&T Network Notes project with some of my Lotus Notes, development, and integration experience. For fun, I enjoy time with my wife & two daughters -- enough to keep me busy and sane away from the POTM. My innermost secret wouldn't be one if I told you; besides I'd have to encode a way to eliminate any reader of the secret and I'm not quite finished testing that mechanism yet :-). ================================================================= ======================================= Labyrinth ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer Labyrinth 9200 1270 780 230 250 6670 ================================================================= ======================================= srch4prm ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer srch4prm 11070 520 8820 130 120 1480 ================= srch4prm was submitted by Dale Harris at attbl!iesde!om7@att.com ================= HOW DID srch4prm CHOOSE CANDIDATES FROM THE SQUARE ? Rather than searching through the squares for candidate paths, I rather searched through the possible values, from high to low. I did a parallel search through all squares that gave a given value. Thus: search with all 1st sqaures with a value of (9,8,...) search will all 2nd squares with a value of (9,8,...) ... I used a bit map to indicate the set of squares I was on. It was lucky that there 25 sqaures, ie less than 32, so that a single unsigned long could represent the set of squares that could give the accumulated value being examined so far. I did use next square pointers to travers the square, but I traversed all paths in parallel that had the highest value so far. HOW DID srch4prm TEST A CANDIDATE FOR PRIMALITY ? Basically by modular division of all primes in a list. The list of primes stopped at the square root of the maximum value. And I also stopped testing when the prime used was greated than the sqaure root of the value being tested for being prime. I may have saved some time by creating a composite of small primes, the product of which is less than the square root of the maximum value. The cost was calls to memcpy() and the savings was less mod divides. This probable saved most when creating my list of test primes. ANY OTHER COMMENTS, TRICKS, WHATEVER? The idea of searching for values, not paths, from high to low, allowed me to stop the search as soon as I found a prime, knowing that I had found the highest prime. This thus saved many calls to "isprime", and thus many mod divides. When constructing the list of test primes, I was able to save some time by using a different algorithm for prime testing. I created a list of primes in the range of the square root of the square root of the maximum value. I then took all odd multiplications of those primes to set a "can't be prime" flag in an array the size of the square root of max value. I could then go throgh that array and know that any odd index which did NOT have a "can't be prime" flag set, MUST be prime. Thus, I generated the prime test list via a series of adds, rather than mod divides, which ended up costing less time. WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? My job is C and C++ programming on some tools that compile a high level language into database operations. For fun, I play video games, I write letters and books, and I go dancing at night clubs. The writing is not so much "fun" as it is work. In fact, the night club thing is also kindof work, since it was research work for my second book. I authored the book "The Quest for Love" under the pen name of "Dave Erickson". Its ISBN is 289-7059-02-8. I am also involved in the men's movement and attend and speak at conferences on gender issues. For example, in early Feb '95 I will be at the "International Men's Day" conference in Toronto and speak on subjects related to my book. ( Organizer: Tom Oaster, PO Box 10033, Kansas City, MO 64171. ) ================================================================= ======================================= potm_prime ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer potm_prime 15730 4110 1200 120 310 9990 ================================================================= ======================================= primeRib ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer primeRib 20400 410 1470 1480 1600 15440 ================= primeRib was submitted by Glenn Bradford at gmb@ams.hr.att.com ================= HOW DID primeRib CHOOSE CANDIDATES FROM THE SQUARE ? It did a recursive walk starting from the highest digits and worked downward. First it checked for trick grids, then it searched for 9 digit solutions, then 8, 7, ... Standard stuff. HOW DID primeRib TEST A CANDIDATE FOR PRIMALITY ? Very slowly by dividing all the prime factors up to the square root of the candidate. If HOT DOG hadn't knocked me out, this would have. I didn't realize this was my bottleneck until the 11th hour (literally). Up until then I had been optimizing my program with better pruning techniques. ANY OTHER COMMENTS, TRICKS, WHATEVER? I recognized {1,4,7} and coded for it. I also kept track of partial paths that had been searched already at every location on the grid for the first 6 steps so that I wouldn't needlessly search them again. I also kept track of the top 10 composite numbers that kept popping up in the search, so I wouldn't have to check them again for primality. I also had a fast way to find solutions to grids composed of only 2 different digits, by generating all their 9-digit permutations (in a pre-sorted fashion). My program incorrectly calculated HOT DOG as 44404447. It did this during the 9 digit search when the leading digit was 0, effectively turning it into an 8 digit number. If I had coded it properly to prevent a leading zero, the new answer would have been 47! This was due to a second bug involving the arrays which stored the partial paths tried. I failed to initialize this memory when starting to look for primes 8 digits long. In the back of my mind I was aware of this latter problem, but I never thought anyone would come up with an 8-digit grid outside of {1,4,7} !! I should have known better! WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? I'm a software developer in Network Systems. For fun I play racquetball and putter around the house. ================================================================= ======================================= =usdaprime ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer =usdaprime 22040 6690 240 150 190 14770 ================= usdaprime was submitted by Neil Weinstock at nsw@luna.att.com ================= HOW DID usdaprime CHOOSE CANDIDATES FROM THE SQUARE ? Simple (relatively) recursive search. At each node, I selected the next node based on which would yield the highest possible 9-digit value, so I would, at least roughly, search in order from highest to lowest. HOW DID usdaprime TEST A CANDIDATE FOR PRIMALITY ? I wish I knew of a better way to do this (is there one?), but all I did was divide the number (call it N) by a list of primes from 3 to SQRT(N). I did some other checks as well, to minimize the number of times I needed to go through this time-consuming process: 1) If the last digit of the N wasn't 1,3,7, or 9, then it couldn't be prime, so I skipped the checks. 2) If N was <= the largest prime I had found so far, then I again skipped the check, since there was no point. 3) If I had already tried this value (see below), then I skipped the check. Oh, I generated the list of primes (potential factors) using a basic sieve. ANY OTHER COMMENTS, TRICKS, WHATEVER? I checked for all the obvious trick boards, i.e., all board entries multiples of 2, 3, 5, or 7. In addition, I found one interesting and unobvious (to me at least) trick board: when no digits on the board are either 1,3,7, or 9, then the answer is the highest single-digit prime found on the board. In my search, I kept track of all the values I'd seen before, plus the positions in which I'd seen them. If I ever encountered a value I'd seen before in the same position, then I terminated that branch of the search immediately, since I'd already covered it. If I encountered a value I'd seen before in a different position, then I at least avoided doing a prime check on it. I used a sorted list of "seen" values so I could do a quick search on it; insertions unfortunately took a while. WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? 1) Hardware developer for BNS-2000 2) Volleyball, bowling, perl hacking 3) I am Elvis (please don't tell) ANY IDEAS FOR THE NEXT POTM? Not a specific idea, but a general one. How about some sort of task that is like a game, in that you pit two programs against each other? You give each program the current board and its current run time, and it returns the new board. You then run a tournament to decide the winner. I realize how difficult it would be (impossible?) to come up with a game that would be suitable for such a contest, but it would make an interesting change of pace. Code Size and run time limits would make the challenge. An ideal game would be a new one for which no algorithms would already exist. Ah, well. Just a thought... ================================================================= ======================================= BoggleYourMind ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer BoggleYourMind 24080 5510 330 590 800 16850 ================================================================= ======================================= usda ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer =usdaprime 22040 6690 240 150 190 14770 usda 24310 2310 420 170 210 21200 ================================================================= ======================================= mintu ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer mintu 27900 2440 1000 3090 3800 17570 ================================================================= ======================================= gridzip ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer gridzip 31260 7320 370 130 160 23280 ================= gridzip was submitted by Rana Dutt at rcd@mtqua.mt.att.com ================= HOW DID gridzip CHOOSE CANDIDATES FROM THE SQUARE ? Picked the largest digit(s) in the square with the largest neighbor to start with. Kept a list of neighbors sorted by value for each position. Walked the square recursively from each starting digit. Picked next candidate from list of sorted neighbors, going from largest to smallest. HOW DID gridzip TEST A CANDIDATE FOR PRIMALITY ? Kept a cache of the last 50 non-primes found during testing, and searched the cache for a match first. Only if no match would I test using the more time-consuming division-by-primes-less-than-square-root approach. ANY OTHER COMMENTS, TRICKS, WHATEVER? The main optimization was to avoid traversing routes already visited. Did this by keeping a list of n-digit numbers that had already been generated/visited for each position, for n=1 to 9. WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? Design software for a WAN access system. Play tennis and racketball for fun. ================================================================= ======================================= primecut ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer primecut 40200 14870 670 200 960 23500 ================= primecut was submitted by Joe Eccles at joe@mink.att.com ================= HOW DID primecut CHOOSE CANDIDATES FROM THE SQUARE ? Searching was done depth first, with candidate squares at each search level ordered highest value first, and in the case of equal values, in order of the highest value "neighbor" for that square. HOW DID primecut TEST A CANDIDATE FOR PRIMALITY ? Hard code results for 1 and 2, then simply check for zero remainder as the number is is divided by sucessive odd numbers up the approximately the square root of the number. ANY OTHER COMMENTS, TRICKS, WHATEVER? - Never check a number for primality if it is smaller than the largest prime found so far. - If sqrt() is used, it becomes the most expensive component of the program, so the upper limit is changed to be the minimum of the number itself, or the sqrt of the number rounded up to the next largest power of 2. This estimate can be generated byusing a series of "and"s with fixed bitmasks, and a couple of shift operations. The savings compared to the use of sqrt() more than makes up for the extra remainders computed. - If there is symmetry in the problem, make use of it. - If row 5 is the same as row 1, and row 4 is the same as row 2, eliminate rows 4 and 5. If in addition, rows 1 and 3 are the same, also eliminate row 3. - Do the same reduction for columns. - Never reduce to less than 2 rows or columns. - There were other problem reduction possibilities that were not implemented due to lack of time. For example, if a corner has the same value as two of its neighbors, never consider it. (This is a small gain for most problems). - Prune the search tree. - At any search level, if a search starting at any candidate square has already produced a prime number with 9 digits, discard all other candidate squares whose value is smaller than that one. - By saving a list is digits and matrix coordinates for the largest prime found, never search a subtree whose digits so far match the prime, and whose next square has the same coordinates as the next coordinate for the known prime. - If a 9 digit prime has been found on any search path, never consider a candidate square whose value is less than that of the known prime for the corresponding digit. WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? - Software development. - Golf, music, bridge. - Sometimes programming can actually be fun. ================================================================= ======================================= gr_primes_id ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer gr_primes_id 51640 13050 8020 1110 800 28660 ================= gr_primes_id was submitted by Kenneth Smolik ================= 1. HOW DID gr_primes_id CHOOSE CANDIDATES FROM THE SQUARE? First of all, the square is searched for the special one-digit-prime-number cases. It is given that at least one prime number is in the grid, and the grid does not have all of its digits as 1's. Therefore, if all the digits are divisible by strictly one of any of the one-digit prime numbers (2, 3, 5, or 7), then the one-digit prime itself must appear at least once in the square and also be the largest prime in the square. Otherwise, numbers in the grid less than 10^9 are sequently picked out largest to smallest, to be tested for primality. A for loop from 9 down to 1 executes, where the loop counter represents the number of digits of the next number to be found. Then a function is called recursively, where each recursion selects a digit for the number in the order from leftmost to rightmost digits. To select the largest numbers first, the gsort library function sorts all the values in all possible grid positions for the current digit to be selected from largest to smallest and then sequntially goes through the test. For a given digit possibility, all possible grid positions for the next digit are stored in another array, and this array is passed to the next recursion of the function. After all the digits are selected, the number is tested for primality. If it is prime, the number is displayed as the program exits; otherwise the recursion process is continued until a prime number is found in the grid. HOW DID gr_primes_id TEST A CANDIDATE FOR PRIMALITY? To test a given number for primality, the number2 and all positive odd intergers other than 1 <= to the square root of the given number are tested as factors of it. The idea is to insure that at least all possible prime numbers are tested as factors of the given number in the most systematic (and legal) but quickest manner. No even numbers besides 2 are prime and since all factors <= the square root of a given number must have a corresponding factor >= the square root of the given number, there is noo need to check tha above square root. If no factors (besides 1 and itself) are found for a givennumber, then it is prime. ANY OTHER COMMENTS, TRICKS, WHATEVER? If there were many if not any possible grids that have largest primes with between 2 and 8 digits inclusive, then if might save run-time to use a temporary file to save all 9-digit numbers found, and then for numbers 8 or less digits, the right-hand digit for a given d-digit number can be truncated to form a corresponding (d-1)-digit number. However, since all grids presented so farthat I've seen are either 1-digit special cases or 9-digit prime number grids using a temporary file proobably is a waste of time- both for the program author and its system run time. WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? Being a systems engineer, I did not have a clue about solving the POTM problem. However, I did pass the "requirements" to my developer who is my son Andrew. Andrew is a high school senior and is taking an AP CS course in Pascal. He is also active in the Math Team, which took first in IL state competion. During hisspare time, he designed the program using Microsoft Quick C. (This program was his fun during XMAS break!) Andrew will be entering UIUC in EE this fall and is looking for a summer job in computer programming. If anyone has any leads, please contact me at ihlpf!kfs. ANY IDEAS FOR THE NEXT POTM? Given some integer x between 1 and some other integer (depending on how long the program would take to run- perhaps 100 to 1000) generate a closed forula strictly in terms of n for the summation from i=1 to n of i^n (in other words, 1^x + 2^x + 3^x + ... + n^x). This formula should be in the form of a polynomial in terms of n. The program should output the sum of the numerical coefficients of each term; for example, in the polynomial a*n^4 + b*n^3 + d*n + e the program should output whatever the value of the sum a+b+d+e is. The sum should be rounded to a certain number of significant digits. The formula and sum both must be generated; no sums, formulas, or parts of the formulas for the summation may be in the source code. ================================================================= ======================================= EnQuest ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer EnQuest 59590 17730 2490 5040 6240 28090 ================= EnQuest was submitted by Frank Rehwinkel at fsr@kingfish.att.com ================= HOW DID EnQuest CHOOSE CANDIDATES FROM THE SQUARE ? Ordering the 25 cells so they'ld be looked at in descending order. For each cell, created a descending ordering of the cells around it. For each cell, kept a hash table that tracked which number had already been tested for that cell. (This reduced a lot of excess searching down branches that had effectively already been traversed.) The cells were traversed in descending order, and once a 9 digit prime was found, the search tree could be pruned whenever a cell was reached that didn't have at least the value of the associated position in the candidate prime. HOW DID EnQuest TEST A CANDIDATE FOR PRIMALITY ? I learned my lesson here. The library could probably have taught me much about primes judging from the solutions the fastest programs used. I created a list of primes, the hard way (using %), that would then be used against any odd number that was larger than the largest prime found so far. I even forgot about the trivial test for 5s and the easy test for 3s! (So I guess it doesn't matter that I never heard of the test for 7s, 11s and 13s.) ANY OTHER COMMENTS, TRICKS, WHATEVER? WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? Design and develop software for ADSS (in Quest), a group specializing in optimization software for the airline industry. ANY IDEAS FOR THE NEXT POTM? How about trying to solve one of the many NP-hard optimization problems that we get from the airline industry (e.g. travelling salesman or bin-packing). ================================================================= ======================================= goodprimes ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer goodprimes 70300 30710 17440 4150 7370 10630 ================= goodprimes was submitted by David Good at dgood@iwcs.att.com ================= HOW DID goodprimes CHOOSE CANDIDATES FROM THE SQUARE ? All possible paths through the array were built up starting with the low-order digit. HOW DID goodprimes TEST A CANDIDATE FOR PRIMALITY ? 1) I ran the standard sieve to generate an array of all primes less than sqrt(999999999) (there are 3400 of them). 2) For each path through the array, I checked the remainder of the number against each of the primes in the prime array, starting with 7 (since filtering step 1 eliminated the need to check for 2 and 5, and filtering step 3 eliminated the need to check for 3), until either the prime array was exhausted, or the current prime was more than sqrt(num) (so num had to be either prime, or a composite number whose smallest factor was greater than sqrt(num) (!!) ) 3) filtering: "for each path through the array" is not quite right. 1) if the starting cell (low order digit) is 0, 2, 4, 5, 6, or 8, none of the paths can be prime, and are not even generated. 2) if the digit to be prepended to a number is == 0, there is no need to check to see if it is a prime, since it will not be a largest prime. 3) if the current number modulo 3 == 0, it is divisible by three, and is not a prime. 4) if the current number is less than the largest prime found so far, there is no need to test it for primality. 5) if the current number matches any of the numbers previously found to be not prime, it is not prime, and need not be checked. (I kept an array of not_primes[], which eliminated a *lot* of the need to do modulo math, which is apparently slow on System 3000's and SUNs (involving a subroutine call?)) ANY OTHER COMMENTS, TRICKS, WHATEVER? I originally had a paths() subroutine that called itself recursively. I wrote a program to generate 225 pathsLXY() routines, collapsing the depth and the current position into the subroutine names, so all array calculations involved constant subscripts, so addresses could be calculated at compile time. WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? For a living: I'm in the StarServer FT development and support group at IW. For fun: I read a lot of science fiction. ================================================================= ======================================= primevil ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer primevil 153230 140 810 40710 48740 62830 ================= primevil was submitted by Stuart Rowland at swr@mtatm.att.com ================= HOW DID primevil CHOOSE CANDIDATES FROM THE SQUARE ? Brute force HOW DID 0ready4 TEST A CANDIDATE FOR PRIMALITY ? Divided by all prime less than or equal to sqrt of number ANY OTHER COMMENTS, TRICKS, WHATEVER? I was truly "not ready for prime time" - I wrote the simplest program that would solve the problem since I did not have the time required to work on a faster solution. WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? ANY IDEAS FOR THE NEXT POTM? ================================================================= ======================================= spite ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer spite 231740 126560 720 10150 61510 32800 ================= spite was submitted by Gerald Williams at gsw@aloft.att.com ================= > HOW DID spite CHOOSE CANDIDATES FROM THE SQUARE ? This was the fast part--it first checked for degenerate cases (i.e. all numbers in matrix divisible by 2,3,5,7) while generating a linked list through the matrix in which the links are keyed on the following digit. This can be thought of as a tree when it is expanded by following the first 8 links. It recursively traversed the "tree" by depth, starting with 9 digits, and by number, starting with 9. > HOW DID spite TEST A CANDIDATE FOR PRIMALITY ? This was the extremely slow part. Actually, the testing itself was fast, but the setup was slow. It first generated enough primes to factor the largest prime the square could produce, then used those to try to factor candidate primes. The last few known non-primes were kept track of to avoid checking them again, and some other tricks were used to make the generation faster or not test numbers that can't be prime. The program was not supposed to work this way in its final form. There are MUCH faster ways to test primality, although I did not remember the algorithms at the time (I was surprised the entry did as well as it did with this algorithm). I borrowed a book on primes and primality testing, but did not have a chance to read it since I was coordinating over a dozen software releases around Christmas (it wasn't my idea!). > WHAT DO YOU DO FOR A LIVING? Spend too much time coordinating other people's efforts and not enough doing REAL programming. > FOR FUN? Ski. Travel. Whatever else I can fit in between work, graduate school, and working on our new house. > INNERMOST SECRET? It wouldn't be a secret then, would it? ================================================================= ======================================= prisq ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer prisq 307510 195860 1190 10510 74410 25540 ================================================================= ======================================= voodoo ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer voodoo 359830 125700 1390 23300 107310 102130 ================= voodoo was submitted by Ram Ramachandran at rams@ihsdv1.att.com ================= HOW DID voodoo CHOOSE CANDIDATES FROM THE SQUARE ? Did some preliminary checking to eliminate the case of all numbers divisible by 2, 3 and 5. Then checked to see symmetric squares along the diagonals. If so eliminate numbers above the diagonal and check if the resultant set of pattern is symmetric across its "diagonal" and further eliminate numbers. Do this till no more can be eliminated. Sort the list in descending order. Computed primes up to sqrt (999999999) Starting with the highest number pick candidates moving from position to its neighbour and keeping track of the highest computed prime. HOW DID voodoo TEST A CANDIDATE FOR PRIMALITY ? 1) Test for multiple of 2, 3, 5. 2) If < sqrt(999999999) binary search to see if it is one of the primes computed. 3) If > sqrt (999999999) see if divisible by one of the primes computed ANY OTHER COMMENTS, TRICKS, WHATEVER? Looking for symmetric squares. I think I was on a time "(de)warp". I thought the dead line was Monday night. Over the weekend I found one major bug which causes it to code dump in certain cases. I came all prepared to mail the POTM master my final version just to find out that I was 8 hours (9 if dead line was 11:59 EST) too late... WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? I work for the Switched Digital Video project at Naperville, Illinois. ================================================================= ======================================= FIVE ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer FIVE 366240 270 980 28060 242350 94580 ================= FIVE was submitted by Mark Meyer at mdm@cbnscs.att.com ================= HOW DID FIVE CHOOSE CANDIDATES FROM THE SQUARE ? A simple recursive traversal of the grid, starting at a 9 (or highest non-zero digit) and stepping to the highest of the (up to 8) next possible digits. HOW DID FIVE TEST A CANDIDATE FOR PRIMALITY ? The biggest time saver was to remember previous candidates in a Digital Search Tree. It also checks the last digit (not even or 5), and compares if longer and greater than current high prime. The IsPrime function is rather simple and used only when necessary. ANY OTHER COMMENTS, TRICKS, WHATEVER? It looks for those special grids (like all 3,6,9,0, all 1,4,7, etc...) There must be a way to reduce the size of non-random grids (which I suspect some others have done.) FIVE works well for random grids. WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? - Systems Engineering, Software Development, System Testing, and Field support for the Netminder Network Trouble Patterning team. - Golf, Bowling, surf the internet, and enter the POTM. - ...but then it would not be a secret ;-) ANY IDEAS FOR THE NEXT POTM? Whatever my next programming assignment is... ================================================================= ======================================= primesquare ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer primesquare 412400 225780 230 19220 109210 57960 ================================================================= ======================================= Deion ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer Deion 525040 459510 1130 6290 26170 31940 ================= Deion was submitted by Dennis Sanger at drs@dr.att.com ================= HOW DID Deion CHOOSE CANDIDATES FROM THE SQUARE ? Just plain ol' depth-first, largest-first searching. After submitting a working version in early November, I never got around to improving my entry. I suppose I should be pleased that it actually got a perfect score, even though it got stomped on the tie-breaker. HOW DID Deion TEST A CANDIDATE FOR PRIMALITY ? It's too embarrassing to talk about. WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? Living: software development for the Multimedia Call Server. Fun: Anything else. Innermost secret: Aliens speak to me via transmitters implanted in my molars. ================================================================= ======================================= poot ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer poot 619970 619020 530 140 140 140 ================================================================= ======================================= yap ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer yap 953250 618690 1280 84050 162980 86250 ================================================================= ======================================= Daroohahaha ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer Daroohahaha 1042940 606540 830 420 560 434590 ================================================================= ======================================= =past_my_... ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer =past_my_... 1202330 200 340 614170 474730 112890 ================= past_my_... was submitted by Fred Hicinbothem at fah@ffast.ffast.att.com ================= HOW DID past_my_... CHOOSE CANDIDATES FROM THE SQUARE ? VERY UGLY ... prepared an ordered list of neighbors for each of the 25 squares - largest neighbor first. Then, looked at the biggest starting numbers and examined each neighbor in turn until a nine digit string was found. Then test it - if no good, move down the stack until all nine digit numbers are tested. Then go to 8 digits ... etc. HOW DID past_my_... TEST A CANDIDATE FOR PRIMALITY ? Nothing too difficult - Sieve of Eratosthenes (easier to code than to spell) to come up with a list of primes, and then straight use of % ... ANY OTHER COMMENTS, TRICKS, WHATEVER? Got rid of repeated candidates, divisible by 3 candidates, those that end in 0,2,4,5,6,8, squares with all (7,4,1), all one number squares, etc. WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? Systems Engineering and project management (whatever they are); POTMs, games, and family (not necessarily in that order); my secret? - I can't code worth a damn! ================================================================= ======================================= 2true ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer 2true 1504710 610830 2370 27700 616780 247030 ================================================================= ======================================= bodkin ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer bodkin 1653930 614920 1870 105580 619440 312120 ================= bodkin was submitted by Ton Kramer at ton.kramer@att.com ================= HOW DID bodkin CHOOSE CANDIDATES FROM THE SQUARE ? for startdig = 9 downto 1 do step recursively through the square taking the heighest neighbour as next digit if it is a prime and larger than the one we have, mark it if we have all numbers starting with startdig and prime is set then print prime and exit done HOW DID bodkin TEST A CANDIDATE FOR PRIMALITY ? test all even cases and then loop through 11 < sqrt(number) ANY OTHER COMMENTS, TRICKS, WHATEVER? Due to my stupidity I lost the original code on my machine so development stopped after the first entry. I was designing a better way of selecting the correct branch but this broke the original algorithm and I could not get the new algorithm to work properly in the time I allowed myself to work on it. WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? Living: I develop 5ESS ISDN features. (Did develop Supervision Signaling features) Fun: Drive my BMW R1100GS Motorcycle. Build Motorcycle models. Develop tours for motorcyclists. Program C on my Amiga Home computer. ANY IDEAS FOR THE NEXT POTM? ================================================================= ======================================= squaredance ============= ================================================================= Measured Time (milliseconds) ENTRY TOTAL best.741 holy.factory corners hot.dog equalizer squaredance 1925820 612370 6080 616240 610890 80240 ================= squaredance was submitted by Graham McDermot at gmcdermo@ihlpo.att.com ================= HOW DID squaredance CHOOSE CANDIDATES FROM THE SQUARE ? A form of alpha-beta cutoff (or at least I think that was what my lecturers at Uni called it.......dim distant past) Judging by the performance of squaredance a very poor form of cutoff... HOW DID squaredance TEST A CANDIDATE FOR PRIMALITY ? I had originally planned to use the small array of numbers from the factor.c code to generate all the prime numbers to test a candidate, however the powers that be decided this was not allowed. I had no option then but to hack in an odd number generator instead. ANY OTHER COMMENTS, TRICKS, WHATEVER? These competitions are great fun, but like every other time I've entered I get enough time to cobble together a first attempt, then only get an hour or two every blue moon to update/change it........ WHAT DO YOU DO FOR A LIVING? FOR FUN? INNERMOST SECRET? Field Support, ex-Development, now trying to get back into Development.... judging by my recent potm results I need the practice 8-) ANY IDEAS FOR THE NEXT POTM? 1. How about a maze solving puzzle.....for example given a sample file with an ascii representation of a maze, find your way from point A to point B, program to output N,E,S,W as directions. As an added twist find your way from A -> B then C. Shortest direction, quickest time, smallest code decides or whatever....... 2. Magic puzzle solving. All the numbers in an X by X square add up to the same in any direction Solve the puzzle by using a set of numbers supplied. Alternatively use the alphabet to represent the numbers in the same way as the addition puzzle did but this time it has to solve a magic puzzle. Shortest code, quickest time, highest numerical value of the digits or subset of digits, etc....... 3. Finding the longest word acceptable to the system dictionary (if one exists) from a set of letters passed to a program. Multiple use of letters can be allowed or disallowed dependant upon the whim of Mr POTM. 4. errm...thats all I can think of in 5 minutes. =================================================================