Let $k -$ positive integer, $k \ge2$. The sequence $a_n(k)$ such that $$a_0(k)=k, a_n(k)=\tau\left(a_{n-1}(k)\right),$$ for $n\ge1$, where $\tau(a) -$ the number different divisors of the number $a$.

Find all $k$, such that the sequence $a_n(k)$ does not contain squares of positive integers.

My work so far:

If $a=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot...\cdot p_n^{\alpha_n}$ then $$\tau(a)=(\alpha_1+1)(\alpha_2+1)\cdot...\cdot(\alpha_n+1)$$

Let $k=2$ $$a_1=2, a_2=2,a_3=2,...$$ Hence, $a_n(2) -$ satisfies.

Let $k=6$ $$a_1=6, a_2=4=\color{red}{2^2}, $$ Hence, $a_n(6) -$ not satisfies.


Those $k$ are precisely the prime numbers.

Because $2\leq\tau(n)<n$ for $n\geq3$, every sequence eventually reaches $2$, from which point it is constant.
Let $k$ be given and suppose $n$ is the smallest index with $a_n=2$. Suppose $n\geq2$.
Then $a_{n-1}$ has $2$ divisors, and is thus prime.
Then $a_{n-2}$ is a prime power with exponent $a_{n-1}-1$. But by the minimality of $n$, $a_{n-1}\neq2$ so $a_{n-1}$ is odd, which means $a_{n-2}$ is a square.

This reason is invalid if $n\leq1$, i.e. if it takes at most $1$ step to reach $2$, which is the case if and only if $k$ is prime.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.