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
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
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.
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.
365 Puzzlers Calendar 2017
365 Puzzlers Calendar 2018
(Hint: If you can
wait, current year calendars are usually on sale in January.)
e-mail with your comments about this program (or anything else).
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,
Finding the solution seems daunting at first glance, but after studying on it
a bit, a few helpful clues come to light:
- The smallest solution number is 3 and the largest is 300,000.
- 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:
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.
|The "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.|
|The "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. |
|The "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.
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
Running/Exploring the Program
Suggestions for Further Explorations
|Original: August 29. 2017
August 30, 2017