Maths Olympiad Prep

Library / /16 of 520

Number theory Difficulty 6.2 National olympiad Find the answer

Let NN denote the number of all natural numbers nn such that nn is divisible by a prime p>np> \sqrt{n} and p<20p<20. What is the value of NN ?

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,192, 3, 5, 7, 11, 13, 17, 19.

2. **Determine the range of nn for each prime pp**:
For a prime pp, nn must be divisible by pp and p>np > \sqrt{n}. This implies nn must be in the range pn<p2p \leq n < p^2.

3. **Count the number of valid nn for each prime pp**:
For each prime pp, the valid nn are p,2p,3p,,(p1)pp, 2p, 3p, \ldots, (p-1)p. The number of such nn is p1p-1.

4. Sum the counts for all primes:
- For p=2p = 2: The valid nn are 22, so there is 11 number.
- For p=3p = 3: The valid nn are 3,63, 6, so there are 22 numbers.
- For p=5p = 5: The valid nn are 5,10,15,205, 10, 15, 20, so there are 44 numbers.
- For p=7p = 7: The valid nn are 7,14,21,28,35,427, 14, 21, 28, 35, 42, so there are 66 numbers.
- For p=11p = 11: The valid nn are 11,22,33,44,55,66,77,88,99,11011, 22, 33, 44, 55, 66, 77, 88, 99, 110, so there are 1010 numbers.
- For p=13p = 13: The valid nn are 13,26,39,52,65,78,91,104,117,130,143,15613, 26, 39, 52, 65, 78, 91, 104, 117, 130, 143, 156, so there are 1212 numbers.
- For p=17p = 17: The valid nn are 17,34,51,68,85,102,119,136,153,170,187,204,221,238,255,27217, 34, 51, 68, 85, 102, 119, 136, 153, 170, 187, 204, 221, 238, 255, 272, so there are 1616 numbers.
- For p=19p = 19: The valid nn are 19,38,57,76,95,114,133,152,171,190,209,228,247,266,285,304,323,34219, 38, 57, 76, 95, 114, 133, 152, 171, 190, 209, 228, 247, 266, 285, 304, 323, 342, so there are 1818 numbers.

5. Sum the counts:
1+2+4+6+10+12+16+18=69 1 + 2 + 4 + 6 + 10 + 12 + 16 + 18 = 69

The final answer is 69\boxed{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.