Digits Sum To 3

[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

How many numbers less than 1,000,000 have digits that sum to 3? 

Background & Techniques

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

  1. The smallest solution number is 3 and the largest is 300,000.
  2. There are only three sets of nonzero digits that can meet the given "sum to 3" condition: 3, 12, and 111 (our four sets if  it's convenient to treat the 21 permutation as separate from 12).  

I came up with three approaches to a solution:

Math Approach

Mathematically 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!/(N-R)!  (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. 

bulletThe "3" case: How many ways can I replace one of the siz zeros with a "3"?  Clearly there are six ways. If we drop the leading zeros and sort the numbers, the  results are [3,30,300,3000,30000,and 300000]. And note that 6!/(6-1)!  = 6!/5! = 6.
bulletThe "12" case shows us the effect of permuting (rearranging) when we have multiple zeros to replace.  The first digit, whether it is the "1" of the "2", replaces one of the six zeros and the other digit replaces one of the other five zeros so the total number of arrangements 6*5 = 30.  And, notice the 6!/(6-2)! = 6!/4! = 6*5 = 30. 
bulletThe "111" case throws another wrinkle at us.  The 30 results from the previous case are distinguishable because a "2" looks different than a "1".  If we had had "11" to insert, half of the cases would be duplicates of the other half.  In the "111" case, the formula would return 6!/(6-3)!= 6!/3! = 6*5*4=120, but in fact only 1/6 of the results would be unique because the 3 ones could rearrange   themselves  in 3!(=6) ways to produce identical numbers. So, we need to divide the 120 by 6 giving us 20 unique results for this case.

Generate and Filter Approach

Sorry, 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 Approach

The final human do-able way applies an  home-made 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.       

 Non-programmers 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 

bullet Download executable
bullet Download source (Note: program requires routines residing in our library zip file of commonly used units.  Library file DFFVLIB15 or later is required to recompile this program )
bullet Download current library file (DFFLibV15) required to recompile this program.

 

Suggestions for Further Explorations

???
.
 
 
   
   

 

Original:  August 29. 2017

Modified:  August 30, 2017

 

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