home *** CD-ROM | disk | FTP | other *** search
/ DP Tool Club 15 / CD_ASCQ_15_070894.iso / vrac / tpchal_1.zip / ANALYSIS.TXT next >
Text File  |  1994-06-09  |  9KB  |  226 lines
  1. ------------------------------------------------------------------------------
  2. Date:   Sun May 22 1994  14:36:16
  3. From:   Andrew Key
  4. To:     All
  5. Subj:   A simple programming challenge
  6. Attr:
  7. international C echo
  8. -------------------------------
  9. You can take advantage of a few divisibility rules when coding for an
  10. efficient solution, or when solving with pen and paper.
  11.  
  12. Divisible by 2: ones digit will be even.
  13. Divisible by 3: sum of digits will also be divisible by 3.
  14. Divisible by 4: last two digits (ie. ones and tens digits) will by div. by 4.
  15. Divisible by 5: ones digit will be a zero or a five.
  16. Divisible by 6: ones digit will be even, and sum of digits will be div. by 3.
  17. Divisible by 8: last three digits will be div. by 8.
  18. Divisible by 9: sum of digits will also be divisible by 9.
  19.  
  20. Additionally, since zero may not be used, the 5th digit must be a five.
  21. And using 1 through 9, each once, guarantees that any number we select
  22. will be divisible by nine.  So once we have eight digits that meet the
  23. criteria, just add the digit not used to complete the ninth digit.
  24. Another thing to note is that none of the odd-numbered digits may
  25. contain 2, 4, 6, or 8; all four possible even numbers will be used in
  26. the even-numbered digits.
  27.  
  28. We'll start with the first three digits, remembering that digit two must
  29. be even and non-zero, and that none of the digits can repeat.  Also, since
  30. the fifth digit must be five, we can eliminate any that contain it.
  31. The possibilities are:
  32.  
  33. 123  129  147  183  189  321  327  369  381  387  723  729  741  783
  34. 789  921  927  963  981  987
  35.  
  36. So, immediately, we've narrowed down our search to 20 initial branches
  37. that the number could take.  Now we start looking for possiblities for
  38. the fourth and fifth digit.  We need only test the last two digits for
  39. of a four digit number, and then add our five as a fifth digit to the
  40. ones that pass - of course striking out any zeros, repeats.  This gives
  41. us:
  42.  
  43. 12965  14725  14765  18325  18365  18925  18965  32165  32765  36925
  44. 38125  38165  38725  38765  72365  72965  74125  74165  78325  78365
  45. 78925  78965  92165  92765  96325  98125  98165  98725  98765
  46.  
  47. This gives us a total of 29 5-digit numbers that meet all criteria so
  48. far.  Now, to test for the sixth digit, we look for even numbers, and the
  49. resulting number must be divisible by three.  Since the first three digits
  50. have already been determind to be divisible by three, we need only test the
  51. last two.  And since the 2nd and 4th digits are even, and the 6th digit must
  52. be also, there are only two possibilities to test per number.  This gives
  53. us:
  54.  
  55. 147258  183654  189654  321654  327654  369258  381654  387654  723654
  56. 729654  741258  783654  789654  921654  927654  963258  981654  987654
  57.  
  58. At this point, 3 of 4 possible even numbers have been used in each
  59. number and 3 of 5 odd numbers possible have been selected.  So we know
  60. that our possible answers will take this form(x represents unknown):
  61.  
  62. 147258x6x  183654x2x  189654x2x  321654x8x  327654x8x  369258x4x
  63. 381654x2x  387654x2x  723654x8x  729654x8x  741258x6x  783654x2x
  64. 789654x2x  921654x8x  927654x8x  963258x4x  981654x2x  987654x2x
  65.  
  66. At this point, substitute in our remaining odd numbers for digit 7 and
  67. test digits 6-8 for divisibility by 8(We'll check for divisibility by
  68. 7 next).  And if a number passes the div. by 8, we'll go ahead and put
  69. the remaining number in the 9th position.  We are left with:
  70.  
  71. 147258963  183654729  189654327  189654723  381654729  741258963
  72. 789654321  981654327  981654723  987654321
  73.  
  74. Now we check the remaining numbers for divisibility by seven.  We saved
  75. this test for last, as there are no shorter tests that we can apply than
  76. to actually divide the whole number by 7.  The only number whose first
  77. seven digits are evenly divisible by 7 is:
  78.  
  79. 318654729
  80.  
  81. Of course, it's a simple matter to write code to take advantage of the
  82. divisibility rules.  Following along these lines, you should be able to
  83. code a pretty *fast* algorithm.
  84.  
  85.                                            -AK
  86.  
  87.  
  88.  
  89. ------------------------------------------------------------------------------
  90. Date:   Sat May 21 1994  00:12:04
  91. From:   Auke Reitsma
  92. To:     Jeff Dunlop
  93. Subj:   A simple programming cha
  94. Attr:
  95. international C echo
  96. -------------------------------
  97. My 'program' -- heavily optimized ;-) -- is:
  98.  
  99. #include <stdio.h>
  100.  
  101. main( void )
  102. {
  103.     puts( "The answer is: 381,654,729\n" );
  104. }
  105.  
  106. Actually found this 'manually' within an hour. Method:
  107.  
  108. Consider ABCDEFGHI to represent the nine digit number, and each
  109. letter an unique digit.
  110.  
  111. 1  As AB must be divisible by 2, B must be even. And similar for D,
  112.    F, and H. Therefore A, C, E, G and I must be odd.
  113.  
  114. 2  As ABCDE must be divisible by five, it IS five.
  115.  
  116. 3  ABC must be divisible by three. Therefore (A+B+C) mod 3 == 0.
  117.    ABCDEF must be divisible by six. So also by three.
  118.    So (A+B+C+D+E+F) mod 3 == 0. Therefore (D+E+F) mod 3 == 0.
  119.    Similarly: (G+H+I) mod 3 == 0.
  120.  
  121. 4  As E = 5, the only valid pairs of digits for D and F are
  122.    4 and 6 or 2 and 8.
  123.    C is odd, so D cannot be 4 or 8 as ABCD must be divisible
  124.    by 4. So D=6 and F=4 or D=2 and F=8. In each case B and H are
  125.    the remaining even digits.
  126.  
  127. 5  ABCDEFGH must be divisible by eight. Therefore FGH must be
  128.    divisible by eight. F is even and G is odd, so H cannot be 4
  129.    or 8 (G4 / 2 = X7, G8 / 2 = X9). At this point the only
  130.    possible values are A4C258G6I and A8C654G2I.
  131.    After trying G = 1, 3, 7 or 9 and checking FGH/8:
  132.    A4C25816I, A4C25896I, A8C65432I and A8C65472I.
  133.  
  134. 6  And after (respectively) trying I = the remaining digits:
  135.    (with G+H+I mod3 == 0)(see 3):
  136.    A4C258963, A8C654321, A8C654327, A8C654723 and A8C654729.
  137.  
  138. 7  Filling in all remaining possible values for A and C:
  139.    147258963, 789654321, 189654327, 189654723, 183654729,
  140.    741258963, 987654321, 981654327, 981654723 and 381654729.
  141.  
  142. 8  Now check each of these numbers for divisibility by 7 of the
  143.    number consisting of the first seven digits.
  144.    Only 381654729 satisfies this test and therefore is the
  145.    ONLY solution.
  146.  
  147. Note that division by nine is always possible!
  148.  
  149. Greetings from Delft, The Netherlands,
  150. Auke Reitsma.
  151.  
  152.  
  153.  
  154. ------------------------------------------------------------------------------
  155. Date:   Mon May 23 1994  15:19:48
  156. Date:   Mon May 23 1994  15:19:48
  157. From:   Stephen Lindholm
  158. To:     Rhys Wong
  159. Subj:   A SIMPLE PROGRAMMING CHAL
  160. Attr:
  161. international C echo
  162. -------------------------------
  163. Whoa! This is probably the longest paper you'll see from me in this echo that
  164. doesn't have any code in it. :)
  165.  
  166.  RW> Solving the problem is not so challenging, but writing a program to solve
  167.  RW> the problem IS !
  168.  
  169. You can either have it plug through all of the combos or optimize it as much as
  170. possible. It would take about thrice as long to do the latter. If I had access
  171. to a computer (well, a real computer, I was in typing class which is in the
  172. Apple 2 lab... :) while during it, I would only have used it to check
  173. divisibility by 7.
  174.  
  175.  RW> I don't understand why the odds have 4 possibilities or evens have only
  176.  RW> 2 possibilities.  You said there was only one possilibity for the 7-th
  177.  
  178. 123456789
  179. ---------
  180.     5
  181.  
  182. That leaves 8 possibilities. Since there are 4 even and 4 odd, and divisible by
  183. even always end in even, that means that all evens go to the evens and all odds
  184. to the odds.
  185.  
  186. 123456789
  187. ---------
  188. 121252121
  189. 3434 4343
  190. 7676 6767
  191. 9898 8989
  192.  
  193. Since that means that the evens have an odd for the tens digit and all numbers
  194. divisible by 4 with an odd tens are either 2 or 6 in the ones, leaving 4 and 8
  195. for 2 and 6.
  196.  
  197. 123456789
  198. ---------
  199. 141254121
  200. 3836 8363
  201. 7 7   7 7
  202. 9 9   9 9
  203.  
  204. From this, I computed the number of possible solutions. I cannot remember what
  205. I computed, but because the third digit only allows certain combos to pass, the
  206. number of combinations after the third are far less than 32, as you might
  207. believe. You have two possibilities for the next three digits. One with 2 in
  208. the 4 and one with a 6. The 5 is a given. The 6 is a given, as there aren't two
  209. different numbers with the same modulus as 3 had.
  210.  
  211.  SL> the digits required.
  212.  
  213.  RW> 2 possibilities.  You said there was only one possilibity for the 7-th
  214.  RW> digit (?), but that's not true.  It may be xxxxxx2xx or xxxxxx9xx.   How
  215.  
  216. All of the evens are reserved for the evens. That means that 7 is a given. 8
  217. can be figured out easily (7 and 8 are where most of the possibilities dropped
  218. out, beyond the 12 that didn't live beyond 3), and 9 is extraneous, because all
  219. 9! of the possibilities are divisible by 9.
  220.  
  221. I hope this answers your question, because the proof paper in question is
  222. turning to compost at the Cedar Rapids Municipal Mt. Trashmore and I had to
  223. make this up as I go, and I can't list my work, at least not without the
  224. duldrums of making it up all over again. :)
  225. ------------------------------------------------------------------------------
  226.