# Behavior of integer recurrence $u_0\geq 2$, $u_{n+1}=d(u_n)^\alpha$, for $\alpha \geq 3$, where $d$ is the number-of-divisors function

Let $$u_0\ge 2$$ and $$\alpha\ge 1$$ integers.

I'm trying to study the sequence $$(u_n)_{n\ge 0}$$ defined by : $$\forall n\ge 0,\quad u_{n+1}=d(u_n)^{\alpha},$$ where $$d$$ is the number-of-divisors function.

If $$\alpha=1$$, it's not hard to prove that $$\lim\limits_{n\rightarrow +\infty}u_n=2,$$ And if $$\alpha=2$$ we also have : $$\lim\limits_{n\rightarrow +\infty} u_n=9.$$ However, if $$\alpha\ge 3$$, the sequence doesn't always converge.

For example, when $$\alpha=3$$, if $$u_0=2$$, then for $$n\ge 1$$, $$u_{2n}=2^6$$ and $$u_{2n+1}=7^3$$.

Do we have more results about the behaviour of the sequence $$(u_n)_{n\ge 0}$$ when $$\alpha\ge 3$$ ?

$$\textit{Edit 2 -}$$ After many simulations, I have the following conjecture :

$$\boxed{\textbf{Conjecture -} \text{ For all \alpha\ge 1, the sequence (u_n)_{n\ge 0} is eventually periodic.}}$$

When $$\alpha=4$$, the sequence always seems to converge, but the limit depends on $$u_0$$ (for $$u_0=2$$ the limit is $$625$$ and for $$u_0=6$$ the limit is $$6561$$).

For example, when $$\alpha=5$$, if $$u_0=2$$, then the sequence converges to $$3^52^5$$, but if $$u_0=2^53^511^{10}$$, then the sequence is $$2$$-periodic (with $$u_1=2^{10}3^{10}11^{5}$$).

We can easily prove that :

$$\boxed{\text{For all \alpha\ge 1, there are infinitelty many numbers such that (u_n)_{n\ge 0} converges.}}$$

Indeed, if $$u_0=p_1...p_l$$ is a squarefree integer, then : $$u_1=2^{\alpha l}$$ and $$u_2=(\alpha l+1)^{\alpha}.$$ By Dirichlet's theorem on arithmetic progressions, there are infinitely many integers $$l\ge 1$$ such that $$\alpha l+1$$ is a prime number. If we choose a such integer $$l\ge 1$$, then for all $$n\ge 2$$ : $$u_n=(\alpha l+1)^{\alpha},$$ and the sequence $$(u_n)_{n\ge 0}$$ converges. $$\blacksquare$$

• Does it being equivalent to modifying the number of divisors in a specific weird way count. Even if predictable ? – Roddy MacPhee Aug 3 at 2:18
• Since $\tau(n)$ grows slower than any power of $n$, the sequence will eventually converge to a limit point or a limit cycle for any fixed $\alpha$. Infinite growth is impossible, that much we can be sure of. – Ivan Neretin Aug 3 at 13:38

I'll show that the conjecture that the sequence will end up periodic (or converge which just means of period $$1$$).

Let's first express the sequence in terms of $$v_n=d(u_n)$$ so that $$v_{n+1}=d(v_n^\alpha)$$.

I'll start off by proving that, for any integer $$\alpha>0$$, there is at most a finite number of positive integers $$v$$ for which $$d(v^\alpha)\ge v$$, and then use this to prove that the sequence must eventually be periodic.

Prime factorise $$v=p_1^{m_1}\cdots p_k^{m_k}$$. Then, $$d(v^\alpha) = (\alpha m_1+1)\cdots(\alpha m_k+1)$$. So, I wish to prove that for $$v$$ sufficiently large, $$d(v^\alpha)/v<1$$. We can write this fraction as $$\frac{d(v^\alpha)}{v}=\prod_{i=1}^k \frac{\alpha m_i+1}{p_i^{m_i}}.$$ For any given prime number $$p$$, the largest value of $$(\alpha m+1)/p^m$$ is $$(\alpha+1)/p$$ if $$p\le\alpha$$ (corresponding to $$m=1$$), and $$1$$ for $$p>\alpha$$ (corresponding to $$m=0$$). This gives us an upper bound $$d(v^\alpha)/v\le A$$ where $$A=\prod_{\text{prime } p\le\alpha} (\alpha+1)/p$$. Since picking $$m_i$$ which maximise $$d(v^\alpha)/v$$ makes it at most $$A$$, if there is any term with $$(\alpha m_i+1)/p_i^{m_i}<1/A$$, that will make $$d(v^\alpha)/v<1$$. However, for any prime $$p$$, the restriction that $$(\alpha m+1)/p^m\ge 1/A$$ places an upper bound $$m\le M(p)$$, as well as an upper bound $$p\le 2A$$ om primes for which $$m\ge 1$$.

