The Prime Game

First, the game.

Ask a friend to write down a prime number. Bet them that you can always strike out 0 or more digits to get one of the following 26 primes:

2, 3, 5, 7, 11, 19, 41, 61, 89, 409, 449, 499, 881, 991, 6469, 6949, 9001, 9049, 9649, 9949, 60649, 666649, 946669, 60000049, 66000049, 66600049.

For example, if your friend writes down 43, you can strike out the 4 to get 3. If your friend writes down 946969, you can strike out the first 9 and the 6's to get 499.

(There's not always a unique way to do this, and of course it works with some non-primes, too: if your friend writes down 35, which isn't a prime, you can strike out the 3 to get 5 or vice versa. But if someone gives you a number where you can't strike out some subset of the digits to get a prime on the list above, then that number isn't prime. For example, you can't strike out any subset of the digits of 649 to get a prime on the list, but 649 isn't prime.)

I published this strange result in the Journal of Recreational Mathematics in 2000; there's a copy on my papers page. Believe it or not, there's actually some interesting mathematics behind it.

Let's say that a string of symbols x is a subsequence of a string of symbols y if you can strike out some symbols of y (not necessarily contiguous) to get x. ("Subsequence" seems to be the preferred term in North America, but in Europe they call this a "subword". However "subword" is used in North America to mean "contiguous subblock".) The relation "x is a subsequence of y" is a partial order, meaning it shares the following properties of the ordinary <= relation on integers:

• x is a subsequence of x;
  
  
• If x is a subsequence of y and y is a subsequence of x, then x=y.
  
  
• If x is a subsequence of y and y is a subsequence of z, then x is a subsequence of z.
  

We now call two strings comparable if x is a subsequence of y, or vice versa; otherwise, we say x and y are incomparable. A set is pairwise incomparable if every pair of elements is incomparable.

Now, a very neat result about the subsequence partial order is that every pairwise incomparable set is finite. This isn't obvious, and it isn't true for every partial order. (For example, it isn't true for the order where "subsequence" is replaced by "subword".) You may enjoy trying to prove this.

We need one more concept: the minimal element. A string x in S is said to be minimal for S if whenever y in S is a subsequence of x, then y=x. Given a set of strings S, it's not hard to see that the set of minimal elements of S is pairwise incomparable. So it must be finite. And every string in S has the property that some minimal element is a subsequence of it.

Now, to get the prime game, let S be the set of strings representing primes in base 10. The list of 26 primes above is the set of minimal elements for S.

Determining the set of minimal elements isn't always easy. For example, if instead of the primes we use the decimal representations of the powers of 2, then no one currently knows how to compute the set of minimal elements. It's probably {1,2,4,8,65536}, but proving this seems quite hard.

A neat consequence of this result is that, given any language L, the set of all subsequences of strings in L is regular. We can't always easily determine the regular expression or automaton for L, but we know it exists.

Here's a link to a file of cards you can print, cut out, and perhaps laminate, with the prime game on them. Enjoy.