Caveat: This is not a programming question per se, but am posting here for LQ minds attuned to logic and mathematics.

Recently wanted to generate a 6-digit prime number from the set of digits {0,1,2,3,4,5} or {1,2,3,4,5,6}. Goal: Generate a six digit prime number using each digit in the set exactly once, in any order. After a few failed attempts, I started puzzling and soon remembered a mathematical principle via which I knew, without having to write a program or trying all possible combinations, that my goal was impossible given either of the above two sets of six digits.

Rules: Assume normal base-10 integers. Use each of the six digits in the set in any order. Leading zero OK. Obviously, the final digit may not be an even number or a five, so only numbers ending in a 1 or 3 need be tried. This leaves 240 possible combinations of digits for each 6-digit set. None of which are prime.

Other sets such as {1,4,6,7,8,9} or {3,6,7,1,8,4} might yield one or more prime numbers (e.g. 417869 and 186437). But there are no prime numbers containing the six digits {0,1,2,3,4,5} or {1,2,3,4,5,6}

I can explain why. Can you?

Am confident someone in LQ land is already aware of the mathematical principle involved, which can also lead to a neat number trick to play on friends. Possibly more to follow.

Is this it?

Prime Factors of Consecutive Integers
E. F. Ecklund and R. B. Eggleton
The American Mathematical Monthly
Vol. 79, No. 10 (Dec., 1972), pp. 1082-1089

Daniel B. Martin

.

No.

Have never heard of the work you cited, and don't understand the relationship to my puzzle. I've presented the two sets of digits in ascending order, but the curiosity is that no matter what sequence in which the digits are arranged the resulting number is not prime, and there is a mathematical principle to prove it without trying all such sequences.

By the way, I think there's at least one prime number (23456789) consisting of consecutively ordered digits.

Here's a hint

1 members found this post helpful.

John 1:14 but where does that lead us? To the promised land? Didn't somebody else already do that?

Daniel B. Martin

Click on the hyperlink 'hint'

(Nice job decoding my signature, but that wasn't the hint)

The digits sum to a number divisible by 3.

Specifically, as the above link explains, the modulo-9 of any multi-digit number can be obrained by adding the digits until you have a single digit. That digit is the modulo-9 of the number, or, if the single digit is a 9, the modulo-9 is zero. This holds true for all multi-digit base 10 numbers regardless of the order of the digits. (It likewise works for modulo-7 of any multi-digit octal number, modulo-f of any hex number, etc.)

Thus, a base 10 number formed by the six digits {0,1,2,3,4,5} will always have a modulo-9 of 6:
0+1+2+3+4+5 = 15, => 1+5 = 6
A number formed by the six digits {1,2,3,4,5,6} will always have a modulo-9 of 3:
1+2+3+4+5+6 = 21, => 2+1 = 3
Since 9, 6, and 3 are evenly divisible by 3, any number formed by either of these sets of six digits will be evenly divisible by 3, and therefore not prime.

2 members found this post helpful.

Now, here's a fun guess-the-number trick you can play on your friends using the modulo-9 phenonmenon:

1. Tell your friend(s) to pick any number with 3 or more digits, without revealing it to you. It has to have at least two different digit values. e.g. 777 not allowed. Zeroes OK, but no leading zero. e.g. they pick 1652

2. Next, they scramble the digits to make a different number. e.g 6215

3. Now they subtract the smaller number from the larger. 6215 - 1652 = 4563

4. Now they eliminate any one of the digits. (NOTE: They may NOT eliminate a zero) e.g. They eliminate the 5, leaving 463

5. You haven't seen any of the numbers or operations so far. You ask them for the number they have left. They say "463"

6. Add the digits in your head, you get 13 and then add those two digits to get 4. So modulo-9 of 463 is 4.
Subtract 4 from 9, giving 5.
You say "You eliminated a five."
(If your modulo-9 digit is 9, they eliminated a 9. You would also get modulo-9 = 9 if they eliminated a zero, but you forbad that in step 4 above.)

7. They say, "Lucky guess; Bet you can't do it again." But, it works every time, providing everyone does their math correctly. If you 'guess' the wrong digit, you can be sure that either your friends or you made a mistake, or didn't follow the steps correctly.


Here's why it works:

The number they pick in step 1, and its scrambled step-2 counterpart both have the same modulo-9 value.

Subtracting the smaller from the larger will always yield a number with modulo-9 of zero (or 9). Note 4563 is evenly divisble by 9.

Eliminating a digit in step 4 now produces a number whose modulo-9 when added to the eliminated digit will equal 9.

By quickly calculating the modulo-9 of this number, you can know the digit that was eliminated.


One last hint:
You can speed up you mental calculation by eliminating any 0s, 9s, and digits that add up to 9. In the example, eliminate the 6 and 3 from 463, leaving 4.

(I used to play around with this in high school study hall in lieu of, say, studying my French vocabulary.)

2 members found this post helpful.

One more little detail:

It may rarely happen that when you tell your friend(s) to eliminate one of the digits (step 4 above), they may say "But there's only one digit left", in that rare case, you can tell them in all confidence that that one digit is a 9.

e.g. 443, scrambled 434, subtract = 9