Maths Olympiad Prep

Library / /14 of 19

Number theory Difficulty 8.2 Shortlist Find the answer

To every natural number k,k2k, k \geq 2, there corresponds a sequence an(k)a_n(k) according to the following rule:
a0=k,an=τ(an1)n1,a_0 = k, \qquad a_n = \tau(a_{n-1}) \quad \forall n \geq 1,
in which τ(a)\tau(a) is the number of different divisors of aa. Find all kk for which the sequence an(k)a_n(k) does not contain the square of an integer.

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

Solution

Given the problem, we need to find all natural numbers k2 k \geq 2 for which the sequence an(k) a_n(k) defined as follows does not contain the square of an integer:
a0=k,an=τ(an1)n1, a_0 = k, \qquad a_n = \tau(a_{n-1}) \quad \forall n \geq 1,
where τ(a)\tau(a) denotes the number of positive divisors of the integer a a .

### Understanding τ(a)\tau(a)

The function τ(a)\tau(a) counts the number of divisors of a a . For any integer a a , if a a has a prime factorization of the form:
a=p1e1p2e2pmem, a = p_1^{e_1} p_2^{e_2} \cdots p_m^{e_m},
then the number of divisors τ(a)\tau(a) is given by:
τ(a)=(e1+1)(e2+1)(em+1). \tau(a) = (e_1 + 1)(e_2 + 1) \cdots (e_m + 1).

### Objective

We seek values of k k for which the sequence never contains a perfect square (a number of the form n2 n^2 ).

### Analysis
1. **Base Case (kk is a Prime):**
- If k k is a prime, then τ(k)=2 \tau(k) = 2 because a prime number has exactly two divisors: 1 and itself.
- Therefore, the sequence becomes:
a0=k,a1=2,a2=τ(2)=2,a3=τ(2)=2, a_0 = k, \quad a_1 = 2, \quad a_2 = \tau(2) = 2, \quad a_3 = \tau(2) = 2, \ldots
- Since 2 2 is not a perfect square, the sequence does not contain any perfect square for any prime k k .

2. **Non-prime kk:**
- If k k is composite, then τ(k)3\tau(k) \geq 3. At some point in the sequence, it may stabilize at a value τ \tau which could be a perfect square.
- In particular, consider powers of 2. If an=2b a_n = 2^b for b2 b \geq 2 , then τ(2b)=b+1\tau(2^b) = b + 1.
- Assess the divisibility properties and possible stabilization at perfect squares under various composite k k scenarios. This analysis quickly becomes complex, but instances will either reduce or stabilize to perfect squares at some n n .

### Conclusion

Through this exploration, it becomes evident that the sequence an(k) a_n(k) avoids containing a perfect square only when k k is a prime. This is due to the rapid stabilization of the sequence at the non-perfect square number 2 2 .

Hence, the sequence an(k) a_n(k) does not contain the square of an integer if and only if k k is a prime number.

Thus, the final answer is:
iff k is a prime \boxed{\text{iff } k \text{ is a prime}}

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.