PUZZLET 020 - THE SOLUTION
| Here's
a program, written in IBasic, which will solve the Puzzlet. A detailed
description and
explanation follow below it. ' Puzzlet #020 ' The number of letters in "Monday" ' is 6; for the other days it's ' 7, 9, 8, 6, 8, 6. If these are ' added together daily, the total ' on day 44 is 313, a palindromic ' prime. Find at least four other ' palindromic primes that occur as ' the days pass and are totalised. ' By Dave Ellis. ' Declarations. declare IsPrime(p: int) declare IsPalindrome(p: int) declare PrintSolution() def count, days, tot: int ' Screen Setup color 11, 0: cls openconsole print "Searching ... " print "Nr of Days Total Letters" color 14, 0 ' Initialisations days = 2 tot = 13 count = 0 ' Main Routine do days = days + 7: 'increment days tot = tot + 50: 'get new total if IsPrime(tot): 'is it prime? if IsPalindrome(tot): 'palindrome? PrintSolution(): ' print it count = count + 1: ' incr count endif endif until count > 4 ' Finished color 11, 0 print: print "That's all, folks!" print: print "Press any key ...", do: until inkey$ <> "" closeconsole end ' +++ Functions and Subroutines +++ sub IsPrime(p) ' if argument p is prime returns ' TRUE (-1), otherwise returns FALSE (0) def flag, i, root: int 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 if p % i = 0: 'not prime flag = 0 else i = i + 2 endif until flag = 0 | i > root endif endif return flag sub IsPalindrome(p) ' if p is palindromic returns TRUE (-1), ' otherwise returns FALSE (0) def flag, i, j, L: int def p$, q$, r$: string p$ = ltrim$(str$(p)) L = len(p$) j = L/2 i = 1 flag = -1 do ' get symmetrically opposite pairs q$ = mid$(p$, i, 1) r$ = mid$(p$, L + 1 - i, 1) if q$ <> r$: 'not a palindrome flag = 0 endif i = i + 1 until flag = 0 | i > j: 'either failed or finished return flag sub PrintSolution() def d$, t$: string d$ = string$(7, "#") t$ = string$(15, "#") print using (d$, days), print using (t$, tot) return |
|
PROGRAM NOTES
Overview and strategy: A little analysis makes the problem, and thus the code, simpler. On day 1, the total is 6, an even number, and is not therefore prime. On day 2, 1t's 13, an odd number (which happens to be prime but not palindromic). On days 3, 4, 5, 6 and 7 the total will always be an even number, which cannot be prime. The total number of letters per week is 50. The next time the total is odd is a week later on day 9. So that's the next time it could be a prime number. It will in fact be 13 + 50, which is the total on day 2 plus a week's total of 50. This makes 63, which is an odd number (but not, in this case, prime). So all the code needs to do is to look at day 2, then day 9, day 16, etc, adding 50 each time. And checking the weekly total for primality. If it's prime, check for palindromicity. If it passes both tests, it's a solution. 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 |
do days = days + 7: 'increment days tot = tot + 50: 'get new total if IsPrime(tot): 'is it prime? if IsPalindrome(tot): 'palindrome? PrintSolution(): ' print it count = count + 1: ' incr count endif endif until count > 4 |
|
| 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 |
tot = tot + 50. The letter count is stored in variable tot. There total count for a week is 50, and, since the day count was incremented in the previous line by 7, the letter count must be incremented by 50. So line 3 says "Add 50 to the value stored in variable tot and save the new value in tot, over-writing what was already stored in there." |
| 4 |
if IsPrime(tot).
The task of line 4 is to discover if the latest letter count,
stored in variable tot, is a prime. tot 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 tot prime?" IsPrime() is taken from my own library. If you would like to know how it works in detail, just click here now. |
| 5 |
if
IsPalindrome(tot).
Line 5 is only executed if line 4 returned TRUE. This is
because there's no point in checking tot's
palindromicity is it
isn't also a prime. tot is passed as parameter to the function IsPalindrome(), which simply returns a -1 (TRUE) or 0 (FALSE). So this line poses the question "Is the value stored in variable tot palindromic?" IsPalindrome() 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 palindromic, then execute line 6, otherwise skip to line 10." |
| 6 |
PrintSolution(). Lines 6 and 7 are 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 |
count = count + 1. Now that a solution has been found and printed out, a record of the number of solutions must be incremented. This record is stored in variable count, which was initialised to zero. This is a very important action, as the program will continue to run forever unless it's informed when an appropriate number of solutions have been found. |
| 8 |
endif. Housekeeping - closes the if-endif clause opened in line 5. |
| 9 |
endif. Housekeeping - closes the if-endif clause opened in line 4. |
| 10 |
until count > 4.
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 count is greater than 4." This is in line with the specified number of solutions. |
| When
you run the code, it generates the inset results, taken from a
screenshot of my computer running the code. These are the required 5 solutions. If you keep going long enough, the next one is 3103013, taking a massive 434,422 days to generate! |
 |