Previous page Next page Navigation bar

Puzzles

Prior to 2001 Puzzles

19 March 2000 (Four Digit Primes)

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 ]

Previous page Top of page Next page Navigation bar

Copyright © 2001 Brian Hetrick
Page last updated 25 November 2001.

Brian’s Casio Calculator Corner

Home

Programs

Tutorial

Puzzles

Index

2001/2002

Previous years

Index

3 December 2000

27 October 2000

16 April 2000

9 April 2000

19 March 2000

13 February 2000

6 February 2000

28 November 1999

12 September 1999

8 August 1999

25 July 1999

11 July 1999

30 May 1999

4 April 1999

29 April 1996

In memoriam: Dijkstra

Site Information

Your Privacy

Site Map

E-mail

Site Technical Data