### Search

 Search WWW Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

Support DFF - Shop

If you shop at Amazon anyway,  consider using this link.

We receive a few cents from each purchase.  Thanks

### Support DFF - Donate

If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Mensa® Daily Puzzlers

For over 15 years Mensa Page-A-Day calendars have provided several puzzles a year for my programming pleasure.  Coding "solvers" is most fun, but many programs also allow user solving, convenient for "fill in the blanks" type.  Below are Amazon  links to the two most recent years.

(Hint: If you can wait, current year calendars are usually on sale in January.)

### Contact

 Search DelphiForFun.org only

### 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 & Techniques

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

 Combinations There are actually only 83 primes generated by phase  1.  Therefore the number of subsets to check is the number of ways we can select unique sets of 3 numbers from the 83.  This is the number of Combinations of 83 things taken 3 at a time, commonly denoted as C(83,3).  The formula for C(n,r) is  n!/(n-r)!/r!.  In our case this is 83x82x81/(3x2) or only 91,881 cases to test!.

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
begin
n1:=Primes[I]; {get the first prime}
for j:= i+1 to count-1 do
begin
n2:=Primes[j]; {get the second prime}
if nodups2(n1,n2) then {if unique from n1 then...}
for k:= j+1 to count do
begin
n3:=Primes[k]; {get the third prime}
if nodups2(n1,n3) and nodups2(n2,n3) then
begin  {we have found three primes containing all 9 digits}
{etc.- a few more lines of code to save and list the set with the smallest sum }
end;
end;
end;
end;

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.

### Suggestions for Further Explorations

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

 Originally posted: June 9,  2003 Modified:July 29, 2017