Previous page Next page Navigation bar

Puzzles

2001/2002 Puzzles

23 April 2001 (Serious Sevens)

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 7x and 9 numbers of the form x7 (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” Xk, and suppose we already know Xk for k=1, 2, ..., n-1, and further suppose we want to know Xn. Now, there are two types of numbers with 7 in them. There are a bunch of numbers of the form 7xx...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 10n-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:

Xn = 10n-1 + 8(Xn-1 + ... + X1)

From this, we can generate a little table:

n

Xn

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×9n-1. The number of n digit numbers is 9×10n-1. So the number of n digit numbers containing 7 is

Xn = 9×10n-1 - 8×9n-1.

And X7 = 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 ]

Previous page Top of page Next page Navigation bar

Copyright © 2001 Brian Hetrick
Page last updated 25 November 2001.

Brian’s Casio Calculator Corner

Home

Programs

Tutorial

Puzzles

Index

2001/2002

Index

15 April 2002

11 February 2002

1 October 2001

24 September 2001

13 August 2001

30 July 2001

18 June 2001

4 June 2001

21 May 2001

7 May 2001

30 April 2001

23 April 2001

9 April 2001

18 February 2001

4 February 2001

29 January 2001

Previous years

In memoriam: Dijkstra

Site Information

Your Privacy

Site Map

E-mail

Site Technical Data