# Counting

WatchPage 1 of 1

Go to first unread

Skip to page:

This discussion is closed.

What's the

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.

**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

Report

#2

(Original post by

What's the

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.

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

(Original post by

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.

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

Report

#5

**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.

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

(Original post by

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!

Galois.

0

Report

#7

(Original post by

Thanks, but we're not allowed to use any software during an exam - just pen and paper.

Galois.

**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

Report

#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.

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

(Original post by

If your number is ....

....get rid of all that.

**JamesF**)If your number is ....

....get rid of all that.

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

Report

#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

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

Page 1 of 1

Go to first unread

Skip to page:

new posts

Back

to top

to top