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

How many seven digit numbers contain the digit seven at least once?

Ah, a simple search problem. We need only generate all seven digit numbers, then examine all the digits of each each to see any are 7, and count all those for which the answer is “yes.” Just the sort of thing computers are good for. Let us whip out the trusty CFX-9850G or FX-7400G and get to it, then.

Looking forward just a little bit, though, we realize checking
the answer — the CFX-9850G would not make a mistake, of
course, but our program might — would be the slightest bit
tedious.
We cleverly generalize the program a little bit to generate
numbers of *any* specified length.
We wind up with the following program, available as a text file with .CAT file contents,
or here in text.
Once again, lines and parts of lines starting with a semicolon
(“;”) are comments and are not actually entered into the
calculator.

Program P042301 (123 bytes):

; Variables: ; A is number of digits, then number being examined ; B is count of 7-containing numbers ; C is copy of current number being examined ; D is low bound on numbers with proper number of digits ; E is is high bound on numbers with proper number of digits ; Symbols: ; -> is assignment arrow ; 10^x is ten to the power of operator ; <> is not equal relational ; / is division operator "Digits"?->A ; Get number of digits of numbers to process Int Abs A->A ; Ensure is a non-negative integer 10^xA->E ; Get largest value 0->B ; Initialize count of 7-containing numbers .1E->D ; Get first number with number of digits E-1->E ; Get last number with number of digits For D->A To E ; Loop through numbers with right number of digits A->C ; Copy the current number to C While C<>0 ; Check all digits of C If 10Frac (C/10)=7 ; If the bottom digit is a 7 Then 0->C ; Then clear the number (short-circuit loop) B+1->B ; Increment count of 7-containing numbers Else Int (C/10)->C ; Otherwise drop bottom digit of C IfEnd ; [End of test on bottom digit of C] WhileEnd ; [End of loop on digits of C] Next ; [End of loop through proper sized numbers] B ; Report count of 7-containing numbers

We run the program, and when it asks us

Digits?

We reply

1

The answer comes back, 1.
Good.
There is one 1-digit number whose digit is 7 (and I bet we
know what number that is).
Now we try again with length 2: the answer comes back, 18.
Let’s see: there are 10 numbers of the form 7*x* and 9
numbers of the form *x*7 (remember, the leading digit of a
*k* digit number should not be 0), but we want to count 77
only once, so that gives 10+9-1 = 18 two digit numbers containing
a 7 digit.
We are on a roll.
So we run the program again with length 7.

Four days later, the calculator dies as the batteries run out.

Well, that is unfortunate. We could hook the calculator up to a power supply so it can sit there and count for two weeks. We can change the program so it periodically saves state and can pick up from a saved state — “checkpoint/restart” in the lingo of the trade — so it can survive a battery change. Or we can think instead. Let’s try thinking.

Call “the number of k-digit numbers with a 7 in them”
X_{k}, and suppose we already know X_{k} for k=1,
2, ..., n-1, and further suppose we want to know X_{n}.
Now, there are two types of numbers with 7 in them.
There are a bunch of numbers of the form 7*xx...x* where
there are n-1 *x*’s.
Then there are numbers of the form *yxx...x* where *y*
is not 7 or 0, and there are n-1 *x*'s at least one of which
is a 7.
There are 10^{n-1} numbers of the first form.
There are 8 possible values of *y*.
We need the number of n-1 digit sequences containing a 7 to have
something to multiply 8 by.

Now, “n-1 digit sequence” is not the same as
“n-1 digit number,” because we *do* want to count
numbers like 3007 — the “007” is a 3 digit
sequence, but not a 3 digit number.
We would count that as a 1 digit number.
So the number of n-1 digit *sequences* containing 7 is the
number of n-1 digit numbers containing 7, *plus* the number
of n-2 digit numbers containing 7, plus ..., plus the number of
one digit numbers containing 7.
So the formula we want is:

X_{n} = 10^{n-1} + 8(X_{n-1} + ... + X_{1})

From this, we can generate a little table:

n |
X |
---|---|

1 |
1 |

2 |
18 |

3 |
252 |

4 |
3168 |

5 |
37512 |

6 |
427608 |

7 |
4748472 |

So now we have our answer: the number of 7 digit numbers containing at least one 7 is 4748472.

But what an incredibly ugly formula! There has to be a better way. Let us therefore think about this some more.

If a number has a digit that is 7, we will count it.
This means that if it has *no* digit that is 7, we will
*not* count it.
Oh.
So the first digit has to be non-zero and non-7: there are 8
such digits.
And the remaining digits have to be non-7: there are 9 of
these digits.
So the number of n digit numbers *not* containing 7 is
8×9^{n-1}.
The number of n digit numbers is 9×10^{n-1}.
So the number of n digit numbers containing 7 is

X_{n} = 9×10^{n-1} - 8×9^{n-1}.

And X_{7} = 4748472.

That’s much better, now. And as an extra bonus, in this form we observe that as n tends to infinity, 90% of all numbers have a “7” in them.

Hmmm...

[ Previous page | Top of page | Next page ]

Copyright © 2001 Brian Hetrick

Page last updated 25 November 2001.