HHC 2015 RPN programming Contest is now open

[Allen]

(10-02-2015 09:19 PM)Peter Murphy Wrote:  I still wonder about Egan's commented code (in #47, on page 3 of this thread) in which he refers to "map to prime numbers," ""x^2 - x + 11, x = 0-10 prime." what algorithm is he applying here? David? Egan?

Egan's beautiful and clever solution (my favorite) is just the right balance for the approach he took. Using a trivial python program, one will find that \(x^3-x+11\) is not the only diophantine polynomial that maps {1..6} on to the set of primes. There are countably infinite polynomials that will map to primes, including:

\(-x^2+17x+37\): 53,67,79,89,97,103,prod: 249446106271
\(-x^2+17x+97\): 113,127,139,149,157,163,prod: 7606248149551
\(x^2-17x+83\): 67,53,41,31,23,17,prod: 1764708511
\(x^2-17x+89\): 73,59,47,37,29,23,prod: 4995745291
\(x^2-15x+67\): 53,41,31,23,17,13,prod: 342406129

The trick is to minimize the byte count for BOTH the generating function, and the modulus tests. To that end, the polynomial Egan chose is probably the smallest byte count to calculate using just x^2 and x. Interestingly, there is one other trivial polynomial that can shorten the program by at least two more bytes:

\(x^3-5x^2+23\): 19,11,5,7,23,59, prod=9926455

It takes an extra step or two to calculate the primes (19,11,5,7,23,59) but since all the MOD tests have to test for dice 3 and 4, the total length of the program is reduced since the smallest primes (5 and 7) are used in every product for testing (in this case 7315, 8855, and 47495). The smaller products actually make the total byte count smaller, even if the polynomial is not as clean. Kudos to Egan for such a clever solution.