This discussion is now closed.
Check out other Related discussions
- alevel english literature coursework
- What's your age and body count?
- Does body count matter ?
- Tc2(CO)10,valence electron count for Tc in the dimer.
- The Forum Games Hurt/Heal Game
- physics radioactivity count rate gcse question
- Word count excess
- Was the dr supposed to do a ferritin blood test?
- went over my word count by 10% and i'm scared ill be capped
- 10% leeway on essays
- not meeting the word count
- Went over word limit.. soas penalty?
- Nursing placement
- Need help with problem solving
- GEM Warwick Work Experience
- Does each year at uni count
- body count
- ...
- Heavily over EPQ word count and very worried.
- Personal Statement
Counting
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.
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.
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.
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.
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.
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?
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.
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!
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!
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.
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.
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.
JamesF
If your number is ....
....get rid of all that.
....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.
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
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
Related discussions
- alevel english literature coursework
- What's your age and body count?
- Does body count matter ?
- Tc2(CO)10,valence electron count for Tc in the dimer.
- The Forum Games Hurt/Heal Game
- physics radioactivity count rate gcse question
- Word count excess
- Was the dr supposed to do a ferritin blood test?
- went over my word count by 10% and i'm scared ill be capped
- 10% leeway on essays
- not meeting the word count
- Went over word limit.. soas penalty?
- Nursing placement
- Need help with problem solving
- GEM Warwick Work Experience
- Does each year at uni count
- body count
- ...
- Heavily over EPQ word count and very worried.
- Personal Statement
Latest
Trending
Last reply 4 days ago
Did Cambridge maths students find maths and further maths a level very easy?Last reply 2 weeks ago
Edexcel A Level Mathematics Paper 2 unofficial mark scheme correct me if wrongMaths
71
Trending
Last reply 4 days ago
Did Cambridge maths students find maths and further maths a level very easy?Last reply 2 weeks ago
Edexcel A Level Mathematics Paper 2 unofficial mark scheme correct me if wrongMaths
71
