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