Previous page Next page Navigation bar

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 ]

Previous page Top of page Next page Navigation bar

Copyright © 2002 Brian Hetrick
Page last updated 24 March 2002.

Brian’s Casio Calculator Corner

Home

Programs

Tutorial

Puzzles

Index

2001/2002

Index

15 April 2002

11 February 2002

1 October 2001

24 September 2001

13 August 2001

30 July 2001

18 June 2001

4 June 2001

21 May 2001

7 May 2001

30 April 2001

23 April 2001

9 April 2001

18 February 2001

4 February 2001

29 January 2001

Previous years

In memoriam: Dijkstra

Site Information

Your Privacy

Site Map

E-mail

Site Technical Data