ok, the way I am understanding the problem , we wish to find a pair of primes X,Y such that we can have a sequence of 15 moves of length either X or Y that visits each of the numbers once.  Now based on the sequence given with 5,4 the final move from 5 to 12 is not of length 5 or 4, thus based on this I am assuming that the final move back to the start does not have to be of length X,Y to be valid.  It simply resets itself once the last number is visited.  So the first button press gives us the first number in the sequence so we only need worry about the other 15 button presses.  Each of these can result in a move of either X or Y, thus there are a total number of 2^15=32768 possible button press combinations we need to look at for each X,Y to see if a complete sequence is possible.

Now a point of confusion for me is in the further thoughts section it mentions that by changing one of the primes it results in a different number being lit first.  From what I understand any combination X,Y that allows for a complete tour in 16 presses, then any starting number you choose to start at will still result in a complete tour.  So once we find the initial minimal X,Y we can then have the sequence start at any of the 16 numbers.  So it appears that there is an aspect of this problem that I am overlook.

Also I am assuming that by smallest X,Y we mean we wish to minimize the larger of X,Y.

Having said all that I am going to write a program that starts with the combination (2,3) and checks all 2^15 possible sequences for a complete sequence and if not found continues through progressively larger pairs until one is found.

Posted by Daniel on 2009-06-18 12:09:35