Puzzles

2001/2002 Puzzles

13 August 2001 (Reversing Primes)

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

The prime number 13 has an interesting quality. When its digits are reversed, the new number 31 is also prime. Find the sum of all prime numbers greater than 10 yet less than 125 that share this quality.

Hmm. Sounds like a search problem to me — find all the numbers with a certain property, and do something with them. That certainly seems like some sort of mechanized process would be useful. Fantastically enough, we happen to have a CFX-9850G or FX-7400G programmable graphics calculator right here. Perhaps — I realize the novelty and complete unexpectedness of this idea requires a stretch of the imagination — we could program the programmable calculator to come up with the answer to this problem.

It seems simple enough. Loop through the numbers from 10 to 125, pick out the primes, reverse their digits, check to see whether that is a prime too, and if so, add in the original number to an accumulator.

We can use NEXTFACT from the Factorization program to check whether the numbers are prime. We can reverse the digits of the primes by popping digits off the bottom and slapping them together the other way around. Seems straightforward.

So, once again the programs are presented in text here, or in a text file with .CAT file contents. And as always semicolons (“;”) start comments that 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 P081301 (140 bytes):

```; Variables:
;   A is number to factor (argument to/result from NEXTFACT)
;   B is factor (argument to/result from NEXTFACT)
;   C is candidate number between 10 and 125
;   D is sum of primes that are also primes when reversed
; Symbols:
;   -> is assignment arrow
;   = is equality relational
;   <> is inequality relational

0->D               ; Initialize sum of primes to zero
For 10->C To 125   ; Loop through all numbers between 10 and 125
C->A               ;   Set up for NEXTFACT call
0->B               ;   Set up for NEXTFACT call
Prog "NEXTFACT"    ;   Try to factor number between 10 and 125
If A=1             ;   Test whether number is prime
Then C->B          ;     If so, copy it to B
0->A               ;     Initialize reversal of digits
While B<>0         ;     Loop while there are any digits left
10A+10Frac (B/10)->A;      Put bottom digit onto A
Int (B/10)->B      ;       Remove it from B
WhileEnd           ;     [End of loop while any digits left]
Prog "NEXTFACT"    ;     Try to factor prime with reversed digits
If A=1             ;     Test whether it too is prime
Then C+D->D        ;       If so, add original number to sum
IfEnd              ;     [End of test whether reversed is prime]
IfEnd              ;   [End of test whether number is prime]
Next               ; [End of loop through 10 to 125]
D                  ; Display sum at end
```

A quick run of the program, and after about 20 seconds the calculator displays:

```750
```

Well, that is interesting.

Perhaps I have too little number theory to appreciate this problem, but I have no idea how to analytically do this problem, how to generalize it in an interesting way, or even what we are supposed to have learned from this exercise. There are 12 primes that go into this sum, but that does not seem particularly relevant. There are 52 of these reversible primes between 10 and 1000, and they add up to 23892, and that does not seem relevant either. There are 144 reversible primes between 10 and 3500, and they add up to 214400; at least those, too, are “round” numbers. The incidence of reversible primes does not appear to have any particularly interesting features, at least up to 9857 (the 250th reversing prime greater than 10), where the sum is 1023830. Sigh. It’s a terrible thing to lose one’s mind, as a certain United States vice president said.