You are Here: Home >< Maths

# Counting watch

1. What's the most efficient way of counting how many numbers there are between 1 and, say, 644 that don't have the digit 5 in it.

More generally, how would one count how many numbers there are from 1 to n that don't have an r-digit in it (0 <= r <= 9). (Is there a general formula?)

Galois.
2. (Original post by Galois)
What's the most efficient way of counting how many numbers there are between 1 and, say, 644 that don't have the digit 5 in it.

More generally, how would one count how many numbers there are from 1 to n that don't have an r-digit in it (0 <= r <= 9). (Is there a general formula?)

Galois.
Probably the inclusion-exclusion formula.

So for the 644 case, let A = numbers 5**, B = numbers *5*, C = numbers **5

Set of numbers with a 5 in them is A U B U C and

|AUBUC| = |A|+|B|+|C| - |AnB|-|AnC|-|BnC|+|AnBnC|

= 100 + 60 + 64 - 10 - 10 - 6 + 1 = 199,

which I hope is the right answer.
3. (Original post by RichE)
Probably the inclusion-exclusion formula.

So for the 644 case, let A = numbers 5**, B = numbers *5*, C = numbers **5

Set of numbers with a 5 in them is A U B U C and

|AUBUC| = |A|+|B|+|C| - |AnB|-|AnC|-|BnC|+|AnBnC|

= 100 + 60 + 64 - 10 - 10 - 6 + 1 = 199,

which I hope is the right answer.
OK. So say you want to know how many 5 digit numbers there are from 1 to n (n being a very large number). Would it be best to do the following:

1-digit numbers that contain 5 = 1
2-digit numbers that contain 5 = (1).8 + 1.10 = 18
3-digit numbers that contain 5 = (1+18).8 + 1.100 = 252
4-digit numbers that contain 5 = (1+252).8 + 1.1000 = 3024
.
.
.
U_[r+2] = (1 + U_[r+1]).8 + 10^(r+1) _____ {U_1 = 1, U_2 = 18}

And then solve the difference equation?

Galois.

Edit: There's something wrong with that DE. Although it's second order, I seem to get only 1 arbitrary constant in the complimentary function, which shouldn't happen. The roots of the auxilliary equation are 0 and 8 - which leads to the single constant. Anybody?
4. . . .
5. (Original post by Galois)
What's the most efficient way of counting how many numbers there are between 1 and, say, 644 that don't have the digit 5 in it.

More generally, how would one count how many numbers there are from 1 to n that don't have an r-digit in it (0 <= r <= 9). (Is there a general formula?)

Galois.
MS Excel

Put numbers in col a

split into cols BCD(EFG...) using string functions.

test for =5, using array formula(e) for speed.

use SUMIF to total

subtract from MAX in col A or similar

For general soln, use a master cell for the key value and absolute references.

Aitch

This is the "efficient way" you asked for - not maths!
6. (Original post by Aitch)
MS Excel

Put numbers in col a

split into cols BCD(EFG...) using string functions.

test for =5, using array formula(e) for speed.

use SUMIF to total

subtract from MAX in col A or similar

For general soln, use a master cell for the key value and absolute references.

Aitch

This is the "efficient way" you asked for - not maths!
Thanks, but we're not allowed to use any software during an exam - just pen and paper.

Galois.
7. (Original post by Galois)
Thanks, but we're not allowed to use any software during an exam - just pen and paper.

Galois.

Sorry! Didn't grasp it was for an exam!

Aitch
8. If your number is x, then define the number n to be the next largest number, smaller than x that doesnt have a 5 in, then the formula is
n - 9^0[(n+5)/10] - 9^1[(n+50)/100] - 9^2[(n+500)/1000] - 9^3[(n+5000)/10000] ....
Where [m] is the integer part of m (floor function).

This is because every 10th number cant be counted, then when you get to 50, you cant count the nine numbers 50-54, 56-59 (55 already counted) and these occur every 100 numbers. Then you cant count all the numbers from 501 to 549 and 560-599 excluding all those ending in 5 and those starting with 55_ ...which is 100-10-9 = 81 numbers
Then from 5000-5999, excluding those ending in 5, those ending in 50, and those ending in 500. Which is 1000-100-90-81 = 729

The n+5, n+50, bits are because if n = 9, then [n/10] = 0, but clearly 5 cannot be counted. Same for n between 50 and 99, none of the numbers from 50 to 59 would be excluded. I spose if you defined [m] to be the nearest integer, rather than the floor function then you could get rid of all that.
9. (Original post by JamesF)
....get rid of all that.
Fair enough. But the original problem can still be solved by considering the reccurence relation U_[r+2] = (1 + U_[r+1]).8 + 10^(r+1) _____ {U_1 = 1, U_2 = 18}

If you begin by trying U_r = lambda^n then problems will occur as there will only be 1 constant.

Should there be a change of variable?

Galois.
10. Here's the way I do it.
If you give a number is x containing n figures. It's similar to the way I do with your case here. Hope you can get it.

In this case x = 664, x contains 3 figures. Let put it abc.
If we count from 1 to 599.
So set of a:{0,1..,5}-{5}, b and c:{0,1..,9}-{5}
Number of choices of a: 5
That of b is 9, that of c is 9.
So number of numbers can be formed with no digit 5 in it (1->599) is
5.9.9 = 405.

Now count from 600 to 659.
a = 6, b:{0,1,..5} - {5}, c:{0,1,..,9}-{5}
a: 1 choice, b: 6 choices, c: 9 choices
Number of abc can be formed:
1.5.9= 45

Then from 660 to 664, easily to find: 4 numbers
(or a: 1 choice (=6), b: 1 choice (=6), c: 4 choices (0->4)
Total number is:
405 + 45 + 4 = 454.

This is called multiplication rule I think

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: February 14, 2005
Today on TSR

### Cambridge interviews

Find out which colleges are sending invitations

### University open days

Wed, 21 Nov '18
• Buckinghamshire New University
Wed, 21 Nov '18
• Heriot-Watt University
Wed, 21 Nov '18
Poll
Useful resources

### Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams