Puzzlet 77 - The Answer

THE PUZZLET PAGE

PUZZLET 077 - THE SOLUTION

' Puzzlet #077.
' The six digits of a prime number are
' in ascending order, and they're all
' different. The sum of the digits is
' another prime.
' Example: Prime 124679, digit Sum 29.
' Can you find any other prime numbers
' with exactly these characteristics?
' By Dave Ellis.

declare IsPrime (p: int)
declare IsSorted (s$: string)
declare AllDigitsDifferent(a$: string)
declare SumStringDigits(s$: string)
declare PrintResult()

def n, digSum: int
def num$: string

openconsole
print "Searching ...": print
n = 123457

do
    num$ = ltrim$(str$(n))
    if IsSorted(num$)
        if AllDigitsDifferent(num$)
            digSum = SumStringDigits(num$)
            if IsPrime(digSum)
                if IsPrime(n)
                    PrintResult()
                endif
            endif
        endif
    endif
    if n % 5 = 0
        n = n + 4
    else
        n = n + 2
    endif
until n > 345679

print: print "No more!"
print: print "Press any 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 IsSorted (s$)
' if the ascii values of s$ are
' arranged in ascending order,
' returns -1, else returns 0.
def flag, i, L: int
def p$, q$: string
L = len(s$) -1
i = 1
flag = -1
do
    p$ = mid$(s$, i, 1)
    q$ = mid$(s$, i + 1, 1)
    if p$ > q$
        flag = 0
    endif
    i = i + 1
until flag = 0 | i > L
return flag

sub AllDigitsDifferent(a$)
' if every character of a$ is unique
' (that is, there are no repeated
' characters in the a$), returns -1,
' else returns 0.
def flag, i, j, L: int
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 SumStringDigits(s$)
' s$ must contain only numerics, no
' alpha characters. Returns the
' sum of the values of the characters
' of s$.
def i, L, sum: int
L = len(s$)
sum = 0
for i = 1 to L
    sum = sum + val(mid$(s$, i, 1))
next i
return sum

sub PrintResult
' pretty printer
print "Prime: ",num$,". ",
print "Sum of Digits: ", digsum
return



PROGRAM NOTES

We begin by determining the search range. All digits must be different and in ascending order, so let's start with 123456. This is even, so it can't be a prime. Without digging any deeper, we just use the next odd number - 123457. The highest possible number might be 456789. This is divisible by 3, so try the next one down - 345789. This is another even number, and thus also not prime. Once again, just use the next odd number - 345679. So the range is 123457 to 345679.

Variable n is used to iterate over the legal range. In order to be able to manipulate this integer easily, we need it in string form. It's converted and stored in variable num$.

num$ is passed as parameter to the function IsSorted(), whose job is to determine if the digits in its argument are sorted into ascending order. If TRUE (signified by -1) is returned, num$ is passed to function AllDigitsDifferent(). As the name implies, if all the digits of num$ are different from each other, TRUE is returned.

A TRUE here triggers a summing of the values of all the digits in num$, using function SumStringDigits(). The result is returned not as a string but an integer, and stored in variable digSum.

digSum is passed as parameter to function IsPrime(). If this test is passed, the original number, n, is also passed to IsPrime(). Any value of n which makes it this far and causes a TRUE to be returned must be a valid solution since it is meets all the requirements. Subroutine PrintResult() is called to print the results to the screen.

All functions and subroutines are from my library, and have all been used in former Puzzlets. If you want to know more about how they work, please refer back to the archives, or e-mail me (see footer).

When the program is run, it generates the inset screen. These two are the only solutions.

29 and 31 are both, of course, primes!

Searching ...

Prime: 124679. Sum of Digits: 29
Prime: 234589. Sum of Digits: 31

No more!

Press any key to exit ...