Turn on thread page Beta
    • Thread Starter
    Offline

    2
    ReputationRep:
    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.
    Offline

    15
    ReputationRep:
    (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.
    • Thread Starter
    Offline

    2
    ReputationRep:
    (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?
    • Thread Starter
    Offline

    2
    ReputationRep:
    . . .
    Offline

    2
    ReputationRep:
    (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!
    • Thread Starter
    Offline

    2
    ReputationRep:
    (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.
    Offline

    2
    ReputationRep:
    (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
    Offline

    1
    ReputationRep:
    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.
    • Thread Starter
    Offline

    2
    ReputationRep:
    (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.
    Offline

    12
    ReputationRep:
    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
 
 
 

University open days

  • University of Bradford
    All faculties Undergraduate
    Wed, 21 Nov '18
  • Buckinghamshire New University
    All Faculties Postgraduate
    Wed, 21 Nov '18
  • Heriot-Watt University
    All Schools Postgraduate
    Wed, 21 Nov '18
Poll
Black Friday: Yay or Nay?
Useful resources

Make your revision easier

Maths

Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

Equations

How to use LaTex

Writing equations the easy way

Equations

Best calculators for A level Maths

Tips on which model to get

Student revising

Study habits of A* students

Top tips from students who have already aced their exams

Study Planner

Create your own Study Planner

Never miss a deadline again

Polling station sign

Thinking about a maths degree?

Chat with other maths applicants

Can you help? Study help unanswered threads

Groups associated with this forum:

View associated groups

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

Write a reply...
Reply
Hide
Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.