T-Shirt #2

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. 

     

We receive a few cents from each purchase.  Thanks

 


Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Mensa Daily Puzzlers

For over 15 years Mensa Page-A-Day calendars have provided several puzzles a year for my programming pleasure.  Coding "solvers" is most fun, but many programs also allow user solving, convenient for "fill in the blanks" type.  Below are Amazon  links to the two most recent years.

Mensa 365 Puzzlers  Calendar 2017

Mensa 365 Puzzlers Calendar 2018

(Hint: If you can wait, current year calendars are usually on sale in January.)

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

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 & Techniques

A 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:

bulletThe solutions are a form of narcissistic numbers, numbers that "love themselves" in the sense that they can be written as expressions using only their own digits.
bulletMore specifically they are called PluPefect Digital Invariants (PPDIs) or Armstrong numbers.
bulletThere are either 79 or 88 of them, I've seen both counts, the largest contains 39 digits.
bulletHere's  a link to Harvey Heinz's  excellent page with more info (look for the PPDI section).

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 

bulletBrowse source extract 
bulletDownload source 
bulletDownload  executable

Suggestions for Further Explorations

bulletSolve for larger values of N, as described above.

 

Originally posted: December 11. 2001 Modified: July 29, 2017

 

 

  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2017, Gary Darby    All rights reserved.