The problem statement from the Ole Miss Problems of the Week page is:

Think of all of the possible different seven-digit numbers
of the form **1abcdef**, such that the digits
**a**, **b**, **c**,
**d**, **e**, and **f**
must either be 0 or 1.
Your task is to determine the sum of all such seven-digit
numbers of this form.

Knowing that computation (with our handy CFX-9850G or FX-7400G) is next to Godliness, we decide to write a program to answer this question.

The hard part of this problem is generating all seven-digit
numbers where all the digits are either 0 or 1.
We could simply count through all seven-digit numbers, look
at all the digits of each, and reject the number of it has
a digit that is not 0 or 1.
But that would take a long time.
So we want a way to find the next of these special numbers
when we already have one.
(We know the first, trivially: 1000000).
If we add 1 to the number, we get the next regular number,
but the last digit may be 2.
We want to turn that 2 into a 0 and add 1 to the next digit
over.
That means add 10 (to add 1 to the next digit over) and
subtract 2 — adding 8 will do both at once.
But then we want to check the next digit over, and if
*it* is 2, we want to do the same thing.

So if we add 1, then look at the individual digits from the right to the left, looking for a 2 and adding 8 when we find one, we will basically force the addition to carry at 2 in a digit instead of at 10 in a digit. This will generate all the numbers we want. When we no longer have a seven digit number, we are done.

However, extracting a specific digit means dividing by the
appropriate power of 10, taking the fractional part,
multiplying by 10, and taking the integer part.
We are going to do this just to compare the digit to 2.
If we just divide by the next higher power of 10, if the
*fractional* part is .2 or greater, then we know we
need to pull the add 8 trick — and 8 times the
appropriate power of 10 is the same as .8 times the next
higher power of 10.

So we made up for the tedium of having to figure out how to count in binary using decimal by being clever with exponents. Modestly pleased with our cleverness, we can write our program.

The program is available as a text file with .CAT file contents, or here in text. As before, lines and parts of lines starting with a semicolon (“;”) are comments and are not actually entered into the calculator.

; Variables: ; A is the current seven-digit number of the special form ; B is the current sum of seven-digit numbers of the special form ; C is the power of 10 used to check the digits of A ; Symbols: ; EE is the EXP key ; -> is the assignment arrow ; < is the less than relational ; / is the divide operator ; >= is the greater than or equal to relational 1EE6->A ; Start A with the first 7 digit number 0->B ; Zero out the sum accumulator While A<1EE7 ; As long as A is within range B+A->B ; Add A into the accumulator A+1->A ; Increment A 10->C ; Check for carry: look at the bottommost digit While Frac (A/C)>=.2; As long as the current digit is 2 A+.8C->A ; Make it zero and increment the higher digit 10C->C ; Look at the next higher digit WhileEnd ; [End of check for carry loop] WhileEnd ; [End of A within range loop] B ; Report the sum B

All right. We run the program and get:

67555552

Hmm, what an interesting number. Where does it come from? Let’s think about this problem for a minute.

We want to add all the numbers of the form
**1abcdef**, where all the letters are either
0 or 1.
That is two possibilities per letter.
That means there are 2^{6}, or 64, of these
numbers.
Pick a letter.
In half of those 64 numbers, that letter will be 0; in the
other half of those 64 numbers, that same letter will be 1.
The 1, however, is 1 all 64 times.
So the sum of all these numbers will have 32 in the ones
place, 32 in the tens place, and so forth, up to 32 in the
100,000s place; then 64 in the 1,000,000s place.
Putting this into decimal gives us:

......32 ones place .....32. tens place ....32.. hundreds place ...32... thousands place ..32.... ten thousands place .32..... hundred thousands place 64...... millions place -------- 67555552

Oh. That was easy. Maybe we should think before computing more often.

[ Previous page | Top of page | Next page ]

Copyright © 2001 Brian Hetrick

Page last updated 25 November 2001.