Binary Games

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
Сайт управляется системой uCoz