HHC 2015 RPN programming Contest is now open

[Dieter]

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

It's just me, but I think I can explain how it works. ;-)

For integer x=0...10, the expression x²–x+11 yields a prime number. In our case x is an integer between 1 and 6, and so the expression returns 11, 13, 17, 23, 31 and 41. So if the roll is 1 3 2 4 6 this sequence is transformed to 11 17 13 23 41. Multiplying these values yields a characteristic product, in this case 1281137.

Now a small straight has to contain 1 2 3 4 or 2 3 4 5 or 3 4 5 6, which corresponds to the products 11*13*17*31=55913, resp. 13*17*23*31=157573, resp. 17*23*31*41=496961. The remaining fifth die just changes this result by a (prime) factor. So all that's left to do is check whether the product is divisible by 55913, 157573 or 496961. If it is, a small straight has been detected. In our case 1281137 mod 55913 = 0 => Bingo.

Dieter