[Home] [Puzzles & Projects] [Delphi Techniques] [Math topics] [Library] [Utilities]
|
|
Problem Description
The second in the "T-Shirt" series: Front of T-Shirt: "The smallest 3 digit number equal to the sum of its digits cubed" Back: __ __ __ ? Background & TechniquesA ran across this problem in a paper by Donald Knuth referenced below. As usual, there's more to the problem that meets the eye. For three digit numbers, it's pretty simple to just try numbers from 100 to 999 until we find a number, abc, that satisfies 100a+10b+c = a3+b3+c3. In the more general case, we want to find N digit numbers which are equal to the sum of the Nth powers of their digits. The same "Brute Force" or exhaustive search procedure works pretty well for numbers up to say 8 or so, then run times start getting long. I added a second button to take advantage of the fact that, for any particular N, there are only 10 different values for xn, 0<=x<=9. This "Faster Brute Force" method is about twice as fast as the first. Knuth mentions solutions for n=10,11,12,and maybe 13, too large for brute force, so how did he do it? He makes a reference to "double backtracking" but doesn't explain, and I wasn't successful in tracking any more detail. I did however learn a lot in the course of my search:
I also read or figured out, how to solve for higher orders, although I haven't implemented it yet. The key is recognizing that all permutations of the digits in any number have the same sum of powers. So if we've checked 12345, there's no need to check 54321 or any of the other 719 permutations of those digits. Generating only the subsets will significantly reduce the number of numbers to be checked and is going to be an interesting exercise. The complication is not just generating combinations of n of 10 things, but doing it with replacement. (e.g. 112233 must be checked but 112233 is not a proper subset of the digits 0-9). I know now that these are called multi-sets, subsets of K of N things with replacement. So once I figure out how to generate multi-sets, I think we'll be on the way to generating all solutions up to N=20 or so. Going on up to N=39 would require using the Big Integers unit, but we'll start small. Ref: "Are Toy Problems Useful?" reprinted in "Selected Papers on Computer Science", Donald E. Knuth, Cambridge Press, 1996. Addendum - January 13,2002: T-Shirt2 (XXL) contains to the program with the complete solution that calculates all 88 Armstrong numbers.
Running/Exploring the Program
Suggestions for Further Explorations
|
[Feedback] [Newsletters (subscribe/view)] [About me]Copyright © 2000-2018, Gary Darby All rights reserved. |