Previous page Next page Navigation bar

Puzzles

Prior to 2001 Puzzles

13 February 2000 (An Average Prime)

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

Find three different two-digit prime numbers such that the average of all three is prime and the average of any two is also prime.

Well, that certainly is a pretty problem. We could poke around through the prime numbers looking at random triples of prime numbers and see whether their averages are prime. We could pick prime numbers and try to find other primes such that the first primes were their averages. But both of these approaches looks tedious and boring.

I know! We can write a program for our CFX-9850G or FX-7400G programmable calculator! The calculator will not get bored, we will have our answer, and everyone will be happy. Amazing how we thought of that alternative, isn’t it?

Let us think about what the program will need to do. First, it will need to get three distinct primes — call them A, B, and C. Then it will need to take the average of any pair, and the average of all three. These values will be (A+B)/2, (A+C)/2, (B+C)/2, and (A+B+C)/3. And it will need to test whether these averages are primes.

We could use the primality testing program we wrote for the Prime 500 puzzle, or we could use the NEXTFACT program from the Factorization program, to test whether the averages are primes. But it occurs to us that there will be a great many averages to test. Perhaps a faster way to do this problem would be to generate a table of all the two-digit prime numbers, then to see whether the averages are in the table. If we put the table in order, we can use a technique known as a binary search, which is very quick.

A binary search works like this. Suppose we have a list of elements in sorted order, and we want to find a particular element. We keep two indices into the list — call them i and j. We let the index i is the smallest index that could possibly be the index of the element we want — that is, we know all elements with index less than i are too small to be the element we want to find. And we let the index j be one greater than the largest index that could possibly be the index of the element we want — that is, we know all elements with index j or greater are too big to be the element we want to find. Then we narrow down the range for i and j until we either have the element we want, or show that there is no element with the value we want.

We can find initial values for i and j very easily: the value 1 serves as a starting value for i, and the number of list elements, plus 1, serves as a starting value for j. Now, to narrow the range between i and j, we first compute

k = Int ((i + j) / 2)

That is, we take the average of i and j and round down. If the element indexed by k is too small, then we can update the value of i to k+1. If the element indexed by k is too large, then we can update the value of j to k.

If we ever find that i is greater than or equal to j, then we know that there is no element having the value we want.

So our overall strategy for finding a computational solution to this puzzle is:

The easiest way to generate all triples is simply to have three indices, and step each index through its range. If there are, say e elements in the table of primes, the first index, say f, will step from 1 to e-2; the second index, say g, will step from f+1 to e-1; and the third index, say h, will step from g+1 to e. As an optimization, we can check the average of the element indexed by f and g; if it is not a prime, we do not need to check any value of h, as there is no value of h that will result in a triple meeting the conditions.

We are now ready to write the program, available here in text or as a text file with .CAT file contents. First we have the NEXTFACT program, taken verbatim from the Factorization program, which we will use as a primality tester. Then we have the P021300A program, which will do a binary search of List 1 to see if a specified element is there. Finally we have the P021300 program, which generates triples and displays all the triples found matching the criteria. As with our other programs, semicolon (“;”) indicates the start of a comment that is 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 P021300A (112 bytes):

; Variables:
;   A is the number to be found in List 1.
;   B is the lower bound on the index into List 1.  It is known that
;     the index of the element in List 1 with value A, if it exists,
;     is at least as large as B.  On exit, the index of the element
;     in List 1 is placed here, or 0 if there is no element.
;   C is the upper bound on the index into List 1.  It is known that
;     the index of the element in List 1 with value A, if it exists,
;     is strictly smaller than C.
;   D is the candidate index, the average of B and C.
;   List 1 is the list of elements.  This must be sorted in increasing
;     order.
; Symbols:
;   -> is the assignment arrow
;   >= is the greater than or equal to comparision operator
;   => is the conditional jump
;   < is the less than conditional
;   > is the greater than conditional
;   <> is the not equal to conditional
 
