[Home] [Puzzles & Projects] [Delphi Techniques] [Math topics] [Library] [Utilities]
|
|
Problem Description
A sevenrh entry in our "Numeric T-Shirt" line: Back of T-Shirt: "Three prime 3-digit numbers that contain all
of the digits 1 through 9 and have a 3-digit sum" Front: __ __ __
Background & TechniquesThis problem is from Martin Gardner in his book "The Sixth Book of Scientific American Mathematical Games". He solves it with a little logical reasoning and some trial and error. With dumb computers, it is simpler to skip the logical reasoning part and just use trial and error. These programs are primarily programming exercises and probably not of much interest to non-programmers (unless you want to custom make a mathematical T-shirt!). So we'll skip straight to a discussion of the method the program uses to solve the problem. I decided to approach the problem if two phases. First we'll generate all 3 digit prime numbers that do not contain duplicate integers and do not contain zeros. Our solution set must be chosen from these. Button "Find Primes" does this by testing all numbers from 123 to 987 (the smallest and largest possible candidates). I copied function IsPrime from the Tshirt 5 program to test for primeness, and added functions NoDups to make sure that the prime contained no duplicate digits and NoZeros makes sure that they contain no zeros. . Numbers that pass all three tests are added to the Primes integer array and field Count keeps track of how many we have found. In phase 2, triggered by the "Find Sum" button, we'll check all possible ways to select three different numbers from this set and find the set with the smallest sum. (The original problem called for the smallest sum, I changed it to "a 3-digit sum" because I happen to know that the smallest sum has 3-digits and it just reads a little simpler.) Since there are less than 100 primes which qualify, the number of ways we can select 3 from the set is less than 100x100x100 (1,000,000), a trivial number to check for today's computers.
Since the order of the subsets does not matter, we need to examine the number of combinations of 3 number subsets selected from the entire set of primes built in Phase 1. The simplest way to select combinations of small subsets of items from a large set is with nested loops like this:
for i:=1 to count-2 do NoDups2 is a function that checks to make sure that two passed number
have no digits in common. If we find three 3-digit numbers with no digits
in common and no zeros, they must contain all of the digits
1-9. For simplicity, we'll just list each new smallest sum that we find - the
last one listed will be our answer. Running/Exploring the Program
Suggestions for Further ExplorationsMy original thought was to generate all permutations of 3 digits selected from the set of digits 1..9 and save those that passed the primeness test. Selecting permutation subsets seems more complicated than the enumerate-and-test procedure used here but it is certainly another way to skin this cat. An alternative, and simpler, version of the T-Shirt message is "The only set of 3-digit primes containing all of the digits 1 through 9 and whose sum is a 3-digit number." It's an interesting exercise to prove that this problem statement produces the same result.
|
[Feedback] [Newsletters (subscribe/view)] [About me]Copyright © 2000-2018, Gary Darby All rights reserved. |