Friday, December 01, 2006

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.

11 comments:

Jonathan Lubin said...

This is, indeed, very neat!

Deane said...

Jeff,

Very cool!

Deane

D. Eppstein said...

So is there an algorithm that takes as input a base and outputs the list of minimal primes in that base? Or did you just get lucky with decimals that you were able to construct the complete description?

Jeffrey said...

Hi, David. Thanks for stopping by.

The primes are sufficiently dense that there might well be an algorithm to deduce the minimal set in any base of representation. But I don't currently have such an algorithm.

Someone has suggested the size of the minimal set, as a function of the base, as a measure of the complexity of the original language, but as far as I know, little work has been done on this because computing the minimal set is, in general, so hard.

David Swart said...

Hi Jeff (and all),

If anyone is planning on coming up with a recursive method of calculating such minimal sets, perhaps I can get people started with a base case:

unary: {11}

(I know recusion is not a likely candidate for such an algorithm, but then the tongue-in-cheekiness doesn't work).

Jackie Rodgers said...

Jeff, that's something new I learn from your blog today. Very cool indeed! :)

DavidA said...

Is the minimal set for the squares known? My Haskell code has so far found:
1,4,9,25,36,576,676,7056,80656,
665856,2027776,2802276,22282727076,
77770707876,78807087076,
7888885568656,8782782707776,
72822772707876,555006880085056,
782280288087076,827702888070276,
888288787822276,2282820800707876,
7880082008070276
It looks like it could go on and on.

Jeffrey said...

No, the minimal set for squares in base 10 is not known, to my knowledge. It might be extremely difficult.

Anonymous said...

I'd include 0 as a square, which would simplify the minimal set of the squares in base 10 somewhat. :)

Bassam Abdul-Baki said...

Hi Jeffrey,

Thanks for a very interesting article. Looking at the powers of 2 minimal set, I think there's a way to determine it, which I've somewhat started in an Excel spreadsheet. I'll let you know if do.

Marc said...
This comment has been removed by a blog administrator.