Puzzles
2001/2002 Puzzles
11 February 2002 (Four Four-Digit Primes)
The problem statement from the Ole Miss Problems of the Week page is:
A, B, C, and D represent different digits. AACA, ADDD, BCDB, and BDAC represent four different four-digit prime numbers. Determine the sum of all four four-digit prime numbers (AACA + ADDD + BCDB + BDAC).
Why, that sounds remarkably like a search problem, with a sum added as camouflage. Let us see what we can do with this.
A, B, C, and D represent different digits. That is simple enough. We can just have four nested loops, each going through all values. We can also test at the start of each loop as to whether the current value repeats any value in the outer loops. If so, we can just try the next value. We can also start the loops for A and B at 1, rather than 0, as the leading digits of all four numbers must be non-zero (in order for them to be four-digit numbers).
AACA, ADDD, BCDB, and BDAC all are prime numbers. This is simple enough. We can use the NEXTFACT routine from the factorization program to determine if the number is prime.
Now, we need to give the sum of the primes. We can add up the four-digit numbers as we generate them; we will display the sum if all four four-digit numbers are prime.
So, we pseudocode this algorithm:
for a := 1 to 9
do
begin
for b := 1 to 9
do
begin
if b ≠ a
then
begin
for c := 0 to 9
do
begin
if (c ≠ a) and (c ≠ b)
then
begin
for d := 0 to 9
do
begin
if (d ≠ a) and (d ≠ b) and (d ≠ c)
then
begin
t := 1101 * a + 10 * b;
s := t;
if isPrime (t)
then
begin
t := 1000 * a + 111 * d;
s := s + t;
if isPrime (t)
then
begin
t := 1001 * b + 100 * c + 10 * d;
s := s + t;
if isPrime (t)
then
begin
t := 1000 * b + 100 * d + 10 * a + c;
s := s + t;
if isPrime (t)
then
begin
{ display a, b, c, d, s }
end
end
end
end
end
end
end
end
end
end
end;
{ display "Done" }
Well, this is easy enough to program for the calculator, so we do it:
Program P0211021 (379 bytes):
; Variables:
; A is number to test for primality (input to NEXTFACT)
; B is lowest possible factor (input to NEXTFACT) (always set to 0)
; F is digit a
; G is digit b
; H is digit c
; I is digit d
; J is sum of primes
;
; Symbols:
; -> is assignment arrow
; >= is greater than or equal to relational
; => is conditional operation
; <> is not equal to relational
; _ is display triangle
1->F ; Loop through a from 1 to 9
Lbl 0 ; Label 0: have a new a value
F>=10=>Goto 8 ; If digit a done, exit loop
1->G ; Loop through b from 1 to 9
Lbl 1 ; Label 1: have a new b value
F=G=>Goto 6 ; If digit b = digit a, try next value
G>=10=>Goto 7 ; If digit b done, exit loop
0->H ; Loop through c from 0 to 9
Lbl 2 ; Label 2: have a new c value
F=H=>Goto 5 ; If digit c = digit a, try next value
G=H=>Goto 5 ; If digit c = digit b, try next value
H>=10=>Goto 6 ; If digit c done, exit loop
0->I ; Loop through d from 0 to 9
Lbl 3 ; Label 3: have a new d value
F=I=>Goto 4 ; If digit d = digit a, try next value
G=I=>Goto 4 ; If digit d = digit b, try next value
H=I=>Goto 4 ; If digit d = digit c, try next value
I>=10=>Goto 5 ; If digit d done, exit loop
1101F+10H->A ; Figure first candidiate prime
A->J ; Initialize sum of primes
0->B ; Start factor search at 2
Prog "NEXTFACT" ; Search for a factor
A<>1=>Goto 4 ; If the first candidate is composite, try next
; digit d value
1000F+111I->A ; Figure second candidate prime
A+J->J ; Accumulate sum of primes
0->B ; Start factor search at 2
Prog "NEXTFACT" ; Search for a factor
A<>1=>Goto 4 ; If the second candidate is composite, try
; next digit d value
1001G+100H+10I->A ; Figure third candidate prime
A+J->J ; Accumulate sum of primes
0->B ; Start factor search at 2
Prog "NEXTFACT" ; Search for a factor
A<>1=>Goto 4 ; If the third candidate is composite, try next
; digit d value
1000G+100I+10F+H->A; Figure fourth candidate prime
A+J->J ; Accumulate sum of primes
0->B ; Start factor search at 2
Prog "NEXTFACT" ; Search for a factor
A<>1=>Goto 4 ; If the fourth candidate is composite, try
; next digit d value
100000(10(10(10F+G)+H)+I)+J_
; Display individual digits and sum
Lbl 4 ; Label 4: get next d digit
I+1->I ; Increment d digit
Goto 3 ; Use it
Lbl 5 ; Label 5: get next c digit
H+1->H ; Increment c digit
Goto 2 ; Use it
Lbl 6 ; Label 6: get next b digit
G+1->G ; Increment b digit
Goto 1 ; Use it
Lbl 7 ; Label 7: get next a digit
F+1->F ; Get next a digit
Goto 0 ; Use it
Lbl 8 ; Label 8: nested loops done
"Done" ; Report completion
We run this program, and, sure enough, in a little over a minute and a half, it reports a solution:
137910880
We interpret this as the digits A, B, C, and D being 1, 3, 7, and 9; and the sum of the various primes is 10880.
It takes a while longer for the program to determine that it has found all solutions, though. Approximately 45 minutes later, it finally reports:
Done
Well, we have a solution, but in thinking it over we decide it is ugly. Our solution essentially generates all possible combinations of distinct digits: A has 9 choices, B has 8, C has 8, and D has 7, for a total of 4032 combinations. While this is better than all four-digit numbers (9000 combinations), there has to be a better way. And indeed there is.
We waited to test primality until all four digits had been generated. What if, instead, we test primality as soon as the digits are available? And if we do that, what is the best order in which to generate digits?
The first four-digit prime, AACA, requires A and C. The second, ADDD, requires A and D. The third, BCDB, requires B, C, and D. The last, BDAC, requires all four. So if we generate A and C first, and test AACA, then we can avoid generating B and D if A and C together do not work.
So our pseudocode should actually be:
for a := 1 to 9
do
begin
for c := 0 to 9
do
begin
if a ≠ c
then
begin
if isPrime (1101 * a + 10 * c)
then
begin
for d := 0 to 9
do
begin
if (a ≠ d) and (c ≠ d)
then
begin
if isPrime (1000 * a + 111 * d)
then
begin
for b := 1 to 9
do
begin
if (a ≠ b) and (c ≠ b) and (d ≠ b)
then
begin
if isPrime (1001 * b + 100 * c + 10 * d) and
isPrime (1000 * b + 100 * d + 10 * a + c)
then
begin
{ display a, b, c, d and sum }
end
end
end
end
end
end
end
end
end
end;
{ display "Done" }
This is as easy to program as the last one. However, there is one difference: since we do not ever form the primes explicitly, we do not have them lying around to sum. We realize, though, that the sum AACA + ADDD has 2 A's in the thousands place, 1A and 1D is the hundreds place, 1C and 1D in the tens place, and 1A and 1D in the ones place. Similarly, given A, B, C, and D, we can write the sum of the primes as 2111A + 2001B + 111C + 221D; the digits of the coefficients are the number of times the digit appears in the respective place.
So now we program this algorithm. It is:
Program P1102022 (367 bytes):
; Variables:
; A is number to test for primality (input to NEXTFACT)
; B is lowest possible factor (input to NEXTFACT) (always set to 0)
; F is digit a
; G is digit b
; H is digit c
; I is digit d
;
; Symbols:
; -> is assignment arrow
; >= is greater than or equal to relational
; => is conditional operator
; <> is not equal to relational
1->F ; Loop digit a from 1 to 9
Lbl 0 ; Label 0: new digit a value
F>=10=>Goto 8 ; If digit a is done, report finish
0->H ; Loop digit c from 0 to 9
Lbl 1 ; Label 1: new digit c value
F=H=>Goto 6 ; If digit c is not distinct, try next value
H>=10=>Goto 7 ; If digit c is done, try next digit a
1101F+10H->A ; Form AACA
0->B ; Start factor search at 2
Prog "NEXTFACT" ; Attempt factorization
A<>1=>Goto 6 ; If AACA is composite, try next digit c
0->I ; Loop digit d from 0 to 9
Lbl 2 ; Label 2: new digit d value
F=I=>Goto 5 ; If digit d is not distinct,
H=I=>Goto 5 ; try next value
I>=10=>Goto 6 ; If digit d is done, try next digit c
1000F+111I->A ; Form ADDD
0->B ; Start factor search at 2
Prog "NEXTFACT" ; Attempt factorization
A<>1=>Goto 5 ; If ADDD is composite, try next digit d
1->G ; Loop digit b from 1 to 9
Lbl 3 ; Label 3: new digit b value
F=G=>Goto 4 ; If digit b is
H=G=>Goto 4 ; not distinct,
I=G=>Goto 4 ; try next value
G>=10=>Goto 5 ; If digit b is done, try next digit d
1001G+100H+10I->A ; Form BCDB
0->B ; Start factor search at 2
Prog "NEXTFACT" ; Attempt factorizaton
A<>1=>Goto 4 ; If BCDB is composite, try next digit b
1000G+100I+10F+H->A; Form BDAC
0->B ; Start factor search at 2
Prog "NEXTFACT" ; Attempt factorization
A<>1=>Goto 4 ; If BDAC is composite, try next digit b
100002111F+10002001G+1000111H+100221I_
; Report digits and sum
Lbl 4 ; Label 4: advance digit b value
G+1->G ; Advance digit b value
Goto 3 ; Go through loop again
Lbl 5 ; Label 5: advance digit d value
I+1->I ; Advance digit d value
Goto 2 ; Go through loop again
Lbl 6 ; Label 6: advance digit c value
H+1->H ; Advance digit c value
Goto 1 ; Go through loop again
Lbl 7 ; Label 7: advance digit a value
F+1->F ; Advance digit a value
Goto 0 ; Go through loop again
Lbl 8 ; Label 8: all digit attempted
"Done" ; Report completion
When we run this program, it is indeed much faster. The solution:
137910880
is displayed in under half a minute; the final
Done
Is displayed in less than another minute and a half.
Turning the problem into a two minute search on the calculator seems good enough.
[ Previous page | Top of page | Next page ]
Copyright © 2002 Brian Hetrick
Page last updated 24 March 2002.
