[Home] [Puzzles & Projects] [Delphi Techniques] [Math topics] [Library] [Utilities]
|
|
Problem DescriptionHere's another program answering fairly meaningless questions but providing a
good programming exercise with a little math mixed in. Background & TechniquesThe original program has been setting in my "Future Projects" folder for a number of years. So long in fact, that I have no idea of the source of the problem. I ran across it the other day and decided to revisit. Question1:I added Question 1 for this update, It turns out that none of the permutations of 123456789 are prime. If I were a little smarter, I could have determined that without writing the code to test. The sum of the digits 1 through 9 is 45 which is a multiple of 3. There is a divisibility rule which says that any integer whose digit sum is a multiple of 3 is divisible by 3 so every permutation of digits 1 through 9 sums to 45 and is therefore a multiple of 3 and therefore not prime. Using Google, failed to reveal why the rule is valid, but a little analysis provides the answer. A formal proof could be made by induction, but to understand it quickly, just consider any 3 digit number, abc. Its value can be expressed as N=100a+10b+c and we want to prove that if a+b+c =3X for some integer X, then N is a multiple of 3. If we rewrite the expression for N as 99a+a+9b+b+c then we can rearrange the terms to get get N=99a+9b+a+b+c= 99a+9b+3X = 3*(33a+3b+X), clearly a multiple of 3. Question 2:This one was more challenging and the solution uses several units from our DFF Library:
The strategy for solving is to generate all permutations of the 9 digits and for each arrangement check all 30 ways to split it into smaller numbers and check each of the smaller numbers for prime. Actually, since partitions are generated from smaller to larger number of pieces ([9], [8,1], [7,2],...., [2,1,1,1,1,1,1,1], [1,1,1,1,1,1,1,1,1]. The last partition is the only one in which the one digit prime in the last member could be the single digit prime 2 or 5 and since there are only four single digit primes (2,3,5,7), no partition with more than 4 single digit primes need be checked. We just check that the rightmost digit of any permutation is 1, 3, 7, or 9 and eliminate the others with no further testing. This reduces the number of prime tests significantly and allows the problem to be solved in a couple of seconds. The final tricky bit was allowing the user to click on any summary line of the display which shows the number of prime set solutions for each of the 30 possible partitions. Clicking calls LineNumberClicked to find which line, then extracts the partition (the string surrounded by square brackets) and calls a FindPrimeSets function which performs the search across all permutations for the single partition clicked. Running/Exploring the Program
Suggestions for Further Explorations
|
[Feedback] [Newsletters (subscribe/view)] [About me]Copyright © 2000-2018, Gary Darby All rights reserved. |