Let $a_0(n) = n$ and $a_{i+1}(n) = \varphi(a_i(n))$ for $i\geq 0$, where $\varphi(n)$ is Euler's totient function (the number of positive integers less than or equal to $n$ and coprime with $n$). Denote $f(n) = \prod_{k=0}^{\infty}a_k(n)$.

Determine all positive integers $n$ such that the sum of positive divisors of $f(n)$ is strictly greater than $2f(n)$.

  • $\begingroup$ No, the definition implies $\varphi(1) = 1$. $\endgroup$ Apr 2 '21 at 17:52
  • 1
    $\begingroup$ My first analysis of the question is that these $f(n)$ numbers are highly composite and most of them should be abundant numbers. I think the proof should just focus on the tail of the totient chain which should end with a series of powers of $2$ followed by "the product of some Fermat primes and a power of two ". If the Fermat primes are $3$ or $5$ then $f(n)$ should be divisible by $6$ or $20$ and this makes the number abundant. it remains to check other general Fermat primes and this probably would give proof that only powers of $2$ do not satisfy the abundance criteria $\endgroup$
    – Elaqqad
    Apr 4 '21 at 16:30

Let's observe that:
\begin{align*} a_0(n) &= n \,, \\ a_1(n) &= \varphi(n) \,, \\ a_2(n) &= \varphi(a_1(n)) = \varphi(\varphi(n)) = \varphi^{(2)}(n)\,, \\ ... \\ a_k(n) &= \varphi^{(k)}(n)\,, \end{align*} where $\varphi^{(k)}(n)$ is $k$ times composition of the totient function. This gives us the function $f(n)$ as \begin{align*} f(n) = n\prod_{k=1}^{\infty}\varphi^{(k)}(n) \,. \end{align*} Now it is intuitively clear why $\varphi^{(k+1)}(n)\leq\varphi^{(k)}(n)$; that is, we expect the totient function to decrease with each iteration (until it becomes $1$). This means that for a finite number $n$, we have a finite number of elements in the product of $f(n)$.

The problem asks us to find all numbers $n$ that give us $2f(n)<\sigma(f(n))$, where \begin{align*} \sigma(f(n)) = \sum_{d|f(n)}d\,, \end{align*} is called the divisor function and is the sum of all divisors of $f(n)$.

Numbers that satisfy $2f(n)<\sigma(f(n))$ are called abundant numbers. However, we are going to look for numbers $2f(n)>\sigma(f(n))$, where $n$ is referred to as deficient numbers. Deficient numbers contain all odd numbers with distinct primes and all even numbers that are powers of $2$. Why we choose to look at this case will become apparent soon.

The totient function can be written as \begin{align*} \varphi(n) = n\prod_{p|n}\bigg(\frac{p-1}{p}\bigg)\,, \end{align*} where $p|n$ means all primes that divide $n$. The only number that is even and prime is $2$. This means that numbers that are made up of primes greater than $2$ will always give $\varphi(n)$ as an even number. This means that for all $n>2$ we have that $f(n)$ will always be an even number so we do not need to worry about odd deficient numbers.

However, for $n = 2^{m}$ we have \begin{align*} \varphi(2^{m}) = 2^{m}\bigg(\frac{2-1}{2}\bigg) = 2^{m-1}\,. \end{align*}
Thus $f(2^{m})$ is \begin{align*} f(2^{m}) = 2^{m+(m-1)+(m-2)+...+1} = 2^{m(m+1)/2} \end{align*} and will be a deficient number because $f(2^{m})$ is a power of $2$ (as stated before).

We need to also exclude perfect numbers that satisfy $\sigma(f(n)) = 2f(n)$. We already worked out that $f(n)$ is always even and we do not need to worry about odd perfect numbers (still an open problem in number theory). Even perfect numbers are of the form $2^{p-1}(2^{p}-1)$, where $p$ is a prime and $2^{p}-1$ is also a prime (Mersenne prime). We need $n = 2^{p} - 1$ because this is the only term that is odd. Now if we apply the totient function $\varphi(n) = n - 1 = 2^{p}-2$ (because $n$ is prime and will be always coprime with all numbers up to itself), we expect $\varphi(n) = 2^{p-1}$ and this gives us the equation \begin{align*} 2^{p} - 2 &= 2^{p-1} \\ 2^{p-1} - 1 &= 2^{p-2} \,. \end{align*} The LHS is odd while RHS is even. So only $p = 2$ is valid and we get $n = 3$ and $f(3)$ will be a perfect number.

In conclusion, the numbers that do not satisfy the inequality are $3$ and $2^{m}:m\in\mathbb{N}$. Any other number satisfies the inequality.

  • 3
    $\begingroup$ +1, seems correct. But please do make it concise. You've dragged out the answer really long, a lot of trivial stuff can be omitted. $\endgroup$
    – Kaind
    Apr 2 '21 at 4:18
  • $\begingroup$ Thanks for the feedback, new around here and will keep it in mind. $\endgroup$
    – Schwauss
    Apr 2 '21 at 10:27
  • $\begingroup$ @Schwauss how do we know that for the case of even deficient numbers we need to consider only powers of 2? I was not able to find a corresponding reference. $\endgroup$ Apr 2 '21 at 17:58
  • 2
    $\begingroup$ @Schwauss But it says that all powers of two are deficient but not that all even deficient numbers are powers of two? $\endgroup$ Apr 3 '21 at 12:12
  • 2
    $\begingroup$ I don't think this answers the question $\endgroup$
    – Elaqqad
    Apr 4 '21 at 16: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.