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

"I'll give you $2 and then another $2. You give me $7 back."

"Deal! This time I

posted by Wolfdog at 10:29 AM on July 10, 2007

I totally don't see that. Anyone know the proof?

posted by painquale at 10:51 AM on July 10, 2007

You goddam crazy Yanks with your liberal use of the English language.

posted by Samuel Farrow at 12:35 PM on July 10, 2007

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

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 (

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,

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

Of these,

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,

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:

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

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:

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

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

Candidate 8-digit numbers:

(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]

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

Very nice demonstration.

posted by Arturus at 4:34 PM on July 10, 2007

Post

# 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 Subscribe

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.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

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

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

You could use this to show that a number is

posted by Wolfdog at 6:56 AM on July 10, 2007

*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]

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

posted by Zephyrial at 8:17 AM on July 10, 2007

*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

posted by Chunder at 8:18 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

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

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

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

posted by Terminal Verbosity at 10:15 AM on July 10, 2007

*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

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

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

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]

posted by MiltonRandKalman at 7:04 PM on July 10, 2007 [1 favorite]

« Older Matthew Parris | The Censored Eleven Newer »

This thread has been archived and is closed to new comments

posted by yhbc at 6:48 AM on July 10, 2007