Combinatorics Question

[Giorgos Giannoulakis]

Hello to everyone!

I want to find all non - negative integers [math]0 \le k \le 10^7[/math] which have at least one of the digits [math]4,5,6[/math] in their decimal spread. My thought is this:

If [math]E_1[/math] is the eventuality that [math]k[/math] has at least one of the digits [math]4,5,6[/math] in its decimal spread then [math]E_1^c[/math] is the complementary eventuality which says that [math]k[/math] has none of the digits [math]4,5,6[/math] in its decimal spread so if we condiser the partition [math]Ω = E_1 \cup E_1^c[/math] of our sample space then it is easy to see that:

[math]\vert{E_1} \vert = \vert{Ω} \vert - \vert{E_1^c} \vert = 10^7 + 1 - 7^7 = 9176458[/math]​

Am I wrong or right? The reason I am questioning myself is because I find this number very big for what the problem states

Thank you in advance!

​

 

[Dr.Peterson]

Sounds good to me. The set of numbers with at least one of the digits 4, 5, 6 is the complement of the set of numbers with none of the digits 4, 5, 6.

 

[Giorgos Giannoulakis]

Actually I think the answer is [math]9176457[/math] because we have to substract 1, which is the number [math]10^7[/math] because it does not contain any 4, 5 or 6 and is an 8-digit number so not included in the [math]7^7[/math] we have already substracted. Right ?

 

[Dr.Peterson]

Actually I think the answer is [math]9176457[/math] because we have to substract 1, which is the number [math]10^7[/math] because it does not contain any 4, 5 or 6 and is an 8-digit number so not included in the [math]7^7[/math] we have already substracted. Right ?

You're right; I initially questioned your adding 1 in your work ([imath]10^7+1-7^7[/imath]), and didn't give it a lot of thought.

 

[JeffM]

I get a different answer.

The number of unique 7-digit numbers starting with 1 is obviously [imath]10^7 - 1.[/imath]

When we add in zero and 10,000,000, the number is [imath](10^7 - 1) + 2 = 10^7 + 1.[/imath]

So, I don’t see why 1 is subtracted.

Furthermore, I don’t understand the [imath]7^7[/imath] at all.

That number includes the strings 0, 00, 000, etc., which clearly are duplicate numbers. I think the correct answer is


[math](10^7 + 1) - 1 - 6 * 7^6 = 10^7 - 6 * 7^6 = \\ 10,000,000 - 705,894 = 9,294,106[/math].

 

[Steven G]

The number of unique 7-digit numbers starting with 1 is obviously [imath]10^7 - 1.[/imath]

Jeff,
Am I missing something or did you mean to say 8-digit number?
I am also missing the 7^7 or 7^6
10000000
10000001
10000002
...
10000010
...
19999999
I don't see any duplication.
Steve

 

[pka]

I want to find all non - negative integers [imath]\Large~{0 \le k \le 10^7}[/imath] which have at least one of the digits [math]4,5,6[/math] in their decimal spread.

Jeff,
Am I missing something or did you mean to say 8-digit number?
I am also missing the 7^7 or 7^7

As you can see the PO wanted [imath]0\le K\le 10^7=10000000[/imath].
[imath]10^7-7^7=9176457[/imath]

 

[Steven G]

As you can see the PO wanted [imath]0\le K\le 10^7=10000000[/imath].
[imath]10^7-7^7=9176457[/imath]

Got it, you must have 4, 5 &/or 6

 

[JeffM]

Jeff,
Am I missing something or did you mean to say 8-digit number?
I am also missing the 7^7 or 7^6
10000000
10000001
10000002
...
10000010
...
19999999
I don't see any duplication.
Steve

The only relevant 8-digit number is 10,000,000. Any other 8-digit number is [math]> 10^7.[/math]
The reason why I suspect that pka is wrong is that 01,000,000 is the same number (although not the same string) as 1,000,000 so pka’s way is counting strings rather than numbers. So, once we are past 1-digit numbers, we are double counting if we allow the initial digit to be zero.

 

[Cubist]

The reason why I suspect that pka is wrong is that 01,000,000 is the same number (although not the same string) as 1,000,000 so pka’s way is counting strings rather than numbers. So, once we are past 1-digit numbers, we are double counting if we allow the initial digit to be zero.

I'm not sure which numbers you think are being double counted. Perhaps it would help you if I explain my thinking in some detail...

The upper limit number 10^7 = 10,000,000 doesn't have a digit 4,5 or 6 therefore this 8 digit number can be discarded. All remaining numbers in the range have up to 7 digits. However, if any number has fewer than 7 digits then it can be "left padded" by zeros to become 7 digits in length. For example, 23402 could be written as 0023402

