3
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ Does it being equivalent to modifying the number of divisors in a specific weird way count. Even if predictable ? $\endgroup$ – Roddy MacPhee Aug 3 at 2:18
  • 1
    $\begingroup$ 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. $\endgroup$ – Ivan Neretin Aug 3 at 13:38
1
+50
$\begingroup$

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)<v$. 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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks ! How did you find such values of $u_0$ and $\alpha$ ? Do you have a particular method or was it by chance ? $\endgroup$ – Mishikumo2019 Aug 10 at 9:17
  • 1
    $\begingroup$ 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. $\endgroup$ – Brian Moehring Aug 10 at 13:13
  • 1
    $\begingroup$ 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. $\endgroup$ – Brian Moehring Aug 10 at 13:19

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.