------------------------------------------------------------------------------ Date: Sun May 22 1994 14:36:16 From: Andrew Key To: All Subj: A simple programming challenge Attr: international C echo ------------------------------- You can take advantage of a few divisibility rules when coding for an efficient solution, or when solving with pen and paper. Divisible by 2: ones digit will be even. Divisible by 3: sum of digits will also be divisible by 3. Divisible by 4: last two digits (ie. ones and tens digits) will by div. by 4. Divisible by 5: ones digit will be a zero or a five. Divisible by 6: ones digit will be even, and sum of digits will be div. by 3. Divisible by 8: last three digits will be div. by 8. Divisible by 9: sum of digits will also be divisible by 9. Additionally, since zero may not be used, the 5th digit must be a five. And using 1 through 9, each once, guarantees that any number we select will be divisible by nine. So once we have eight digits that meet the criteria, just add the digit not used to complete the ninth digit. Another thing to note is that none of the odd-numbered digits may contain 2, 4, 6, or 8; all four possible even numbers will be used in the even-numbered digits. We'll start with the first three digits, remembering that digit two must be even and non-zero, and that none of the digits can repeat. Also, since the fifth digit must be five, we can eliminate any that contain it. The possibilities are: 123 129 147 183 189 321 327 369 381 387 723 729 741 783 789 921 927 963 981 987 So, immediately, we've narrowed down our search to 20 initial branches that the number could take. Now we start looking for possiblities for the fourth and fifth digit. We need only test the last two digits for of a four digit number, and then add our five as a fifth digit to the ones that pass - of course striking out any zeros, repeats. This gives us: 12965 14725 14765 18325 18365 18925 18965 32165 32765 36925 38125 38165 38725 38765 72365 72965 74125 74165 78325 78365 78925 78965 92165 92765 96325 98125 98165 98725 98765 This gives us a total of 29 5-digit numbers that meet all criteria so far. Now, to test for the sixth digit, we look for even numbers, and the resulting number must be divisible by three. Since the first three digits have already been determind to be divisible by three, we need only test the last two. And since the 2nd and 4th digits are even, and the 6th digit must be also, there are only two possibilities to test per number. This gives us: 147258 183654 189654 321654 327654 369258 381654 387654 723654 729654 741258 783654 789654 921654 927654 963258 981654 987654 At this point, 3 of 4 possible even numbers have been used in each number and 3 of 5 odd numbers possible have been selected. So we know that our possible answers will take this form(x represents unknown): 147258x6x 183654x2x 189654x2x 321654x8x 327654x8x 369258x4x 381654x2x 387654x2x 723654x8x 729654x8x 741258x6x 783654x2x 789654x2x 921654x8x 927654x8x 963258x4x 981654x2x 987654x2x At this point, substitute in our remaining odd numbers for digit 7 and test digits 6-8 for divisibility by 8(We'll check for divisibility by 7 next). And if a number passes the div. by 8, we'll go ahead and put the remaining number in the 9th position. We are left with: 147258963 183654729 189654327 189654723 381654729 741258963 789654321 981654327 981654723 987654321 Now we check the remaining numbers for divisibility by seven. We saved this test for last, as there are no shorter tests that we can apply than to actually divide the whole number by 7. The only number whose first seven digits are evenly divisible by 7 is: 318654729 Of course, it's a simple matter to write code to take advantage of the divisibility rules. Following along these lines, you should be able to code a pretty *fast* algorithm. -AK ------------------------------------------------------------------------------ Date: Sat May 21 1994 00:12:04 From: Auke Reitsma To: Jeff Dunlop Subj: A simple programming cha Attr: international C echo ------------------------------- My 'program' -- heavily optimized ;-) -- is: #include main( void ) { puts( "The answer is: 381,654,729\n" ); } Actually found this 'manually' within an hour. Method: Consider ABCDEFGHI to represent the nine digit number, and each letter an unique digit. 1 As AB must be divisible by 2, B must be even. And similar for D, F, and H. Therefore A, C, E, G and I must be odd. 2 As ABCDE must be divisible by five, it IS five. 3 ABC must be divisible by three. Therefore (A+B+C) mod 3 == 0. ABCDEF must be divisible by six. So also by three. So (A+B+C+D+E+F) mod 3 == 0. Therefore (D+E+F) mod 3 == 0. Similarly: (G+H+I) mod 3 == 0. 4 As E = 5, the only valid pairs of digits for D and F are 4 and 6 or 2 and 8. C is odd, so D cannot be 4 or 8 as ABCD must be divisible by 4. So D=6 and F=4 or D=2 and F=8. In each case B and H are the remaining even digits. 5 ABCDEFGH must be divisible by eight. Therefore FGH must be divisible by eight. F is even and G is odd, so H cannot be 4 or 8 (G4 / 2 = X7, G8 / 2 = X9). At this point the only possible values are A4C258G6I and A8C654G2I. After trying G = 1, 3, 7 or 9 and checking FGH/8: A4C25816I, A4C25896I, A8C65432I and A8C65472I. 6 And after (respectively) trying I = the remaining digits: (with G+H+I mod3 == 0)(see 3): A4C258963, A8C654321, A8C654327, A8C654723 and A8C654729. 7 Filling in all remaining possible values for A and C: 147258963, 789654321, 189654327, 189654723, 183654729, 741258963, 987654321, 981654327, 981654723 and 381654729. 8 Now check each of these numbers for divisibility by 7 of the number consisting of the first seven digits. Only 381654729 satisfies this test and therefore is the ONLY solution. Note that division by nine is always possible! Greetings from Delft, The Netherlands, Auke Reitsma. ------------------------------------------------------------------------------ Date: Mon May 23 1994 15:19:48 Date: Mon May 23 1994 15:19:48 From: Stephen Lindholm To: Rhys Wong Subj: A SIMPLE PROGRAMMING CHAL Attr: international C echo ------------------------------- Whoa! This is probably the longest paper you'll see from me in this echo that doesn't have any code in it. :) RW> Solving the problem is not so challenging, but writing a program to solve RW> the problem IS ! You can either have it plug through all of the combos or optimize it as much as possible. It would take about thrice as long to do the latter. If I had access to a computer (well, a real computer, I was in typing class which is in the Apple 2 lab... :) while during it, I would only have used it to check divisibility by 7. RW> I don't understand why the odds have 4 possibilities or evens have only RW> 2 possibilities. You said there was only one possilibity for the 7-th 123456789 --------- 5 That leaves 8 possibilities. Since there are 4 even and 4 odd, and divisible by even always end in even, that means that all evens go to the evens and all odds to the odds. 123456789 --------- 121252121 3434 4343 7676 6767 9898 8989 Since that means that the evens have an odd for the tens digit and all numbers divisible by 4 with an odd tens are either 2 or 6 in the ones, leaving 4 and 8 for 2 and 6. 123456789 --------- 141254121 3836 8363 7 7 7 7 9 9 9 9 From this, I computed the number of possible solutions. I cannot remember what I computed, but because the third digit only allows certain combos to pass, the number of combinations after the third are far less than 32, as you might believe. You have two possibilities for the next three digits. One with 2 in the 4 and one with a 6. The 5 is a given. The 6 is a given, as there aren't two different numbers with the same modulus as 3 had. SL> the digits required. RW> 2 possibilities. You said there was only one possilibity for the 7-th RW> digit (?), but that's not true. It may be xxxxxx2xx or xxxxxx9xx. How All of the evens are reserved for the evens. That means that 7 is a given. 8 can be figured out easily (7 and 8 are where most of the possibilities dropped out, beyond the 12 that didn't live beyond 3), and 9 is extraneous, because all 9! of the possibilities are divisible by 9. I hope this answers your question, because the proof paper in question is turning to compost at the Cedar Rapids Municipal Mt. Trashmore and I had to make this up as I go, and I can't list my work, at least not without the duldrums of making it up all over again. :) ------------------------------------------------------------------------------