Intended for: May 18, 2013
Timetable
- First draft entered by Alonso del Arte on March 23, 2012 ✓
- Draft reviewed by Daniel Forgues on May 13, 2012 ✓
- Draft approved by Daniel Forgues on May 17, 2015 ✓
The line below marks the end of the <noinclude> ... </noinclude> section.
A016189:
.
-
{ 0, 1, 19, 271, 3439, 40951, 468559, 5217031, ... }
This sequence can also be computed using a
recurrence relation:
a (0) = 0; a (n) = 9 a (n − 1) + 10 n − 1, n ≥ 1. |
This shows that this sequence answers the question: “How many numbers in
have at least one
9 among their digits?” Up to
9, there is of course just
9. Up to
99 we have
9, 19, 29, ..., 89 (that’s nine numbers) and
90, 91, 92, ..., 99 (that’s ten numbers). And up to
999, we have
900, 901, 902, ..., 999 (that’s a hundred numbers), and between each multiple of
100 to the next, up to
800, we have nineteen numbers with
9s among their digits, so we can just multiply the previous term by
9 rather than count these numbers one by one, hence the recurrence.
Of course this can also be used for how many numbers (base
10) in
have at least one digit greater than or equal to
d, 0 ≤ d ≤ 9: 10 n − d n, n ≥ 0 |
.
This should also work for how many numbers (base
) in
have at least one digit greater than or equal to
db, 0 ≤ db ≤ b − 1: b n − db n, n ≥ 0 |
.
Now, for
, i.e. how many numbers from
0 to
0 have at least one digit greater than or equal to
0:
10 0 − 9 0 = 1 − 1 = 0, which is correct when we consider that leading zeros are not normally written (we make an exception for zero, otherwise we would have the empty string...). Or, if you prefer, you may add a
term to the formula, e.g.
to get
1 for
. The recurrence would be slightly modified thus:
a (0) = 1; a (1) = 1; a (n) = 9 a (n − 1) + 10 n − 1, n ≥ 2 |
.