# Puzzles

## 2001/2002 Puzzles

### 4 June 2001 (Sum Zeroes and Ones)

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 26, 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.