| ' Puzzlet #096 ' 404 x 58 = 23432. 927 x 68 = 63036. In ' each case, the product of a 2-digit and ' a 3-digit integer is a 5-digit "wave" ' number. This is an integer whose digits ' rise (or fall) in an arithmetic progression ' from the beginning to the middle and ' then fall (or rise) in exactly the reverse ' manner to the end. ' Find all possible 5-digit wave numbers ' which are the products of a 2-digit and ' a 3-digit integer. ' By Dave Ellis. declare IsPalStr(p$: string) declare Sequenced(s$: string, f: int) declare PrintResult() def interval, it2, it3, prod: int ' Interval is the difference between ' successive digits in the wave number. ' it2 holds the 2-digit integer ' it3 holds the 3-digit integer ' prod holds it2*it3 openconsole print "Searching ...": print interval = -4 do it3 = 100 do it2 = 10 do prod = it2*it3 if prod > 9999 if prod < 100000 prod$ = ltrim$(str$(prod)) if IsPalStr(prod$) if Sequenced(prod$, interval) PrintResult() endif endif endif endif it2 = it2 + 1 until (prod > 99999) | (it2 > 99) it3 = it3 + 1 until it3 > 999 interval = interval + 1 if interval = 0 interval = interval + 1 endif until interval > 4 print: print "No more!" print: print "Press a key ... ", do: until inkey$ <> "" closeconsole end sub IsPalStr(p$) ' if p$ is a palindrome, returns 1, ' otherwise returns 0 def flag, i, j, L: int def q$, r$: string L = len(p$) j = int(L/2) i = 1 flag = 1 do q$ = mid$(p$, i, 1) r$ = mid$(p$, L + 1 - i, 1) if q$ <> r$ flag = 0 endif i = i + 1 until flag = 0 | i > j return flag sub Sequenced(s$, f) ' if s$ is a wave number with interval ' f between its characters, returns -1, ' otherwise returns 0 def flag, i, L: int def str1$, str2$: string L = len(s$)/2 i = 1 flag = -1 do str1$ = mid$(s$, i, 1) str2$ = mid$(s$, i + 1, 1) if val(str2$) - val(str1$) <> f flag = 0 endif i = i + 1 until (flag = 0) | i > 2 return flag sub PrintResult ' pretty printer print it2, "x ", it3, print "= ", prod return |
| PROGRAM NOTES To help explain how the above code works, I've assigned line numbers to the part that does all the work, as shown below. |
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
|
interval = -4 do it3 = 100 do it2 = 10 do prod = it2*it3 if prod > 9999 if prod < 100000 prod$ = ltrim$(str$(prod)) if IsPalStr(prod$) if Sequenced(prod$, interval) PrintResult() endif endif endif endif it2 = it2 + 1 until (prod > 99999) | (it2 > 99) it3 = it3 + 1 until it3 > 999 interval = interval + 1 if interval = 0 interval = interval + 1 endif until interval > 4 |
| Now for an exegesis, based on the above line numbers: |
| 1 |
interval = -4. Variable interval, which controls the numerical interval between successive digits, is initialised to -4. This is the minimum possible, as in 95159. |
| 2 |
do. Opens the main DO loop. |
| 3 |
it3 = 100. Variable it3, which holds the 3-digit integer used in the product, is initialised to its lowest value, 100. |
| 4 |
do. Opens
the first nested DO loop. |
| 5 |
it2 = 10. Variable it2, which holds the 2-digit integer used in the product, is initialised to its lowest value, 10. |
| 6 |
do. Opens
the second (innermost) nested DO loop. |
| 7 |
prod = it2*it3. Variables it2 and it3 are multiplied together and the result stored in prod. This is the process described as multiplying a 2-digit and a 3-digit integer together. |
| 8 |
if prod > 9999. Ensures the value in prod isn't less than 5 digits in length. |
| 9 |
if prod < 100000. Ensures the value in prod isn't greater than 5 digits in length. |
| 10 |
prod$ = ltrim$(str$(prod)). Converts prod to string form to facilitate further processing, storing the result in prod$. |
| 11 |
if IsPalStr(prod$). prod$ is passed as parameter to function IsPalStr() to ensure it's really a palindrome. The function returns -1 (TRUE) if so, otherwise 0 (FALSE). |
| 12 |
if Sequenced(prod$, interval). If prod$ turns out to be a palindrome, we have only to check that if follows the "wave" pattern to see if this is a valid solution. prod$ and the current value of interval are passed as parameters to function Sequenced() to carry out this check, which returns the same flags as described in Line 11. |
| 13 |
PrintResult(). If Sequenced() returned TRUE, the current values being tested form a solution, and subroutine PrintResult() is invoked to print them to the screen. |
| 14/17 |
endif. Housekeeping - closes the IF-ENDIF clauses. |
| 18 |
it2 = it2 + 1. Increments the 2-digit integer, it2,
ready for the next product test. |
| 19 |
until (prod > 99999) | (it2 > 99). Tests to see if prod is greater than 5 digits in length, or it2 is greater than 2 digits in length. If neither, then the inner DO loop is executed again, otherwise it quits. |
| 20 |
it3 = it3 + 1. Increments the 3-digit integer, it3, ready for the next group of product tests. |
| 21 |
until it3 > 999. Tests to see if prod is it3 is greater than 3 digits in length. If it's not, the inner DO loop is executed again, otherwise it quits. Notice that there's no need to check that it3's new value doesn't cause prod to be greater than 5 digits, since the inner DO loop takes care of that at every iteration. |
| 22 |
interval = interval + 1. Incremements interval ready for the next batch of tests with the new value. |
| 23 |
if interval = 0. Checks the value stored in variable interval. It's effectively asking the question "Is the value stored in variable interval equal to zero?" If it equals zero, it will permit solutions such as 33333 or 77777, which aren't waves. |
| 24 |
interval = interval + 1. If the answer to the question posed in line 23 is "yes," the value stored in variable interval is incremented by one (so it becomes 1 anyway), so that the search recommences with value 1. |
| 25 |
endif. Housekeeping - closes the IF-ENDIF clause opened in line 23. |
| 26 |
until interval > 4. The maximum possible value for interval is 4, leading to 15951. If interval doesn't exceed this value, the main DO loop is executed again, otherwise it quits and the program ends. |
| When
you run the program, you'll see the inset results printed out onto your
computer's screen. This is the complete list. You'll notice that many of the products are duplicated, but always using different pairs of multiplicants. If the "wave" interval is set to zero, the following extra results are obtained: 41
x 271 = 11111
82 x 271 = 22222 41 x 542 = 22222 82 x 542 = 44444 41 x 813 = 33333 82 x 813 = 66666 |
|
Searching
... 94 x 907 = 85258 68 x 927 = 63036 68 x 618 = 42024 91 x 706 = 64246 51 x 824 = 42024 68 x 309 = 21012 91 x 353 = 32123 51 x 412 = 21012 34 x 618 = 21012 37 x 333 = 12321 58 x 404 = 23432 29 x 808 = 23432 71 x 956 = 67876 74 x 333 = 24642 37 x 666 = 24642 75 x 773 = 57975 58 x 808 = 46864 92 x 281 = 25852 46 x 562 = 25852 37 x 999 = 36963 39 x 409 = 15951 No more! Press a key ... |