This discussion is closed.
Gauss
Badges: 11
Rep:
?
#1
Report Thread starter 15 years ago
#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.
0
RichE
Badges: 15
Rep:
?
#2
Report 15 years ago
#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.
0
Gauss
Badges: 11
Rep:
?
#3
Report Thread starter 15 years ago
#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?
0
Gauss
Badges: 11
Rep:
?
#4
Report Thread starter 15 years ago
#4
. . .
0
Aitch
Badges: 2
Rep:
?
#5
Report 15 years ago
#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!
0
Gauss
Badges: 11
Rep:
?
#6
Report Thread starter 15 years ago
#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.
0
Aitch
Badges: 2
Rep:
?
#7
Report 15 years ago
#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
0
JamesF
Badges: 1
Rep:
?
#8
Report 15 years ago
#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.
0
Gauss
Badges: 11
Rep:
?
#9
Report Thread starter 15 years ago
#9
(Original post by JamesF)
If your number is ....
....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.
0
BCHL85
Badges: 12
Rep:
?
#10
Report 15 years ago
#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
0
X
new posts
Back
to top
Latest
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise

How do you feel about your grades? Are they...

What I expected (142)
24.36%
Better than expected (127)
21.78%
Worse than expected (314)
53.86%

Watched Threads

View All
Latest
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise