T-Shirt #7

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

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.

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

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}
               sum:=n1+n2+n3; {add them up}
               {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.  

Running/Exploring the Program 

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:February 18, 2016
 
  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2017, Gary Darby    All rights reserved.