Maths Olympiad Prep

Library / /249 of 520

Number theory Difficulty 6.9 National olympiad Prove it

For any positive integer nn, let w(n)w\left(n\right) denote the number of different prime divisors of the number nn. (For instance, w(12)=2w\left(12\right)=2.) Show that there exist infinitely many positive integers nn such that w(n)<w(n+1)<w(n+2)w\left(n\right)<w\left(n+1\right)<w\left(n+2\right).

Solution

1. We need to show that there exist infinitely many positive integers n n such that w(n)<w(n+1)<w(n+2) w(n) < w(n+1) < w(n+2) . Here, w(n) w(n) denotes the number of different prime divisors of n n .

2. Consider the sequence 2k,2k+1,2k+2 2^k, 2^k+1, 2^k+2 . We will show that for sufficiently large k k , this sequence satisfies w(2k)<w(2k+1)<w(2k+2) w(2^k) < w(2^k+1) < w(2^k+2) .

3. First, note that 2k 2^k has only one prime divisor, which is 2. Therefore, w(2k)=1 w(2^k) = 1 .

4. Next, consider 2k+1 2^k + 1 . For large k k , 2k+1 2^k + 1 is not a power of 2 and is not divisible by 2. Therefore, it must have at least one prime divisor other than 2. Hence, w(2k+1)2 w(2^k + 1) \geq 2 .

5. Now, consider 2k+2=2(2k1+1) 2^k + 2 = 2(2^{k-1} + 1) . Since 2k1+1 2^{k-1} + 1 is odd, it must have at least one prime divisor other than 2. Therefore, w(2k+2)2 w(2^k + 2) \geq 2 .

6. To ensure w(2k+2)>w(2k+1) w(2^k + 2) > w(2^k + 1) , we need to show that 2k1+1 2^{k-1} + 1 has at least one prime divisor that 2k+1 2^k + 1 does not have. For sufficiently large k k , this is generally true because the distribution of prime numbers ensures that 2k1+1 2^{k-1} + 1 and 2k+1 2^k + 1 will have different sets of prime divisors.

7. Therefore, for sufficiently large k k , we have:
w(2k)=1,w(2k+1)2,andw(2k+2)>w(2k+1) w(2^k) = 1, \quad w(2^k + 1) \geq 2, \quad \text{and} \quad w(2^k + 2) > w(2^k + 1)
This implies:
w(2k)<w(2k+1)<w(2k+2) w(2^k) < w(2^k + 1) < w(2^k + 2)

8. Since k k can be chosen to be arbitrarily large, there are infinitely many such k k that satisfy the condition.

\blacksquare

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.