T-Shirt #2 XXL

[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.

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:  __ __ __ ?

 

This is the XXL version (as in extra, extra large) of the previously posted T-Shirts #2 problem.

Background & Techniques

This page is an extension of the discussion started in the page describing the initial version of the T-Shirts2 problem to generate numbers with this characteristic , called Armstrong numbers or Pluperfect Digital invariants (PPDIs).   I suggest that you visit the T-Shirts #2 page first. 

The XXL refers to complexity rather than code size.  I've added the multiset search technique proposed  previously.   In addition, the program now uses the Big Integers unit in an optimized search for Armstrong numbers larger than 19 digits long.  

I have found out that , in base 10,  there are 88 of these Armstrong numbers.  In fact here's a link to a site that that lists them.  

There are two new buttons on the form; a "Multisets" button that generates and tests all subsets of length N from the digits 0 through 9 with duplication allowed.   And a "Big Numbers" button that implements an large integer version of the multiset search technique.

I believe, although I haven't really confirmed that the number of such multisets of length N is given by the number of combinations of N+9 things taken N at a time.     Recall that the number of combinations of N things take R at a time, denoted C(N,R),  is N!/(R!*(N-R)!),  or in our case C(N+9,N)= (N+9)!/(N!*9!).  This matches my empirical results for the first few numbers, so I suspect that it's  true.    

The Multiset button procedure operates on 64 bit integers and therefore can only find numbers through 19 or 20 digits (I've limited it to 19 digits, just to be safe).    As a refresher,  the sum of the powers of the digits of a number is independent of the order.  So if we generate the multisets of size N, calculate the sum of powers and check to see if the digits in the sum are a 1-to-1 match with the digits  summed,  we have a faster way to detect Armstrong numbers.  

The "Big Numbers" button started out as a copy of the above procedure, but using the Big Integers unit  previously introduced.   Because calculations using big integers are about 10 times slower than Int64 calculations, I added some additional optimizations.   

bulletWe don't really need an array of digits in the multiset, just the counts of digits.  so I rewrote the  GetNextMultiset procedure to return just an array of counts.  
bulletWe can stop accumulating a sum when the length of the sum exceeds N digits.  By generating the multisets in decreasing order of the digits selected, this will occur sooner.     
bulletSince we are now generating the multisets in decreasing order, we are done checking whenever a complete sum is is less than N digits in length.
bulletI initialize a two dimensional array (pwrs) with the sums to be added for each possible multiple of each digit.  For example, if we're checking the 10 digit number, 2,555,525,525,  we need to find the value of 210+510+510+...+2 to check if it equals 2,555,525,525.  The quick way is to  add pwrs[5,7], 7*510, and pwrs[2,3], 3* 210  to get the sum  that we need.  

I just added  a fifth button to generate all 88 numbers but haven't run it to completion yet.  

Addendum January 15, 2001 :  Program just completed, it took 36 hours on my 800mmhz Celeron!  Now I know I'm going to have to improve on that time.   Here's a page with my program's output  listing all 88 base-10 PPDIs.

Addendum April 13, 2005:  The UBigIntsV2 containing the TInteger big integer class  has  moved  the DFF Library.  If you want to recompile the program you will nee a one time download of  the DFF Library source.

Running/Exploring the Program 

bulletBrowse source extract  
bulletDownload source  (Requires DFF Library Source DFFLibV02 or later)
bulletDownload DFF Library Source (DFFLibV15 )
bulletDownload  executable

Suggestions for Further Explorations

Are further optimizations possible?   I guess so.
The Big Integer unit has not been optimized for speed.  This problem may provide the excuse to do it.

Originally posted January 13, 2002

Modified: February 18, 2016

 

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