Number theoryDifficulty 6.2National olympiadFind the answer
Let N denote the number of all natural numbers n such that n is divisible by a prime p>n and p<20. What is the value of N ?
A number or a short expression. Spacing and $ signs are ignored.
Solution
1. Identify the primes less than 20: The primes less than 20 are: 2,3,5,7,11,13,17,19.
2. **Determine the range of n for each prime p**: For a prime p, n must be divisible by p and p>n. This implies n must be in the range p≤n<p2.
3. **Count the number of valid n for each prime p**: For each prime p, the valid n are p,2p,3p,…,(p−1)p. The number of such n is p−1.
4. Sum the counts for all primes: - For p=2: The valid n are 2, so there is 1 number. - For p=3: The valid n are 3,6, so there are 2 numbers. - For p=5: The valid n are 5,10,15,20, so there are 4 numbers. - For p=7: The valid n are 7,14,21,28,35,42, so there are 6 numbers. - For p=11: The valid n are 11,22,33,44,55,66,77,88,99,110, so there are 10 numbers. - For p=13: The valid n are 13,26,39,52,65,78,91,104,117,130,143,156, so there are 12 numbers. - For p=17: The valid n are 17,34,51,68,85,102,119,136,153,170,187,204,221,238,255,272, so there are 16 numbers. - For p=19: The valid n are 19,38,57,76,95,114,133,152,171,190,209,228,247,266,285,304,323,342, so there are 18 numbers.
5. Sum the counts: 1+2+4+6+10+12+16+18=69
The final answer is 69.
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.
Source: NuminaMath-1.5,
licensed Apache-2.0.
Statement and solution reproduced as published; topic and difficulty added by this site.