Now, if the digits are [imath] d_1 d_2 d_3 d_4 d_5 d_6 d_7 \text{, where } d_n[/imath] denotes the nth digit, then
there are 10^7 ways to assign all [imath]d_n[/imath] if [imath]0 \leq d_n \leq 9[/imath]
there are (10 - 3)^7 ways to assign all [imath]d_n[/imath] if we no longer allow any digit to be 4, 5 or 6
therefore, the remaining (10^7 - 7^7) numbers must all contain 4, 5 or 6

Hope this helps!

 

[JeffM]

I'm not sure which numbers you think are being double counted. Perhaps it would help you if I explain my thinking in some detail...

The upper limit number 10^7 = 10,000,000 doesn't have a digit 4,5 or 6 therefore this 8 digit number can be discarded. All remaining numbers in the range have up to 7 digits. However, if any number has fewer than 7 digits then it can be "left padded" by zeros to become 7 digits in length. For example, 23402 could be written as 0023402

Now, if the digits are [imath] d_1 d_2 d_3 d_4 d_5 d_6 d_7 \text{, where } d_n[/imath] denotes the nth digit, then
there are 10^7 ways to assign all [imath]d_n[/imath] if [imath]0 \leq d_n \leq 9[/imath]
there are (10 - 3)^7 ways to assign all [imath]d_n[/imath] if we no longer allow any digit to be 4, 5 or 6
therefore, the remaining (10^7 - 7^7) combinations must all contain 4, 5 or 6

Hope this helps!

@Cubist

You have identified my point exactly.

009999is a different string of digits from 9,999, but it is not a different number. As I read the problem, there is nothing that requires strings to have 7 digits.

 

[Cubist]

009999is a different string of digits from 9,999, but it is not a different number. As I read the problem, there is nothing that requires strings to have 7 digits.

