Inclusion-Exclusion Principle: an Example

I picked this example from the MAA MiniuteMath site.

Call a number "prime-looking" if it is composite but not divisibly by 2, 3, or 5. The three smallest prime-looking numbers are 49, 77, and 91. There are 168 prime numbers less than 1000. How many prime-looking numbers are there less than 1000?

Solution

|Contact| |Front page| |Contents| |Algebra| |Store|

For any positive integers N and m, the number of integers divisible by m which are less than N is given by [(N-1)/m], where the brackets designed the floor function. For example, the number of multiples of three below 20 is [19/3] = 6; these are 3, 6, 9, 12, 15, 18.

Turning to the problem, below 1000 there are

499 = [999/2] numbers divisible by 2,
333 = [999/3] numbers divisible by 3,
199 = [999/5] numbers divisible by 5,
166 = [999/6] numbers divisible by 6 = 2·3,
99 = [999/10] numbers divisible by 10 = 2·5,
66 = [999/15] numbers divisible by 15 = 3·5, and
33 = [999/30] numbers divisible by 30 = 2·3·.

According to the Inclusion-Exclusion Principle, the amount of integers below 1000 that could not be prime-looking is

499 + 333 + 199 - 166 - 99 - 66 + 33 = 733.

There are 733 numbers divisible by at least one of 2, 3, 5. Note that this count includes (prime) 2, 3, and 5.

Waht can be said of the remaining 999 - 733 = 266 numbers? These are the numbers that are not divisible by either 2, 3, or 5. Are these prime-looking? No, not all of them. Some are really prime, not just appearing so. As was stated in the problem, there are 168 are primes below 1000. We have to exclude those. But number 2, 3, 5 have been discounted before, which leaves us with 165 primes extras. Subtracting gives 266 - 165 = 101.

Now, a final observation. Number 1 is not divisible by any greater number, 2, 3, 5 in particular. Thus it was not counted among the 733 composite numbers above. So, it is counted among the remaining 266 and, not being a prime, among the last group of 101 numbers. These are the numbers that are not divisible by either 2, 3, or 5, which trivially includes 1. But 1 is not composite and thus is not prime-looking. To get the total of prime-looking numbers we have to remove 1 from the count, leaving 101 - 1 = 100.

References

1. V. K. Balakrishnan, Theory and Probl ems of Combinatorics, Schaum's Outline Series, McGraw-Hill, 1995

|Contact| |Front page| |Contents| |Algebra| |Store|