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


Problem DescriptionHow many numbers less than 1,000,000 have digits that sum to 3? Background & TechniquesThis is puzzle #57 from Terry Stickles' excellent book Challenging Math Problems . The puzzle definition includes examples: 1200, 111000, 21, and 300.
Finding the solution seems daunting at first glance, but after studying on it a bit, a few helpful clues come to light:
I came up with three approaches to a solution: Math ApproachMathematically determining of6 zeros and the count without enumerating the individual numbers. If we assume a set of six zeros and answer the question: How many ways can we replace one ("3"), two ("12"or "21") or three ("111") zeroes with the allowable digit sets ("3","12" or "111"). The mathematical formula for choosing R items from N is N!/(NR)! (X! called "X factorial" is shorthand for the prodicut of all numbers from 1 to X). The method for the first two ( one and two digit substitutions) cases may be easier to understand in English.
Generate and Filter ApproachSorry, got carried away with the above description The second approach will be easier to describe and understand, but harder for a human to perform. The program has an option to generate all numbers from 3 through 300,000 and display & count only those whose digits sum to 3. Apply Algorithm ApproachThe final human doable way applies an homemade algorithm to generate solution numbers by starting with "3", "12","21", or "111" and inserting zeros according to a couple of simple rules. Download the program to see the details. Nonprogrammers are welcome to read on, but may want to jump to bottom of this page to download the executable program now. Programmer's Notes:Not much new or exciting here. The Math case just uses a dialog to display an abbreviated version of the description above. The Generate case converts all integers in the range to strings and uses a "Case" statement to sum the digits in the string, breaking the search when the sum exceeds 3. Finally, the Algorithm case uses a "GetNextNumber" recursive function to a single zeros ate each level based on the number in the previous level. Results are kept in a TStringList for each of the 4 group.s Duplicate numbers are generated in some cases which are detected by checking the list. Dups are flagged but kept in case users want to compare their results to the program's. Running/Exploring the Program
Suggestions for Further Explorations

[Feedback] [Newsletters (subscribe/view)] [About me]Copyright © 20002017, Gary Darby All rights reserved. 