LinuxQuestions.org
Latest LQ Deal: Latest LQ Deals
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices


Reply
  Search this Thread
Old 08-05-2020, 06:49 PM   #1
dogpatch
Member
 
Registered: Nov 2005
Location: Central America
Distribution: Mepis, Android
Posts: 427
Blog Entries: 4

Rep: Reputation: 189Reputation: 189
Lightbulb A curious mathematical principle


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.
 
Old 08-05-2020, 07:04 PM   #2
danielbmartin
Senior Member
 
Registered: Apr 2010
Location: Apex, NC, USA
Distribution: Mint 17.3
Posts: 1,779

Rep: Reputation: 613Reputation: 613Reputation: 613Reputation: 613Reputation: 613Reputation: 613
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

.
 
Old 08-05-2020, 07:50 PM   #3
dogpatch
Member
 
Registered: Nov 2005
Location: Central America
Distribution: Mepis, Android
Posts: 427

Original Poster
Blog Entries: 4

Rep: Reputation: 189Reputation: 189
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.
 
Old 08-06-2020, 04:09 PM   #4
dogpatch
Member
 
Registered: Nov 2005
Location: Central America
Distribution: Mepis, Android
Posts: 427

Original Poster
Blog Entries: 4

Rep: Reputation: 189Reputation: 189
Here's a hint
 
1 members found this post helpful.
Old 08-06-2020, 05:04 PM   #5
danielbmartin
Senior Member
 
Registered: Apr 2010
Location: Apex, NC, USA
Distribution: Mint 17.3
Posts: 1,779

Rep: Reputation: 613Reputation: 613Reputation: 613Reputation: 613Reputation: 613Reputation: 613
Quote:
Originally Posted by dogpatch View Post
Here's a hint
John 1:14 but where does that lead us? To the promised land? Didn't somebody else already do that?

Daniel B. Martin
 
Old 08-06-2020, 05:29 PM   #6
dogpatch
Member
 
Registered: Nov 2005
Location: Central America
Distribution: Mepis, Android
Posts: 427

Original Poster
Blog Entries: 4

Rep: Reputation: 189Reputation: 189
Click on the hyperlink 'hint'

(Nice job decoding my signature, but that wasn't the hint)
 
Old 08-07-2020, 03:49 AM   #7
mina86
Member
 
Registered: Aug 2008
Distribution: Debian
Posts: 517

Rep: Reputation: 228Reputation: 228Reputation: 228
The digits sum to a number divisible by 3.
 
Old 08-11-2020, 06:29 PM   #8
dogpatch
Member
 
Registered: Nov 2005
Location: Central America
Distribution: Mepis, Android
Posts: 427

Original Poster
Blog Entries: 4

Rep: Reputation: 189Reputation: 189
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.

Last edited by dogpatch; 08-11-2020 at 06:30 PM.
 
2 members found this post helpful.
Old 08-11-2020, 07:27 PM   #9
dogpatch
Member
 
Registered: Nov 2005
Location: Central America
Distribution: Mepis, Android
Posts: 427

Original Poster
Blog Entries: 4

Rep: Reputation: 189Reputation: 189
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.
Old 08-14-2020, 07:09 PM   #10
dogpatch
Member
 
Registered: Nov 2005
Location: Central America
Distribution: Mepis, Android
Posts: 427

Original Poster
Blog Entries: 4

Rep: Reputation: 189Reputation: 189
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
 
  


Reply

Tags
math, phenomenon, prime numbers


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
hwclock principle - what I actually do not find clear heavytull Linux - Software 2 12-16-2011 11:04 AM
LXer: Google's Schmidt says requiring stock Android would violate 'the principle of open source' LXer Syndicated Linux News 2 09-25-2010 11:13 AM
LXer: Linux Evolution Reveals Origins of Curious Mathematical Phenomenon LXer Syndicated Linux News 0 12-02-2008 07:20 PM
basic principle behind linux subsystrem sitthar Linux - General 3 04-08-2006 08:05 AM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 01:29 PM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Open Source Consulting | Domain Registration