Divisors

Relevant wiki: Number of Factors

Let $d(x)$ be the number of divisors of a number $x$ . You only need to look one more instance further to see that $d\left(n^n\right)$ is not a strictly increasing function:

$\displaystyle \begin{aligned} d\left(5^5\right) = 6 < 9 = d\left(4^4\right) \end{aligned}$

Recall that the number of divisors of a number $N$ with prime factorization

$\displaystyle \begin{aligned} p_1^{{\color{#3D99F6}{q_1}}}p_2^{{\color{#3D99F6}{q_2}}}p_3^{{\color{#3D99F6}{q_3}}}\cdots p_k^{{\color{#3D99F6}{q_k}}} \end{aligned}$

is equal to $\left({\color{#3D99F6}{q_1}} + 1\right)\left({\color{#3D99F6}{q_2}} + 1\right)\left({\color{#3D99F6}{q_3}} + 1\right)\cdots \left({\color{#3D99F6}{q_k}} + 1\right)$ .

For any prime $p$ raised to itself $p^p$ , it will have $p + 1$ divisors, so for increasing values of $p$ , $d\left(p^p\right)$ is an increasing function. Analogously, it is elementary that $y = x + 1$ is strictly increasing for all $x$ (although their domains are technically different: one continuous, the other discrete).

$\displaystyle \begin{array} {|c|c|} \hline \text{Number} & \text{Number of divisors}\\\hline 2^{\color{#3D99F6}{2}} & {\color{#3D99F6}{2}} + 1 = 3\\\hline 3^{\color{#3D99F6}{3}} & {\color{#3D99F6}{3}} + 1 = 4\\\hline 5^{\color{#3D99F6}{5}} & {\color{#3D99F6}{5}} + 1 = 6\\\hline 7^{\color{#3D99F6}{7}} & {\color{#3D99F6}{7}} + 1 = 8\\\hline 11^{{\color{#3D99F6}{11}}} & {\color{#3D99F6}{11}} + 1 = 12\\\hline 13^{{\color{#3D99F6}{13}}} & {\color{#3D99F6}{13}} + 1 = 14\\\hline 17^{{\color{#3D99F6}{17}}} & {\color{#3D99F6}{17}} + 1 = 18\\\hline\end{array}$

This is not the case, however, for numbers $n^n$ where $n$ is composite.

Take, for instance, $4^4$ :

$\displaystyle \begin{aligned} 4^4 & = 2^8 \\ \implies d\left(4^4\right) & = 8 + 1 = 9 \end{aligned}$

Now look at the rest of the numbers $n^n$ for composite $n$ :

$\displaystyle \begin{array} {|c|c|} \hline \text{Number} & \text{Number of divisors}\\\hline 4^4 = 2^{\color{#3D99F6}{8}} & {\color{#3D99F6}{8}} + 1 = 9\\\hline 6^6 = 2^{\color{#3D99F6}{6}} \cdot 3^{\color{#20A900}{6}} & ({\color{#3D99F6}{6}} + 1)({\color{#20A900}{6}} + 1) = 49\\\hline 8^8 = 2^{{\color{#3D99F6}{24}}} & {\color{#3D99F6}{24}} + 1 = 25\\\hline 9^9 = 3^{{\color{#3D99F6}{18}}} & {\color{#3D99F6}{18}} + 1 = 19\\\hline 10^{10} = 2^{{\color{#3D99F6}{10}}} \cdot 5^{{\color{#20A900}{10}}} & ({\color{#3D99F6}{10}} + 1)({\color{#20A900}{10}} + 1) = 121\\\hline 12^{12} = 2^{{\color{#3D99F6}{24}}} \cdot 3^{{\color{#20A900}{12}}} & ({\color{#3D99F6}{24}} + 1)({\color{#20A900}{12}} + 1) = 325\\\hline 14^{14} = 2^{{\color{#3D99F6}{14}}} \cdot 7^{{\color{#20A900}{14}}} & ({\color{#3D99F6}{14}} + 1)({\color{#20A900}{14}} + 1) = 225\\\hline \end{array}$

We conclude that although $d(p^p)$ is strictly increasing for all primes $p$ , $d(n^n)$ is not a strictly increasing function for positive integers $n$ .