Determine the largest possible number of primes among 100 consecutive natural numbers.
Solution
There are 25 primes among the numbers from 1 to 100. The number of primes in the next a few number intervals with length 100 are shown in the table:
| Interval | out | in | Number of primes |
|---|---|---|---|
| 1,...,100 | 25 | ||
| 2,...,101 | 1 | 101 | 26 |
| 3,...,102 | 2 | 102 | 25 |
| 4,...,103 | 3 | 103 | 25 |
| 5,...,104 | 4 | 104 | 25 |
| 6,...,105 | 5 | 105 | 24 |
| 7,...,106 | 6 | 106 | 24 |
The largest number of primes in these number intervals is 26.
We show now that there cannot be more primes among 100 consecutive natural numbers. Consider arbitrary 100 consecutive natural numbers, the least of which is larger than 7. None of the numbers under consideration that is divisible by one of numbers 2, 3, 5 and 7 is a prime. We show in the rest that there are at least 74 such numbers. As every second number is divisible by 2, there are 50 even numbers. As every third number is divisible by 3, there are at least 33 such numbers. Every second among them has been counted as an even number, thus there are at least 16 new numbers divisible by 3. As every fifth number is divisible by 5, there are at least 20 such numbers. Every second among them is even, thus the number of odd numbers divisible by 5 is 10. Among them in turn, every third is divisible by 3, thus there are at least 6 numbers divisible by 5 not counted yet. As every seventh number is divisible by 7, there are at least 14 such numbers. Every second among them is even, thus there are at least 7 odd numbers divisible by 7. Every third among them is divisible by 3, which eliminates at most 3 numbers, and every fifth is divisible by 5, which eliminates at most 2 numbers. Hence at least 2 numbers not counted before are divisible by 7. Altogether, we have at least composite numbers.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.