3 is an odd prime, 5 is an odd prime, 7 is an odd prime, 9 is a very odd prime...

July 10, 2007 6:34 AM

The Prime Game is not really much of a game, but it is a neat & little-known fact about the decimal representation of prime numbers.
posted by Wolfdog (24 comments total)

"Write down a prime number" also isn't really in the same bar-bet category as, say, "betcha I can drink that shot without touching the glass".
posted by yhbc at 6:48 AM on July 10, 2007

Dumb question: Does this reduce the difficulty in determining primality from O(sqrt(N)) to O(log(N))? Wait...it must have already been better than O(sqrt(N)).
posted by DU at 6:49 AM on July 10, 2007

I don't see why it would, since the number 27 is not prime, but I can turn it into the prime number 2 or the prime number 7. So by itself it'd be a pretty crap primality test.

If you like this sort of thing you should read up on Formal Languages.
posted by chunking express at 6:52 AM on July 10, 2007

d'oh
posted by DU at 6:54 AM on July 10, 2007

You could use this to show that a number is not prime, as I believe he mentions, but remember if there are d digits in the number then there are 2^d-1 subsets of digits you can consider crossing out.
posted by Wolfdog at 6:56 AM on July 10, 2007

good god that's a boring game.
posted by Baby_Balrog at 8:07 AM on July 10, 2007 [1 favorite]

Wolfdog's got it - this is only really useful for showing a number is not prime. Still, it's an interesting little slice of mathematics.
posted by Zephyrial at 8:17 AM on July 10, 2007

"9 is a very odd prime" - really? Hmm, back to school for me then...
posted by Chunder at 8:18 AM on July 10, 2007

This is adorable.
posted by escabeche at 8:33 AM on July 10, 2007

9 is so odd it's divisible by something other than 1 and itself.
posted by dzot at 9:08 AM on July 10, 2007

Wait, exactly how can this help me cheat in online poker?
posted by gwint at 9:08 AM on July 10, 2007

What a bizarre feature of primes. While I didn't quite understand the mathematical explanation, it sounds like it would work in any base system (not just base ten).
posted by McLir at 10:04 AM on July 10, 2007

English. Science. History. I was really good in all these subjects in school. Only math gave me constant frustration. I don't know why; I suppose my brain isn't wired to accept absolutes ("Well, why can't 2+2=7?") but whatever the cause, I always struggled in math. Every now and then I come across some of the wizardry of that universal language and am awed enough to try and give math another shot, to understand its infrastructure, complexity and beauty. But every time I fail. This is a quirky and interesting bit of mathporn, but I won't be tricked again.
posted by Terminal Verbosity at 10:15 AM on July 10, 2007

("Well, why can't 2+2=7?")
"I'll give you $2 and then another $2. You give me $7 back."
"Deal! This time I might just break even!"
posted by Wolfdog at 10:29 AM on July 10, 2007

I've never trusted math people. The way they sit there all calculating... watching... assessing you... It's like they are trying to determine if you are divisible, or how much of you they could subtract before you were rendered irrational.

I can't prove this, but I'm willing to bet that every single serial killer who has ever lived was good at math.

*shudders*
posted by quin at 10:42 AM on July 10, 2007

Now, a very neat result about the subsequence partial order is that every pairwise incomparable set is finite.

I totally don't see that. Anyone know the proof?
posted by painquale at 10:51 AM on July 10, 2007

painquale: that's not his result. Its a generalization of Dickson's lemma.
posted by vacapinta at 11:00 AM on July 10, 2007

Seven!

Seven, Seven, bo-beven
Banana-fana fo-feven
Fee-Fi-mo-meven
Seven!

60000049!

60000049, 60000049, bo-60000049
Banana-fana fo- 60000049
Fee-Fi-mo- 60000049
60000049!

Chuck!
(etc.)
posted by Smedleyman at 11:31 AM on July 10, 2007

"Subsequence" seems to be the preferred term in North America, but in Europe they call this a "subword".

You goddam crazy Yanks with your liberal use of the English language.
posted by Samuel Farrow at 12:35 PM on July 10, 2007

What a bizarre feature of primes. While I didn't quite understand the mathematical explanation, it sounds like it would work in any base system (not just base ten).

As I read it, it will work in any base system, but it becomes considerably less powerful in lower bases: I'm pretty sure the minimal set in binary is {1}, so it's pretty unhelpful there.

As you go into higher bases, you increase the size of the minimal set, so it's going to be increasingly harder to calculate with certainty what that is.

And his point at the end is that it's not just primes: it'll work with any set of strings, but it's not always easy to figure out what the minimal set is.
posted by Arturus at 2:34 PM on July 10, 2007

I'm pretty sure the minimal set in binary is {1}, so it's pretty unhelpful there.

Actually, no, since 1 is not prime. The minimal set in binary would be {10, 11}.

Turns out it's fairly easy to show that the 26 numbers he gives are the minimal set for primes in base 10.

Clearly, the one-digit primes (2, 3, 5, 7) must be on the list.

Now, consider what two-digit combinations prime numbers may end with, which have not already been eliminated by the primes we already have on the list. Recall that in base 10, primes of two or more digits must end in 1, 3, 7 or 9. The two-digit combinations are:

01 09 11 19 41 49 61 69 81 89 91 99