It's this range that allows the use of 7 digits
[math]0 \le k \le 10^7-1[/math](I added the -1 because 10^7 doesn't have a digit 4,5 or 6)

And the use of 7 digits makes this an easy problem. All possible numbers can be written xxxxxxx

If the problem had been [math]0 \le k \le 12382[/math] then the calculation would have been much more involved. We'd have had to consider:-

• 0xxxx
• 10xxx and 11xxx
• 120xx, 121xx, 122xx
• 1230x, 1231x, 1232x, ... 1237x

 

[JeffM]

It's this range that allows the use of 7 digits
[math]0 \le k \le 10^7-1[/math](I added the -1 because 10^7 doesn't have a digit 4,5 or 6)

And the use of 7 digits makes this an easy problem. All possible numbers can be written xxxxxxx

If the problem had been [math]0 \le k \le 12382[/math] then the calculation would have been much more involved. We'd have had to consider:-

• 0xxxx
• 10xxx and 11xxx
• 120xx, 121xx, 122xx
• 1230x, 1231x, 1232x, etc

I clearly have not made my point clear. My fault.

[imath]7^7[/imath] counts the number of strings with 7 digits. I agree. But why are we saying that 7 digits is mandatory? Nothing whatsoever in the presentation of the problem specified strings of exactly 7 digits. The question is about numbers.
0000001
000001
00001
0001
001
01
1

all specify the same number.

 

[Steven G]

I clearly have not made my point clear. My fault.

[imath]7^7[/imath] counts the number of strings with 7 digits. I agree. But why are we saying that 7 digits is mandatory? Nothing whatsoever in the presentation of the problem specified strings of exactly 7 digits. The question is about numbers.
0000001
000001
00001
0001
001
01
1

all specify the same number.

Fine you have duplications. What if we insist on using just 7-digit numbers?? Then the numbers in your list are all the same but will only be counted once.
If we in fact allow a number to be less than 7-digit long, then all the numbers in your list are equal to one another and now I see your point. I need to think about this some more.

 

[pka]

I think a great deal of this confusion could have been avoided had the o.p. been:
find the number of non-negative integers [imath]k<10^7[/imath] that contain at least one of [imath]4,~5,\text{ or 6 .}[/imath]
Now it is perfectly clear that each of [imath]9,~99,~9999,~99999,~\&~9999999[/imath] should not be counted and therefore must be eliminated. So [imath]10^7-7^7=9176457[/imath].
We can all see why testing companies pay big bucks for a team of editors.




[imath][/imath][imath][/imath]

 

[Cubist]

Here's some code that verifies the answer 9176457.

import re

# Search for a 4,5 or 6 anywhere in a string...
regexp = re.compile("[456]")

matchCount = 0
for i in range(0, 10**7 + 1): # gives same result with or without the +1
    if regexp.search(str(i)):
        matchCount += 1

print(matchCount)

 

[Cubist]

[imath]7^7[/imath] counts the number of strings with 7 digits. I agree. But why are we saying that 7 digits is mandatory? Nothing whatsoever in the presentation of the problem specified strings of exactly 7 digits. The question is about numbers.
0000001
000001
00001
0001
001
01
1

all specify the same number.

Yes, they represent equivalent numbers. But the math only includes 7 digit strings...

0000001 <- this has seven digits and therefore it's counted
000001
00001 <-
0001 <- none of the rest have seven digits, and aren't counted in the calculation
001 <-
01
1

--

If we were counting the ways that THREE digits can take the values 0 to 9 inclusive, then the first digit has 10 options, the second has 10 and the last has 10 options. 10*10*10 = 1000 options. This is correct because the range 000 -> 999 has 1000 numbers. We don't add on 10*10 for the two digit numbers, because these are catered for by having a single leading digit of '0' within the 3 digit calculation.

NOTE: if the question had asked for numbers that contain a digit 0,1 or 2 then the method in post#1 wouldn't work (because we don't usually write leading zeros, which this method relies upon). FYI: the answer for digits 0,1 or 2 is 9039202. This was obtained by changing the code in post#16 to have regexp = re.compile("[012]")

 

[JeffM]

Yes, they represent equivalent numbers. But the math only includes 7 digit strings...

0000001 <- this has seven digits and therefore it's counted
000001
00001 <-
0001 <- none of the rest have seven digits, and aren't counted in the calculation
001 <-
01
1

--

If we were counting the ways that THREE digits can take the values 0 to 9 inclusive, then the first digit has 10 options, the second has 10 and the last has 10 options. 10*10*10 = 1000 options. This is correct because the range 000 -> 999 has 1000 numbers. We don't add on 10*10 for the two digit numbers, because these are catered for by having a single leading digit of '0' within the 3 digit calculation.

NOTE: if the question had asked for numbers that contain a digit 0,1 or 2 then the method in post#1 wouldn't work (because we don't usually write leading zeros, which this method relies upon). FYI: the answer for digits 0,1 or 2 is 9039202. This was obtained by changing the code in post#16 to have regexp = re.compile("[012]")

Let me see if I grasp the argument. We can count the number of non-negative integers less than 10^7 by counting the number of possible strings of seven glyphs chosen from the ten glyphs for the decimal digits. We do not have to worry about double counting because we have excluded integers represented by strings of fewer than seven glyphs.

 

[Dr.Peterson]

Let me see if I grasp the argument. We can count the number of non-negative integers less than 10^7 by counting the number of possible strings of seven glyphs chosen from the ten glyphs for the decimal digits. We do not have to worry about double counting because we have excluded integers represented by strings of fewer than seven glyphs.

I wouldn't quite say it that way. We are including integers that can be represented by shorter strings, but are only counting string of seven digits, so we are not counting anything twice.

The problem is about numbers less than or equal to [imath]10^7[/imath]. Apart from 10,000,000, each of these corresponds to a unique string of 7 digits, of which there are [imath]10^7[/imath], from 0000000 to 9999999. If we include 10,000,000, we would add 1 to the count, and get [imath]10^7+1[/imath]. But we don't need to include it, since it can't have any 4, 5, or 6.

All numbers in [imath]0\le k\le10^7[/imath] that contain a 4, 5, or 6 are in fact in [imath]0\le k<10^7[/imath], which correspond to those 7-digit strings. We don't want to include 10,000,000 because the next step counts only strings of 7 digits. So we ignore that, and consider only the [imath]10^7[/imath] strings.

Within that set of [imath]10^7[/imath] strings, [imath]7^7[/imath] do not contain 4, 5, or 6 (namely the strings of 7 digits taken from {0, 1, 2, 3, 7, 8, 9}).

So the answer is [imath]10^7-7^7[/imath].

 

[JeffM]

I wouldn't quite say it that way. We are including integers that can be represented by shorter strings, but are only counting string of seven digits, so we are not counting anything twice.

The problem is about numbers less than or equal to [imath]10^7[/imath]. Apart from 10,000,000, each of these corresponds to a unique string of 7 digits, of which there are [imath]10^7[/imath], from 0000000 to 9999999. If we include 10,000,000, we would add 1 to the count, and get [imath]10^7+1[/imath]. But we don't need to include it, since it can't have any 4, 5, or 6.

All numbers in [imath]0\le k\le10^7[/imath] that contain a 4, 5, or 6 are in fact in [imath]0\le k<10^7[/imath], which correspond to those 7-digit strings. We don't want to include 10,000,000 because the next step counts only strings of 7 digits. So we ignore that, and consider only the [imath]10^7[/imath] strings.

Within that set of [imath]10^7[/imath] strings, [imath]7^7[/imath] do not contain 4, 5, or 6 (namely the strings of 7 digits taken from {0, 1, 2, 3, 7, 8, 9}).

So the answer is [imath]10^7-7^7[/imath].

Yes. I see it now.

Thanks to you and cubist for setting me straight.