Primes from Digits

[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

Here's another program answering fairly meaningless questions but providing a good programming exercise with a little math mixed in.

Question 1:
How many ways can digits 1 through 9 be rearranged to form 9 digit prime numbers?

Question 2:
Using the digits 1 through 9, how many ways can  they be arranged into sets of numbers containing only primes? (Each concatenation of N digits is treated as an N-digit number.) For example, one of the qualifying sets for partition [1,2,2,2,2] is the prime set : {5, 23, 47, 61,
89}
 

Background & Techniques

The 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:

bulletUnit UIntegerPartitions provides the TIntegerPartitions class to define all of the ways that 9 digits can be split into smaller numbers.  It turns out that there are 30 ways to do this.  The unit creates an instance of the TIntegerPartition class named DefPartition during initialization which is used to enumerate the partitions.
bulletUnit UComboV2 has the TCombos class which is used to return all 9! (=362,880) permutations of the 9 digits.  UComboV2 also creates an initial instance of its class named Combos with a GetNext function used to generate all permutations for testing.   
bulletThe Mathslib unit contains the IsPrime function which tests whether each candidate number is prime.
bulletThe DFFUtils unit provides the LineNumberClicked function used to list at least some (up to the first 100) of the detailed prime sets which can be formed for any particular partition.

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 

bulletDownload  executable
bulletDownload source  (Note:  Units DffUtils, MathsLib, UComboV2, and UIntegerPartition contain routines used here and reside in our library zip file of commonly used units.  Library file DFFVLIB14 or later is required to recompile this program )
bulletDownload current library file (DFFLibV15) required to recompile this program.

Suggestions for Further Explorations

 ???
   

 

Original:  August 18, 2012

Modified:  February 18, 2016

 
  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2017, Gary Darby    All rights reserved.