' Puzzlet # 066
' Find all 3-digit primes which take just 5
' steps in the Kaprekar Process (see below)
' to reach 495.
' By Dave Ellis.

declare IsPrime (p: int)
declare PadLeadingZeros (s$: string, n: int)
declare SortString (n$: string)
declare ReverseString (n$: string)
def count, num, temp: int
def num$, temp$, reverse$: string
openconsole
print "Searching ...": print

for num = 101 to 997
    if IsPrime(num): 'is it a prime?
        num$ = ltrim$(str$(num))
        count = 0
        do: 'this is the Kaprekar process
            temp$ = SortString(num$): 'sort into ascending order
            reverse$ = ReverseString(temp$): 'sort into reverse order
            temp = val(reverse$) - val(temp$): 'subtract them
            num$ = ltrim$(str$(temp)): 'restore leading zeros
            PadLeadingZeros(num$, 3)
            count = count + 1: 'count the number of iterations
        until temp = 495 | count > 5
        if count = 5 & temp = 495
            print num,
        endif
    endif
next num

print: print "No More!"
print: print "Press a key to exit... ",
do: until inkey$ <> ""
closeconsole
end

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 SortString(n$)
' Sorts the contents of n$ into ascending
' order using a simple bubble sort
def endpoint, flag, i: int
def hold$, temp$, t1$, t2$: string
temp$ = n$
endpoint = len(temp$) - 1
do
    flag = -1
    for i = 1 to endpoint
        t1$ = mid$(temp$, i, 1)
        t2$ = mid$(temp$, i+1, 1)
        if val(t2$) < val(t1$)
            flag = 0
            replace$ temp$, i, 1, t2$
            replace$ temp$, i + 1, 1, t1$
        endif
    next i
    endpoint = endpoint - 1
until flag = -1
return temp$   

sub ReverseString(n$)
' returns the reverse of string st1$
' example: str1$ = "knob" returns "bonk"
def i, L: int
def rev$: string
L = len(n$)
rev$ = ""
for i = L to 1 #-1
    rev$ = rev$ + mid$(n$, i, 1)
next i
return rev$

sub PadLeadingZeros(s$, n)
' s$ is padded with as many leading zeros
' as necessary to make it equal in length
' to n, and then returned.
def temp$, zero$: string
def L: int
temp$ = s$
L = len(temp$)
zero$ = string$(n-L, "0")
temp$ = append$ (zero$, temp$)
return temp$
     
' The  Kaprekar Process must always  begin
' with  a 3-digit integer and will  always
' terminate with the same number, 495. For
' example, take 323:
'
' 1.  Sort  its digits in ascending order,
'     calling this A.  So A = 233.
' 2.  Take the reverse of A and call it B,
'     so B = 332.
' 3.  Subtract the smaller from the larger
'     number, giving B - A = 99. Call this
'     099 to preserve the 3-digit format.
' 4.  Repeat the process, giving 990 - 099
'     = 891.
' 5.  Keep on repeating, giving the series
'     323, 099, 891, 792, 693, 594, 495.
'
' As predicted, the series terminated with
' 495. It always does, regardless of which
' 3-digit integer you start with.
'
' In  this Puzzlet,  you must always start
' with a prime number. The challenge is to
' find those 3-digit primes which complete
' the sequence in exactly 5 moves.

PROGRAM NOTES

Variable num is used as the iterator to investigate all possible 3-digit integers.  Each one is tested for primality by submitting it as the parameter to function IsPrime(). Those that pass this test are converted into a string num$, for further processing.

In this Puzzlet, we're only interested in numbers that take six iterations of the Kaprekar process to terminate.  The iteration count is tracked by variable count, which is set to zero at the beginning of the Kaprekar test.

The code breaks the Kaprekar process down into six steps, as follows:

1.	temp$ = SortString(num$). This command passes num$ as parameter to the function SortString(), which sorts the numerical value of the characters of its argument in ascending order and returns the result to the calling routine, where they are stored in variable temp$.

2.	reverse$ = ReverseString(temp$). This command passes temp$ as parameter to the function ReverseString(), which reverses theorder of the characters of its argument and returns the result to the calling routine, where they are stored in variable reverse$.

3.	temp = val(reverse$) - val(temp$). This command calculates the difference between the numerical values of reverse$ (derived at step 2 above) and temp$ (derived at step 1 above) and stores the result in integer variable temp.

4.	num$ = ltrim$(str$(temp)). This command converts the value stored in temp to a string and stores the result in variable num$, overwriting the previously-stored contents.  In this way, num$ is changed according to the Kaprekar process.

5.

PadLeadingZeros(). The current contents of num$ were derived in step 2 by a reversal process. If there had been a trailing zero at this point, such as 470, it would have been lost in step 3 by the use of the val function. We need to put that zero back in now as a (padded) leading zero. This command does exactly that. Note that there are two parameters: the string to be padded, and the number of characters it must contain after any necessary padding.

6.	count = count + 1. The variable count is incremented so that the number of Kaprekar iterations can be tracked.

If the value obtained at step 3 and stored in temp equals 495, no further executions of the Kaprekar DO loop are necessary.  Also, if count  is greater than 5, regardless of the value in temp, the loop can be exited.

After exiting the DO loop, a check is made on temp and count.  If they are 495 and 5 respectively, we have a valid result and it's printed out. Then num is incremented and the next value investigated until all have been checked.

There are 143 3-digit primes, but it turns out only 18 of them complete the Kaprekar process in exactly 5 moves:

109, 113, 131, 311, 313, 331, 353, 409, 509, 557, 577, 709, 757, 797, 809, 907, 977, 997.