Question

How many numbers between 1 and 21,000,000 , including both 1 and 21,000,000 , are divisible by \(2,3,\) or 5 but not by \(7 ?\)

Short answer

13,200,000 numbers between 1 and 21,000,000 are divisible by 2, 3, or 5 but not by 7.

Step-by-step solution

Identify the Range

We need to find the numbers between 1 and 21,000,000 that are divisible by 2, 3, or 5, but not by 7. This means we will first count those divisible by 2, 3, or 5 including 1 to 21,000,000.

Count by Divisibility (Inclusion-Exclusion Principle)

Using the inclusion-exclusion principle, count the numbers divisible by 2, 3, or 5:- Numbers divisible by 2: \[ \left\lfloor \frac{21,000,000}{2} \right\rfloor = 10,500,000 \]- Numbers divisible by 3: \[ \left\lfloor \frac{21,000,000}{3} \right\rfloor = 7,000,000 \]- Numbers divisible by 5: \[ \left\lfloor \frac{21,000,000}{5} \right\rfloor = 4,200,000 \]

Subtract Intersections of Divisions

To adjust for overcounting, subtract numbers counted twice due to being divisible by combinations of these numbers:- Divisible by 6 (2 and 3): \[ \left\lfloor \frac{21,000,000}{6} \right\rfloor = 3,500,000 \]- Divisible by 10 (2 and 5): \[ \left\lfloor \frac{21,000,000}{10} \right\rfloor = 2,100,000 \]- Divisible by 15 (3 and 5): \[ \left\lfloor \frac{21,000,000}{15} \right\rfloor = 1,400,000 \]

Add Triple Divisibility

Add back numbers counted three times (as they have been subtracted more than necessary) and which are divisible by 30 (2, 3, and 5):- Divisible by 30: \[ \left\lfloor \frac{21,000,000}{30} \right\rfloor = 700,000 \]

Numbers Divisible by 2, 3, or 5

Combine previous inclusions and exclusions:\[ 10,500,000 + 7,000,000 + 4,200,000 - 3,500,000 - 2,100,000 - 1,400,000 + 700,000 = 15,400,000 \]

Subtract Numbers Divisible by 2, 3, or 5 and 7

Now, subtract from this the numbers divisible by 2 or 3 or 5 that are also divisible by 7. We apply the same inclusion-exclusion principle here:- Divisible by 14 (2 and 7): \[ \left\lfloor \frac{21,000,000}{14} \right\rfloor = 1,500,000 \]- Divisible by 21 (3 and 7): \[ \left\lfloor \frac{21,000,000}{21} \right\rfloor = 1,000,000 \]- Divisible by 35 (5 and 7): \[ \left\lfloor \frac{21,000,000}{35} \right\rfloor = 600,000 \]- Add those divisible by 42, 70, and 105 (2, 3, 5, and 7): * Divisible by 42: \[ \left\lfloor \frac{21,000,000}{42} \right\rfloor = 500,000 \] * Divisible by 70: \[ \left\lfloor \frac{21,000,000}{70} \right\rfloor = 300,000 \] * Divisible by 105: \[ \left\lfloor \frac{21,000,000}{105} \right\rfloor = 200,000 \]- Divisible by 210 (2, 3, 5, and 7): \[ \left\lfloor \frac{21,000,000}{210} \right\rfloor = 100,000 \]

Final Calculation

The count of numbers divisible by 2, 3, or 5 but not 7 is:\[ 15,400,000 - (1,500,000 + 1,000,000 + 600,000 - 500,000 - 300,000 - 200,000 + 100,000) \]Simplifying the expression inside the parentheses:\[ 1,500,000 + 1,000,000 + 600,000 - 500,000 - 300,000 - 200,000 + 100,000 = 2,200,000 \]Thus, the final result is:\[ 15,400,000 - 2,200,000 = 13,200,000 \]

Key concepts

Divisibility

Divisibility is the ability of one integer to be divided by another integer without having a remainder. For example, a number is divisible by 2 if it ends in 0, 2, 4, 6, or 8. This is crucial in solving problems like identifying how many numbers in a range have specific divisibility traits.
In the given exercise, we focus on numbers that are divisible by 2, 3, or 5. We start by counting all such numbers individually using floor division, as this finds how many times one number completely contains another.
The key to solving this problem is systematically adjusting our count to ensure accuracy without overcounting. Divisibility rules help simplify calculations and improve efficiency in dealing with large numbers inclusively, like our range from 1 to 21,000,000.

Discrete Mathematics

Discrete Mathematics is the branch of mathematics dealing with distinct and separate values. This field includes studying mathematical structures that are fundamentally discrete rather than continuous.
Inclusion-Exclusion Principle is one of the techniques commonly used in Discrete Mathematics. This principle helps calculate the size of the union of sets.
In our problem, we applied this principle to avoid overcounts when counting numbers divisible by multiple factors.
We began by counting numbers divisible by each of 2, 3, and 5. We then subtracted counts of numbers divisible by combinations of two factors and added back those divisible by all three factors, adjusting our count appropriately. This method efficiently identifies numbers across large data sets without overlooking overlaps.

Problem Solving

Problem-solving skills are essential when dealing with complex mathematical challenges, such as determining numbers divisible by certain integers.
Approaching such problems requires:

• Identifying what needs to be counted—here, numbers divisible by 2, 3, or 5.
• Using the Inclusion-Exclusion Principle to manage overlaps in counts from multiple divisors.
• Subtracting counts as needed—like numbers also divisible by 7, which do not fit the desired criteria.

In our solution, we refined our result to ensure accuracy by adjusting for numbers that met the base divisibility but failed an additional criterion, which in this case was divisibility by 7. Recognizing and correcting for these miscounted subsets is a critical part of the problem-solving process, ensuring accurate and efficient solutions.