| '
Puzzlet #090 ' Find all 5-digit integers whose digits are ' all different and in increasing order, and ' which are prime numbers when read either ' forward or backwards(emirps). ' By Dave Ellis. declare AllDigitsDifferent(a: int) declare IsPrime(p: int) declare ReverseInteger(n: int) declare IsOrdered(o: int) declare PrintResult() def it1, it2: int openconsole print "Searching ...": print print "These are all primes:" it1 = 12347 do if AllDigitsDifferent(it1) if IsOrdered(it1) if IsPrime(it1) it2 = ReverseInteger(it1) if IsPrime(it2) PrintResult() endif endif endif endif it1 = it1 + 2 until it1 > 36789 print: print "No more!" print: print "Press a key to exit ..." do: until inkey$ <> "" closeconsole end sub AllDigitsDifferent(a) ' if all the digits of a are unique, ' returns -1, else returns 0 def flag, i, j, L: int a$ = ltrim$(str$(a)) L = len(a$) i = 1 flag = -1 do j = i + 1 do p$ = mid$(a$, i, 1) q$ = mid$(a$, j ,1) if q$ = p$ flag = 0 endif j = j + 1 until flag = 0 | j > L i = i + 1 until flag = 0 | i > L - 1 return flag sub IsPrime(p) ' if p is prime, returns 1, ' otherwise returns 0 def flag, i, root: int if p = 2 | p = 3 flag = -1 else if p % 2 = 0 | p < 2 flag = 0 else root = sqrt(p) i = 3 flag = -1 do if p % i = 0 flag = 0 else i = i + 2 endif until flag = 0 | i > root endif endif return flag sub ReverseInteger(n) ' returns the reverse of integer n ' example: n = 1234 returns 4321 def i, L: int def n$, rev$: string n$ = ltrim$(str$(n)) L = len(n$) rev$ = "" for i = L to 1 #-1 rev$ = rev$ + mid$(n$, i, 1) next i return val(rev$) sub IsOrdered(o) 'if the digits of argument o are 'arranged in ascending order, returns '-1 (TRUE), else returns 0 (FALSE) def flag, i, L: int o$ = ltrim$(str$(o)) q$=left$(o$, 1) L = len(o$) i = 1 flag = -1 do r$ = mid$(o$, i+1, 1) if val(r$) <= val(q$) flag = 0 endif i = i + 1 q$ = r$ until flag = 0 | i = L return flag sub PrintResult print it1, print "<---> ", print it2 return |
| PROGRAM NOTES Before we look at the code, let's think about the search range. The smallest integer having 5 different digits is 12345. However, a prime number cannot end in a 5 or 6. Therefore, the lower limit is set to 12347. The upper limit with 5 different digits is 67890. A prime number can't end in a zero, so we have to go for 56789, which keeps the digits in ascending order. This has a problem: its reverse, 98765, has a 5 at the end, which is illegal for prime numbers. So also would be 4 and it becomes necessary to go for 98763, which inverts again to 36789, our upper limit. The usual top-down approach is applied to this program. The main routine tells you everything you need to know. In the following extract, the lines are numbered to make it easier to follow the description. |
| 1 2 3 4 5 6 7 8 9 10 11 12 13 |
do if AllDigitsDifferent(it1) if IsOrdered(it1) if IsPrime(it1) it2 = ReverseInteger(it1) if IsPrime(it2) PrintResult() endif endif endif endif it1 = it1 + 2 until it1 > 36678 |
| Here's an exegesis of the code, based on the line numbers above: |
| 1 |
do. Opens the main DO-LOOP. |
| 2 |
if AllDigitsDifferent(it1). Variable it1 holds the 5-digit integer currently being investigated. It's passed as parameter to function AllDigitsdifferent(). If the digits of it1 are all unique, this function returns -1 (TRUE), otherwise 0 (FALSE). |
| 3 |
if IsOrdered(it1). If it1's digits are all
different, it's passed as parameter to function IsOrdered(). If the digits of it1 are in ascending order from
left to right, this function returns -1 (TRUE), otherwise 0 (FALSE). |
| 4 |
if IsPrime(it1). If it1's digits are in ascending order, line 4 passes it as the parameter to function IsPrime(), which returns TRUE or FALSE according to whether it's prime or not. |
| 5 |
it2 =
ReverseInteger(it1). If it1 is prime, we need to
find out if its reversed value is also prime. To do this, it1 is passed to function ReverseInteger(), whose job is to
reverse the digits of its argument and return the result to the calling
routine. In this application, the returned value is stored in variable it2. |
| 6 |
if IsPrime(it2). Submits the newly-generated it2 to the already-used function IsPrime(). |
| 7 |
PrintResult(). If this second call to IsPrime() also returns a TRUE, we have a valid result and it's passed to the subroutine PrintResult(). |
| 8 |
endif. Housekeeping - closes IF-ENDIF clause opened in line 6. |
| 9 |
endif. Housekeeping - closes IF-ENDIF clause opened in line 4. |
| 10 |
endif. Housekeeping - closes IF-ENDIF clause opened in line 3. |
| 11 |
endif. Housekeeping - closes IF-ENDIF clause opened in line 2. |
| 12 |
it1 = it1 + 2. Increments it1 ready for the next investigation. Notice that it's incremented by 2 instead of 1. This keeps it odd, so it does at least have a chance of being prime. This makes the code run a lot faster, since only half the available integers need to be looked at. You may have noticed that, in spite of this, IsPrime() can handle even numbers anyway , which seems wasteful. You're right! But it's a generic all-purpose function, and I left it in there anyway. |
| 13 |
until it1 > 36678 Prevents it1 being incremented beyond 36789. Once this point is reached, the progam stops. See above for the reason this value is the maximum permitted. |
| The
functions and subroutine called by the main routine are all just about
self-explanatory, and have all been used in previous Puzzlets. If you
want to know more about them please either refer back, or e-mail me
directly. |
| When
you run the program, you'll see the inset printed out onto your
computer's screen. There are six solutions, each with orderered, unique digits and making reversible primes. |
|
Searching
... These are all primes: 12689 <---> 98621 13457 <---> 75431 13469 <---> 96431 13789 <---> 98731 15679 <---> 97651 34589 <---> 98543 No more! Press a key ... |