Here's an interesting game: I announce a sequence of binary digits, such as "1 1 0 1 0 0 1 ...etc". These digits represent a sequence of numbers, with the first announced digit being the most significant and the latest being the least significant. Thus, the string of digits just mentioned corresponds to the sequence of numbers 1, 3, 6, 13, 26, 52, 105, ... Your object is to interrupt me at some stage and supply one more digit such that the resulting number is divisible by (at least) one of a specified set of primes, say {7,11,13,17}. My object is to avoid that outcome. What interests me about this game is that, depending on the specified set of primes, it may or may not be possible for me to avoid eventually giving you a winning number. For example, with the set {7,11,13,23} I can go on indefinitely without giving you a winning opportunity, whereas with the set {7,11,13,17} you are sure to have a winning opportunity no later than the 16th digit. (This is because any number larger than 9705 can be truncated at some point in its binary sequence and made divisible by one of {7,11,13,17} by flipping the least significant digit if necessary.) Let [p,...,q] denote the largest number such that no sequential substring of its binary digits (including the most significant) can be made divisible by one of {p,..,q} by flipping the least significant digit. Then we have the following miscellaneous results [3] = 1 [5] = oo? [5,7] = 3 [5,11] = oo? [5,13] = 7 [7,11,13,17] = 9705 [7,11,13,19] = 17 [7,11,13,23] = oo? [11,13,17,19,31] = 59 [11,13,17,19,29,31] = 15 [13,19,23,29,31,41,47,67] = 85 I think each of these is "minimal" in the sense that removing any one of the primes would change the result. QUESTION: Is there a simple way of characterizing sets of primes that "cover" all the integers above a certain number (in the sense described above)? Analagous problems arise in more complicated games where two or more players each select a digit in turns, and each player trys to cause the constructed number to be divisible by a certain set of primes. Also, there are interesting variations using base-3 or base-4 numbers, etc. Obviously if the set T of "target" primes includes 2, you can win at any stage by simply placing a "0" at the end of the present sequence. If T includes 3 you can win after I supply the first (non-zero) digit by supplying a "1". On the other hand, if T = {5}, you are not guaranteed an opportunity of winning. However, with T = {5,7} you are guaranteed a winning opportunity. Here is a short list of target sets for which you are guaranteed a winning opportunity: {2} {3} {5,7} {7,11,13,17} {11,13,17,19,31} {13,17,23,29,31,37,41} {17,23,29,31,37,41,53,59,61,67,73,79,97,251,1049,1571} {19,23,29,31,37,41,43,53,61,67,73,79,97,173,283,643,701,1049,1123, 1571,3137,4201} For any given prime p, does there exist a set T with smallest member p such that you are guaranteed a winning opportunity? What is the minimum number of elements for such a set?

Return to MathPages Main Menu