PUZZLET 012 - THE SOLUTION
| Here's
a program, written in IBasic, which will solve the Puzzlet. A detailed
description and
explanation follow below it. ' Puzzlet #012 ' A Composite Number is non-Prime, ' such as 1, 4, 6, 8, 9 etc. Add ' all the Composites in ascending ' order to form a Prime Number all ' of whose digits are themselves ' in ascending order. Maximum ' Composite Value: 5,000. ' Example: the Composites up to 8 ' are 1, 4, 6, 8, which sum to 19, ' and 19 is a Prime whose digits ' are in ascending order. ' By Dave Ellis. ' Declarations declare IsPrime(p: int) declare IsUpOrdered(d: int) declare PrintSolution() def n, tot: int ' Screen Setup color 11, 0: cls openconsole print "Searching ... " print "Last Composite Prime" color 14, 0: print ' Initialisations tot = 1 n = 2 ' Main Routine do if IsPrime(n) = 0: 'composite? tot = tot + n: 'totalise if IsPrime(tot): 'is it prime? if IsUpOrdered(tot): 'ordered? PrintSolution(): 'print it endif endif endif n = n + 1: 'get next number until n = 5000 ' Finished color 11, 0 print: print "That's all, folks!" print: print "Press any key ...", do: until inkey$ <> "" closeconsole end ' +++ Functions and Subroutines +++ if p = 2 | p = 3: 'smallest primes flag = -1 else if p % 2 = 0 | p < 2: 'even number or ineligible flag = 0 else root = sqrt(p): 'limit of search i = 3 flag = -1 do: 'commence general divisibility checks if p % i = 0: 'not prime flag = 0 else i = i + 2 endif until flag = 0 | i > root endif endif return flag sub IsUpOrdered(d) ' If the digits of argument d are ' arranged in ascending order returns ' TRUE (-1), else returns FALSE (0). ' Note: this algorithm is around four ' times faster than a string method. def flag, LSD: int flag = -1 do LSD = d % 10: 'store LSD d = d/10: 'chop off LSD 'is new LSD bigger than old LSD? if LSD < d % 10 flag = 0: 'abort - not ordered endif until not flag | d <10 return flag sub PrintSolution() def h$: string h$ = string$(8, "#") print using (h$, n), print using (h$+h$, tot) return |
|
PROGRAM NOTES
Overview and strategy: The code has to find both non-primes (to totalise their values) and primes (to check if the totalised non-prime values are themselves prime). It uses the function IsPrime() for both tasks. It first checks to see if the current number being examined is composite by testing IsPrime() against FALSE (0). If this passes (that is, the number is not prime), it adds the number to the value already totalised in variable tot, the sum of the non-primes so far. IsPrime() is taken from my own library. If you would like to know how it works in detail, just click here now. tot's value is then tested for primality with IsPrime(), this time against TRUE (-1). If this test is passed, a final check is made to see if the individual digits of the value are in ascending order, using function IsUpOrdered(). IsUpOrdered() is taken from my own library. If you would like to know how it works in detail, just click here now. A pass here means a solution has been found, and it's printed to the screen using subroutine PrintSolution(). The program is controlled from the main routine, which we'll look at now in detail. I've numbered the lines to make the explanation which follows easier to understand. Here are the numbered lines. |
| 1 2 3 4 5 6 7 8 9 10 11 |
do if IsPrime(n) = 0: 'composite? tot = tot + n: 'totalise if IsPrime(tot): 'is it prime? if IsUpOrdered(tot): 'ordered? PrintSolution(): 'print it endif endif endif n = n + 1: 'get next number until n = 5000 |
| Let's take a line-by-line look at the code
now, using those line numbers. |
| 1 |
do. Opens the main DO loop. |
| 2 |
days = days + 7.
Increments the day count, which is stored in variable days. Note that this was initialised to value 2, so it will only have values 2, 9, 16 . . . etc. |
| 3 |
if IsPrime(n) = 0. The task of line 3 is to discover if the current value of n is a non-prime. n is passed as parameter to
the function IsPrime(),
which simply returns a -1 (TRUE) or 0 (FALSE). So this line is asking the question "Is the value stored in variable n non-prime?" IsPrime() is taken from my own library. If you would like to know how it works in detail, just click here now. |
| 4 |
tot = tot + n. Line 4 is only executed if line 3 returned FALSE. This is because the code is looking for non-primes at this point. It is effectively saying "Add the value stored in variable n to the value stored in variable tot and write the sum in tot, over-writing what was previously stored there." |
| 5 |
if IsUpOrdered(tot).
Line 5 is only executed if line 4 returned TRUE. This is
because variable tot now holds a new prime to check. tot is passed as parameter to the function IsUpOrdered(), which simply returns a -1 (TRUE) or 0 (FALSE). So this line poses the question "Is the value stored in variable tot comprised of digits which are arranged in ascending order?" IsUpOrdered() is taken from my own library. If you would like to know how it works in detail, just click here now. Note that the combined effect of lines 4 and 5 together is the expression "If tot are is both prime and comprising digits arranged in ascending order, then execute line 6, otherwise skip to line 10." |
| 6 |
PrintSolution(). Lines 6 is only executed if the answer to the qustions in line 4 and 5 both returned TRUE. It
prints out a formatted version of the solution. This is accomplished by calling the subroutine PrintResult(). |
| 7 |
endif. Housekeeping - closes the if-endif clause opened in line 5. |
| 8 |
endif. Housekeeping - closes the if-endif clause opened in line 4. |
| 9 |
endif. Housekeeping - closes the if-endif clause opened in line 2. |
| 10 |
until n = 5000.
End of the main DO loop. At this point, the program has to
make a decision - go around again, or continue with the rest of the
program? It effectively says "Keep on going around the main DO loop until the value stored in variable n is equal to 5000." This is in line with the specification. |
| When
you run the code, it generates the inset results, taken from a
screenshot of my computer running the code. The first few results are trivial, but fall within the Puzzlet's specification. Note that there are very few primes from the large number available that meet the criteria. |
 |