1->B               ; Initialize lower bound
1+Dim List 1->C    ; Initialize upper bound
Lbl 0              ; Label 0: test a new case
B>=C=>Goto 1       ;   If lower >= upper, there is no element
Int ((B+C)/2)->D   ;   Compute midpoint of [B,C) interval
List 1[D]<A=>D+1->B;   If element too small, update lower bound
List 1[D]>A=>D->C  ;   If element too big, update upper bound
List 1[D]<>A=>Goto 0;  If no match yet, try again
D->B               ; The index D is the index of the element
Goto 2             ;   and exit
Lbl 1              ; There is no element meeting the criteria
0->B               ;   Set the result to indicate that
Lbl 2              ; Exit procedure
B                  ; Return the value in Ans also

Program P021300 (384 bytes):

; Variables:
;   A is the number to be tested (input to NEXTFACT, P021300A)
;   B is the result (output from NEXTFACT, P021300A)
;   C is a counter of the primes found so far (also used by P021300A)
;   D is a candidate prime (also used by P021300A)
;   E is the number of two-digit primes found
;   F is the first index into the list of primes
;   G is the second index into the list of primes
;   H is the third index into the list of primes
; Symbols:
;   -> is the assignment arrow
;   = is the equal to relational
;   <> is the not equal to relational
;   _ is the display triangle
 
;
;  Phase 1: Find all two digit primes
;
Seq(0,A,1,100,1)->List 1
                   ; Allocate a big list
0->C               ; Zero the count of two digit primes found
For 10->D To 99    ; Check all two-digit numbers for primality
D->A               ;   Set up argument to NEXTFACT
2->B               ;   Set up argument to NEXTFACT
Prog "NEXTFACT"    ;   Check primality
If A=1             ;   Test if the number is prime
Then C+1->C        ;     If so, increment count of primes found
D->List 1[C]       ;     Save this prime in the list
IfEnd              ;   [End of test if the number is prime]
Next               ; [End of check all two-digit numbers]
Seq(List 1[A],A,1,C,1)->List 1
                   ; Resize the list of primes to have only the primes
                   ;   found
C->E               ; Save the list size in E
;
; Phase 2: find three primes where all averages are prime
;
For 1->F To E-2    ; Loop through all possible first indices
For F+1->G To E-1  ;   Loop through all possible second indices
(List 1[F]+List 1[G])/2->A
                   ;     Get the average of the F,G primes as an
                   ;       argument to P021300A
Prog "P021300A"    ;     Check whether is in the list of primes
If B<>0            ;     Test whether the average is prime
Then For G+1->H To E;      If so, loop through all possible third
                   ;         indices
(List 1[F]+List 1[H])/2->A;  Get an average of the F,H primes as an
                   ;           argument to P021300A
Prog "P021300A"    ;         Check whether is in the list of primes
If B<>0            ;         Test whether the average is prime
Then (List 1[G]+List 1[H])/2->A
                   ;           If so, get an average of G,H primes
                   ;             as an argument to P021300A
Prog "P021300A"    ;           Check whether is in the list of primes
If B<>0            ;           Test whether the average is prime
Then (List 1[F]+List 1[G]+List 1[H])/3->A
                   ;             If so, get an average of F,G,H primes
                   ;               as an argument to P021300A
Prog "P021300A"    ;             Check whether is in the list of
                   ;               primes
If B<>0            ;             Test whether the average is prime
Then 10000List 1[F]+100List 1[G]+List 1[H]_
                   ;               If so, report the primes, each with
                   ;                 two digits
IfEnd              ;             [End of test of average is prime]
IfEnd              ;           [End of test of average is prime]
IfEnd              ;         [End of test of average is prime]
Next               ;       [End of loop through third index]
IfEnd              ;     [End of test of average is prime]
Next               ;   [End of loop through second index]
Next               ; [End of loop through first index]
;
; Phase 3: Report completion
;
"Done"             ; Say we are done

So now we run the P021300 program. After a short time, the program reports:

114771

which we interpret as the three primes 11, 47, and 71. The average of 11 and 47 is 29, which is prime; the average of 11 and 71 is 41, which is prime; the average of 47 and 71 is 59, which is prime; and the average of 11, 47, and 71 is 43, which is prime. After a while more, the program reports:

Done

which means the calculator has checked all triples of two digit primes, and found and reported all that satisfy the requirements.

Well, that is pretty spiffy.

Despite the promise of the Puzzles page, I am not going to attempt an analytic solution to this problem. With some of these problems, I deem an analytic solution not worth the bother. With this one, I have no idea how to solve this analytically, so we will have to live with the computational solution.

[ 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