The problem statement from the Ole Miss Problems of the Week page is:

Find five four-digit prime numbers such that the products of the digits of each four-digit prime number are also prime.

Hmm. That word, “find,” seems to indicate searching a candidate space to find a solution. There is something about that ... I remember! When we want to search a candidate space to find a solution, we frequently construct some sort of automaton to perform the search — we write a program, in other words. And, just by chance, we have a Casio CFX-9850G or FX-7400G sitting here, and it happens to be programmable. You don’t suppose we could write a program for the calculator to solve this problem, do you? What a novel and completely unexpected approach.

Well, the problem sounds simple enough. A perfectly straightforward approach would be to generate all four-digit numbers, test them for primality, form the product of the digits, test the product for primality, and display the four-digit numbers that make it through the tests.

We can use the NEXTFACT program from the Factorization program for our primality test. The only other trick would be to form the product of the digits. We can initialize a product accumulator to 1, pop the digits off the number, and multiply them into the accumulator. This requires no trickery whatever.

The programs, available here or as a text file with .CAT file contents, are as shown below. Semicolons (“;”) start comments which are not to be entered into the calculator.

Program NEXTFACT (85 bytes):

; Variables: ; A is on entry the number for which a factor is to be found, and is ; on exit the quotient of the original A and the factor found ; B is on entry the lowest number that is a possible factor (0 and 1 ; are assumed to be 2), and is on exit the smallest factor found ; Symbols: ; < is less than relational ; -> is assignment arrow ; / is division operator ; x^2 is x square operator ; > is greater than relational If B<2 ; Test if the proposed factor is less than 2 Then 2->B ; If so, replace it by 2 IfEnd ; [End of test of proposed factor] While BInt (A/B)<>A; Loop until B is a factor of A If Bx^2>A ; Test if B is larger than the largest possible ; factor of A Then A->B ; If so, A is the smallest factor Else 2B+1-2Int (B/2)->B; Otherwise, try the next odd number IfEnd ; [End of test on B too large] WhileEnd ; [End of loop until B is a factor of A] A/B->A ; Divide B out of A

Program P031900 (146 bytes):

; Variables: ; A is number to test for primality (argument to NEXTFACT) ; B is minimum test factor (argument to NEXTFACT) ; C is four digit number being tested ; D is digits of prime C remaining to be multiplied ; E is product of digits of prime C ; Symbols: ; -> is assignment arrow ; = is equal to relational ; <> is not equal to relational ; / is divide operator ; _ is display triangle For 1000->C To 9999; Loop through all four-digit numbers C->A ; Set up argument to NEXTFACT 2->B ; Set up argument to NEXTFACT Prog "NEXTFACT" ; See if number is prime If A=1 ; Test if four digit number is prime Then C->D ; If so, copy to D 1->E ; Initialize product of digits to 1 into E While D<>0 ; Loop while there are digits remaining EInt 10Frac (D/10)->E; Multiply bottom digit into E Int (D/10)->D ; Strip off bottom digit of D WhileEnd ; [End of loop while digits remaining] E->A ; Put product into NEXTFACT argument 2->B ; Set up argument to NEXTFACT Prog "NEXTFACT" ; See if product is prime If 1=A ; Test if product is prime Then C_ ; If so, display original four-digit number IfEnd ; [End of test if product is prime] IfEnd ; [End of test if four digit number is prime] Next ; [End of loop through all four-digit numbers] "Done" ; Say we are done

Now we run the program. Within the next few minutes, the program displays the five numbers:

1117 1151 1171 1511 2111

Then, after a long time, it displays the message:

Done

So, we have solved the problem. We have five four-digit prime numbers where the products of the digits are themselves prime.

But there is something funny about those prime numbers. All the digits but one are 1. Now that we think about it, we realize that of course the digits would all be 1, except for one digit, which would be a one-digit prime. Otherwise, the product of the digits would not be prime. So any number that would satisfy the requirement of the product of the digits being prime would have three digits 1, and one digit one of 2, 3, 5, or 7. Any four digit number made up of three 1s and a 3 would have a sum of digits of 6, and so would be a multiple of 3, and so would not be a prime. So any four digit prime number where the product of the digits is itself prime would have three digits 1, and one digit one of 2, 5, or 7. Actually, the last digit could not be 2 or 5, as then the entire number would be a multiple of 2 or 5, and so not a prime. There are only ten four-digit numbers for which the product of the digits is prime that we cannot immediate recognize as composite simply by looking at them: 2111, 5111, 7111, 1211, 1511, 1711, 1121, 1151, 1171, and 1117. We can easily write them down — in fact, we just did — then test them for being primes themselves.

We can do the prime checking manually, but it is just as quick to write a tiny program that generates numbers of this form and tests them for primality. It makes for a simpler program to generate {2, 5, 7} for each digit, rather than worrying about the last digit specially, so we will do that. (We know the numbers are not prime, and so they are not really candidates, but the primality test will correctly reject them.)

Program P0319001 (114 bytes):

; Variables: ; A is the number to test for primality (argument to NEXTFACT) ; B is the minimum factor (argument to NEXTFACT) ; C is the power of 10 of the digit into which primes are inserted ; D is the index of the prime being inserted ; E is the number to test for primality ; List 1 is the list of prime digits ; Symbols: ; -> is the assignment arrow ; 10^x is the ten to the x-th power key ; = is the equality relational ; _ is the display triangle {2,5,7}->List 1 ; Initialize the set of prime digits For 0->C To 3 ; Loop through ones to thousands places For 1->D To 3 ; Loop through the prime digits 1111+(List 1[D]-1)10^xC->E ; Form the number with 1 digits and the prime E->A ; Set up for the 2->B ; call to NEXTFACT Prog "NEXTFACT" ; Call NEXTFACT to check for primality If A=1 ; Test if the constructed number is prime Then E_ ; If so, display it IfEnd ; [End of test if constructed number is prime] Next ; [End of loop through prime digits] Next ; [End of loop through places] "Done" ; Say we are done

We run this program, and the same primes as before are generated, but they come out about as quickly as we can press the EXE key to acknowledge them.

Even though this last method is implemented as a calculator program, the reversal of the test — and its limiting the search space to ten elements! — is close enough to an analytical solution that I am going to count it as such. So this time we have both computational and analytical solutions in one.

I gratefully acknowledge the assistance of Dr. David Rock, the author of the Ole Miss Problem of the Week puzzles, for reminding me that 1 is a digit. Perhaps had I written and run the program first, I might have figured it out on my own. However, I struggled with this problem for some time, convinced the product of the digits would have to be composite, until I received Dr. Rock’s help.

[ Previous page | Top of page | Next page ]

Copyright © 2001 Brian Hetrick

Page last updated 25 November 2001.