At Least Four Distinct Prime Factors Less Than 100

It can be verified that there are $23$ positive integers less than $1000$ that are divisible by at least four distinct primes less than $100$.
Find how many positive integers less than $10^{16}$ are divisible by at least four distinct primes less than $100$.

To solve this problem, the principle of Inclusion-Exclusion will prove useful:

1. First, we need to consider the 25 prime numbers less than 100:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

2. We find the number of numbers less than 10^16 that are divisible by the product of any 4 of these primes. There are 14950 combinations (25 choose 4), and for each combination, the logarithm base 10 of the product of the 4 primes is less than 16. We then subtract the number of numbers less than 10^16 that are divisible by the product of any 5 of these primes. There are 53,130 combinations (25 choose 5), and for each combination, the logarithm base 10 of the product of the 5 primes is less than 16.

3. We then add the number of numbers less than 10^16 that are divisible by the product of any 6 of these primes. There are 177100 combinations (25 choose 6), but only for 177,065 combinations is the log base 10 of the product of the 6 primes less than 16.

4. Subtract the number of numbers less than 10^16 that are divisible by the product of any 7 of these primes. There are 480700 combinations (25 choose 7), but only for 480,478 combinations is the log base 10 of the product of the 7 primes less than 16.

5. Lastly, add the number of numbers less than 10^16 that are divisible by the product of any 8 of these primes (25 choose 8), which is 1081575. But only for 1,081,075 combinations is the log base 10 of the product of the 8 primes less than 16.

So, based on the Inclusion-Exclusion principle, the total number of such numbers is 14950 – 53130 + 177065 – 480478 + 1081075 = 826512. Hence, there are 826512 positive integers less than 10^16 that are divisible by at least four distinct primes less than 100.

More Answers: