$d(n)$ shows the number of positive integer divisors of positive integer $n$. For which positive integers $n$ one cannot find a positive integer $k$ such that $\underbrace{d(\dots d(d}_{k\ \text{times}} (n) \dots )$ is a perfect square.
Problem
Source: 2021 Turkey JBMO TST 2021 P5
Tags: number theory, number theory proposed, function
24.05.2021 09:33
Answer: If $n$ can be represented as $p^{q-1}$ where $p$ and $q$ are prime numbers, then we can't find such $k$. Proof: We will prove this by induction. Check for $n=1,2,3,4$. The key is to see if $n>2$, then $2\leq d(n)<n$. Suppose for $n=1,2,\cdots,m-1$. Let's prove for $n=m$. We have $2\leq d(m)<m$. So, if $d(m)$ can not be represented as $p^{q-1}$ where $p$ and $q$ are prime numbers, then there exist a positive integer $k_0$ such that $\underbrace{d(\dots d(d}_{k_0\ \text{times}} (d(m))) \dots )$ is perfect square. Then, $\underbrace{d(\dots d(d}_{k_0+1\ \text{times}} (m)) \dots )$ is a perfect square too. Assume $d(m)=p^{q-1}$ where $p$ and $q$ are prime numbers. If $q>2$, then $q-1$ is even. Hence, $d(m)=p^{q-1}$ is a perfect square. If $q=2$, then let's say $m=r_1^{\alpha_1}\cdot r_2^{\alpha_2}\cdot r_s^{\alpha_s}$ where $\alpha_i\ge 1$. We have $d(m)=(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_s+1)=p^{q-1}=p$. Since $\alpha_i+1\ge 2$, we can get $s=1$ and $\alpha_1=p-1$. So $m=r_1^{p-1}$ where $r_1$ and $p$ are prime numbers. Clearly the numbers in the form $p^{q-1}$ satisfy the condition since $d(p^{q-1})=q, d(q)=2, d(2)=2$. This completes the proof.
24.05.2021 16:16
I think we can compress above by working backwards. Clearly, $d(n)<n$ for all $n\ge 3$. To see this, simply divide all divisors $d$ of $n$ into pairs $(d,n/d)$ and note that $\min\{d,n/d\}\le \sqrt{n}$ hence $d(n) \le 2\sqrt{n}<n$ for $n>4$ whereas $d(n)<n$ for $n\in\{3,4\}$ via direct computation. Assume next $n$ is not of form $p^{q-1}$, $p,q$ primes. In particular, for any fixed $n$, $d^{(k)}(n)$ strictly decreases till we hit 2. Now, fix any $n\in\mathbb{N}$, and let $k$ be the first time that $d^{(k)}(n)=2$. Then $d^{(k-1)}(n)=q$ for some prime $q>2$, and $d^{(k-2)}(n)=p^{q-1}$. At this point, we are done: since $n$ is not of form, we deduce $d^{(k-2)}(n)$ is a perfect square (and clearly $k\ge 3$, since $n$ is not of aforementioned form).