Maths Olympiad Prep

Library / /203 of 520

Number theory Difficulty 6.8 National olympiad Find the answer

Let us call a positive integer kk{} interesting if the product of the first kk{} primes is divisible by kk{}. For example the product of the first two primes is 23=62\cdot3 = 6, it is divisible by 2, hence 2 is an interesting integer. What is the maximal possible number of consecutive interesting integers?

Boris Frenkin

A number or a short expression. Spacing and $ signs are ignored.

Solution

1. Define the problem and notation:
We need to determine the maximal number of consecutive interesting integers. An integer k k is interesting if the product of the first k k primes is divisible by k k . Let pn p_n denote the n n -th smallest prime number. For example, p1=2 p_1 = 2 , p2=3 p_2 = 3 , p3=5 p_3 = 5 , and so on.

2. **Check small values of k k :**
- For k=1 k = 1 , the product of the first 1 1 prime is p1=2 p_1 = 2 , and 2 2 is divisible by 1 1 . Hence, 1 1 is interesting.
- For k=2 k = 2 , the product of the first 2 2 primes is p1p2=23=6 p_1 \cdot p_2 = 2 \cdot 3 = 6 , and 6 6 is divisible by 2 2 . Hence, 2 2 is interesting.
- For k=3 k = 3 , the product of the first 3 3 primes is p1p2p3=235=30 p_1 \cdot p_2 \cdot p_3 = 2 \cdot 3 \cdot 5 = 30 , and 30 30 is divisible by 3 3 . Hence, 3 3 is interesting.
- For k=4 k = 4 , the product of the first 4 4 primes is p1p2p3p4=2357=210 p_1 \cdot p_2 \cdot p_3 \cdot p_4 = 2 \cdot 3 \cdot 5 \cdot 7 = 210 , and 210 210 is not divisible by 4 4 . Hence, 4 4 is not interesting.

3. Generalize the observation:
- For k=5 k = 5 , the product of the first 5 5 primes is p1p2p3p4p5=235711=2310 p_1 \cdot p_2 \cdot p_3 \cdot p_4 \cdot p_5 = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 = 2310 , and 2310 2310 is divisible by 5 5 . Hence, 5 5 is interesting.
- For k=6 k = 6 , the product of the first 6 6 primes is p1p2p3p4p5p6=23571113=30030 p_1 \cdot p_2 \cdot p_3 \cdot p_4 \cdot p_5 \cdot p_6 = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 = 30030 , and 30030 30030 is divisible by 6 6 . Hence, 6 6 is interesting.
- For k=7 k = 7 , the product of the first 7 7 primes is p1p2p3p4p5p6p7=2357111317=510510 p_1 \cdot p_2 \cdot p_3 \cdot p_4 \cdot p_5 \cdot p_6 \cdot p_7 = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 = 510510 , and 510510 510510 is divisible by 7 7 . Hence, 7 7 is interesting.
- For k=8 k = 8 , the product of the first 8 8 primes is p1p2p3p4p5p6p7p8=235711131719=9699690 p_1 \cdot p_2 \cdot p_3 \cdot p_4 \cdot p_5 \cdot p_6 \cdot p_7 \cdot p_8 = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 = 9699690 , and 9699690 9699690 is not divisible by 8 8 . Hence, 8 8 is not interesting.

4. Conclusion:
From the above steps, we observe that the maximal number of consecutive interesting integers is 7 7 .

The final answer is 7 \boxed{ 7 } .

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.