Ray Girvan, in his JSB blog today, considers a mathematical puzzle which, in essence, involves finding a number which is one less than a given multiple of its own digit sum. (I won't be more detailed or specific; see Ray's original post.)
From here on, things get a bit nerdy ... you have been warned!
My "brute force and ignorance" approach to a solution was considerably less elegant that Ray's (which he provides on a link from the main post). Implementing my method, however, did prompt me to think how tasks which would once have been both tedious and Herculean have been rendered trivial by off the peg computing tools.
Making an assumption that the number (n) has no more than 4 digits, and writing it as dcba, the teaser boils down to the following algebraic statement:
1000d + 100c + 10b + a = 17(d+c+b+a) + 1
If the four digit assumption had proven to be false, then extension to five, six, etc, digits would involve adding e, f, and so on to the equation. In the event, that wasn't necessary as the solution turned out to be a three digit one.
Setting up a spreadsheet containing an array of one hundred numbers (initially 0000 to 0099), which would test each of them against the above condition and then move on to the next array, took slightly under a minute. From there to a solution, through two updates of the array, took perhaps two seconds. (The three versions of the array are shown in the image on the left; click it if you want a larger view. The solution, flagged "YES", can be seen at the bottom of the third frame.)
Like Ray, I then wondered whether this was a unique solution. My spreadsheet couldn't answer that question, but it did (in less that a minute) confirm that there is no other two, three or four digit alternative.
As I say, this is (to put it kindly) not a very cerebral approach ... but it is quick. Writing this description has taken me much longer than the entire design, implementation and use cycle for what was a one time throwaway tool.
Of course, every extra digit would increase the time by an order of magnitude ... but then, I was using visual inspection of the array (watching for the word "YES" to occur on screen). At five digits or more, it would have been worth investing a few minutes in automating that aspect. In fact, having written that, I have just tried a copy, paste and filter approach which took me to the limit of five digits (even without automation) in less time than the original four digit check.
It's very easy to take things for granted and forget how far we've come in a short while. Trying this trick in the days before spreadsheets, even using a calculator, would have taken about twenty to reach the solution (being prepared to go on for over an hour if the solution had been close to a thousand); testing to 9999 would have taken roughly two standard working days. Go to my teens, when calculators hadn't happened yet, and you can multiply those times by a factor of four or five.
1 comment:
Some years back I used to do the mathematical puzzles in PC World, and they were often amenable to programming. With a ZX81, you had to be make maximum use of pre-analysis to reduce the search space. In this case, as I said in my own analysis, you only need to look at numbers of the form 17k + 1, and that thins it out a bit.
Post a Comment