Of these, 11, 19, 41, 61, and 89 are primes. Add them to the list.

What three-digit combinations could end prime numbers, that aren't eliminated by the one- or two-digit primes already on our list?

001         801 901
009 409 609     909
049 449 649     949
069 469 669     969
081         881 981
091         891 991
099 499 699     999

(There's a reason I'm writing them in this format. You'll see.)

Of these, 409, 449, 499, 881, and 991 are prime. Add them to the list.

You might think you could keep going this way, but if you try that you get some that just keep going on forever. You could keep adding zeroes on to the left of the ones we haven't eliminated yet, ad infinitum. Strings that consist entirely of 0s, 6s, and 9s are divisible by three, as well as all subsets thereof (recall that if the sum of the digits of a number are divisible by three, the number itself is divisible by three). Let's split the numbers into those ending with 1, and those ending with 9, and do one more round with each of those as above:

0001 8001 9001
0081      9081
0091 8091
0801      9801
0891
0901 8901
0981

9001 is prime. Add it to the list.

Second, note 0891 and 0981 have no numbers to their right. This means you could keep adding zeroes to the left of these, and you'd have a string of digits which could end a prime number, but since integers don't begin with zeroes, you'd eventually have to add a non-zero digit on the left, and whichever one you chose would allow us to get to one of the ones already on our list. (E.g., if you had 000891 and added an 8 to the left, you'd get 8000891, from which you can strike digits to get 881.)

Likewise, if we took 8091, 8901, 9081, or 9801 one more digit, we'd see the only digit we could add to the left of these and not run into one of the numbers already on our list would be zero. With 8001, you can add a 9 to the left to get 98001 (composite), but add anything else other than zero to the left of that and you get a number from which you can create one already on the list.

Now to the ones ending in 9:

0009      6009 9009
0049      6049 9049
0069      6069 9069
0099      6099 9099
0469      6469 9469
0609      6609 9609
0649      6649 9649
0669 4669 6669 9669
0699      6699 9669
0909      6909 9909
0949      6949 9949
0969      6969 9969
0999      6999 9999

6469, 6949, 9049, 9649, and 9949 are prime. Add them to the list.

The fact that the column of numbers starting with "4" is nearly empty is due to the fact that 409, 449, and 499 are already on our list. But if you kept doing this for more and more digits, you'd never quite get rid of it entirely. With each additional digit, you'd get just a single number in the "4" column: 46669, 466669, 4666669, etc.

Turns out that 46*9 (think of "6*" as 0 or more 6s repeated, i.e., as in a regular expression, not as multplication) is always divisible by 7. (Proof of which is left as an exercise for the reader). But 46*9 remains as a possible string of digits with which a prime number can end, so we have to look deeper.

What can we add on the left of 46*9 which might leave it as a string of digits which could end a prime, and not be eliminated by any of the numbers already on our list? Zeroes, of course, but eventually you have to add something other than a zero. Not 4 (449 is already on the list). Not 6 (649 is composite, and 6469 is on the list). 9 works (949 is composite, 9469 is composite), but don't add a second 9 or you run into 9949, already on the list. 94669 is also composite, but 946669 is prime. Add it to the list, and then we don't need to worry about any longer numbers of the form 946*9.

Now we've gotten rid of that pesky 46*9. (And by extension, all forms of 0*46*9.) The remaining numbers are of two types: those consisting entirely of 0s, 6s, and 9s; and those ending in 49.

Let's take the numbers consisting entirely of 0s, 6s, and 9s first. As long as you keep adding only 0s, 6s, and 9s, the number remains divisible by 3, yet is still a string of digits which could end a prime. But add anything other than 0, 6, or 9, and you get a number we've already covered (keeping in mind that they all end with 9: 19, 2, 3, 409, 46*9, 499, 5, 7, or 89).

Now that we've eliminated some of those pesky potentially-infinite series, we can go back to our old method for the strings of digits ending in 49:

00049 60049
00649 60649
00949
06049 66049
06649 66649

60649 is prime; add it to the list. 00949 has nothing you can add to its left without running into something already on the list, so eliminate it from further consideration.

With 60649 now on the list, all remaining primes to be added to the list must have the form 6+0*49 (let "6+" indicate one or more 6s).

Candidate 6-digit numbers: 600049, 660049, 666049, and 666649. The last of these is prime; add it to the list, and note that larger numbers will have to have three or fewer 6s.

Candidate 7-digit numbers: 6000049, 6600049, and 6660049. None of these are prime

Candidate 8-digit numbers: 60000049, 66000049, and 66600049. It so happens that all three are prime. Add them all to our list, and we're done!

(And acknowledgements to the primality test here, without which I never would have been able to do this.
posted by DevilsAdvocate at 4:11 PM on July 10, 2007 [5 favorites]

Actually, no, since 1 is not prime. The minimal set in binary would be {10, 11}.

Right, thanks. Wasn't quite thinking properly there.

Very nice demonstration.
posted by Arturus at 4:34 PM on July 10, 2007

This game is a lot a fun at parties that I would never go to.
posted by MiltonRandKalman at 7:04 PM on July 10, 2007 [1 favorite]

Ah, great stuff! DevilsAdvocate is awesome.
posted by painquale at 11:47 PM on July 10, 2007