So, to summarise, in order to get $$d(v^\alpha)/v\ge1$$, we must have $$v=\prod p_i^{m_i}$$ where $$p_i$$ are prime numbers $$\le A/2$$ and $$m_i\le M(p_i)$$. There are only a finite number of such numbers. Thus, we can conclude that for all but a finite number of $$v$$, we have $$d(v^\alpha). Since there is only a finite number of $$v$$ with $$d(v^\alpha)\ge v$$, these must have an upper bound $$W\ge d(v^\alpha)\ge v$$. We can therefore conclude that the sequence $$v_n$$ will eventually drop and stay below $$W$$ which means it must eventually become periodic.

Have corrected the explanation of the upper bound $$W$$. Hope the rest should be correct.

For $$\alpha = 49,$$ we can find $$u_0 = \left(2^53^45^{10}11^2\right)^\alpha$$ yields a $$20$$-periodic sequence.

Specifically, $$u_n^{1/\alpha}$$ for $$0\leq n\leq 20$$ is $$\begin{array}{c|c} n & u_n^{1/\alpha} \\ \hline 0 & 2^5\times 3^4\times 5^{10}\times 11^2 \\ 1 & 2\times 3^3\times 11\times 41\times 197\times 491 \\ 2 & 2^7\times 5^{10}\times 37 \\ 3 & 2^4\times 5^2\times 43\times 491 \\ 4 & 2^2\times 3^2\times 5^4\times 11\times 197 \\ 5 & 2^2 \times 3^4 \times 5^4 \times 11^2 \times 197 \\ 6 & 2 \times 3^4 \times 5^2 \times 11^2 \times 197^2 \\ 7 & 2 \times 3^6 \times 5^2 \times 11^3 \times 197 \\ 8 & 2^4 \times 3^2 \times 5^5 \times 11 \times 37 \times 59 \\ 9 & 2^4 \times 3^3 \times 5^6 \times 11 \times 41 \times 197 \\ 10 & 2^5 \times 5^7 \times 37 \times 59 \times 197 \\ 11 & 2^7 \times 3 \times 5^6 \times 41 \times 43 \\ 12 & 2^6 \times 5^7 \times 43 \times 59 \\ 13 & 2^5 \times 5^5 \times 43 \times 59 \\ 14 & 2^4 \times 3^2 \times 5^4 \times 41^2 \\ 15 & 3^4 \times 11^2 \times 197^2 \\ 16 & 3^4 \times 11^2 \times 197 \\ 17 & 2 \times 3^2 \times 5^2 \times 11 \times 197 \\ 18 & 2^3 \times 3^4 \times 5^6 \times 11^2 \\ 19 & 2^2 \times 3^2 \times 5 \times 11 \times 37 \times 59 \times 197 \\ 20 & 2^5\times 3^4\times 5^{10}\times 11^2 \end{array}$$

It still might be interesting to consider the relationship between $$\alpha$$ and the possible periods, but I don't think there's an upper bound on the period that is independent of $$\alpha$$ itself.

• Thanks ! How did you find such values of $u_0$ and $\alpha$ ? Do you have a particular method or was it by chance ? – Mishikumo2019 Aug 10 at 9:17
• For $\alpha$, I just chose one such that $\alpha+1, 2\alpha+1, 3\alpha+1$ are "fairly" composite, since the more composite they are, the greater chance to have larger exponents. I wasn't aware $u_n^{1/\alpha}$ was going to have prime powers as high as $10$ until I started, so there perhaps is some degree of luck there. I wouldn't know without trying other values. – Brian Moehring Aug 10 at 13:13
• As for $u_0$? I actually chose a less exotic-looking initial value (i.e. one of $2, 4, 6$---can't remember which) and then just ran the sequence until the sizes of exponents in the prime factorization seemed to stabilize. Only then did I start writing down the sequence. Since this means I might have run through the entire period once already, the earliest might not have even been my eventual choice of $u_0,$ but it really matter which element you choose inside the period itself. – Brian Moehring Aug 10 at 13:19