1
$\begingroup$

For integers $m\geq 1$ let $\sigma(m)$ the sum of divisors function $\sum_{1\leq d\mid m}d$ and let $\psi(m)$ the Dedekind psi function (as reference I add the Wikipedia Dedekind psi function), then there exist integers $n\geq 1$ that satisfy $$\psi(\sigma(n))=2n.\tag{1}$$ I don't know it this equation is in the literature, compare this equation with the equation studied in the second page of [1] (or well from the last paragraph of the article Totient Function from the encyclopedia Wolfram MathWorld).

Up to $10^4$ these solutions are $n=2,3,4,16,64$ and $4096$. I believe that this sequence isn't in the OEIS, I've searched also the string psi(sigma(n)). It is easy to prove the following statement.

Claim. If $2^{\alpha+1}-1$ is a Mersenne prime, then $n=2^{\alpha}$ is a solution of the equation $(1)$.

Question. I would like to know if it is possible to do more work about the solutions of the equation $$\psi(\sigma(n))=2n.$$ What additional and reasonable* work can be done about it? Many thanks.

*I'm asking about if we can deduce more statements about the solutions (characterization of solutions and if there exist finitely/infinitely many solutions) of $(1)$.

Remarks. The functions $\sigma(n)$ and $\psi(n)$ are multuiplicative. It is unknown if there exist infinitely many Mersenne primes. As a side remark the integer $n=3$ also is a solution, for which $2n-1=5\in$A175611 from the OEIS.

References:

[1] L. Alaoglu and P. Erdös, A conjecture in elementary number theory, Bull. Amer. Math. Soc. Volume 50, Number 12 (1944), 881-882.

$\endgroup$
  • 2
    $\begingroup$ Why A175611 is relevant? $\endgroup$ – Max Alekseyev Nov 22 '19 at 15:33
  • $\begingroup$ Many thanks for your attention @MaxAlekseyev It is a side comment because I don't know what is the relationship between the equation $\psi(\sigma(n))=2n$ and the sequences A175611 versus A000668 (Mersenne primes) from the OEIS. See the Claim. $\endgroup$ – user142929 Nov 22 '19 at 15:47
  • $\begingroup$ All, I was inspired to state previous Claim for the equation $\psi(\sigma(n))=2n$ after I've known the comments for the sequence A001229 from the OEIS. $\endgroup$ – user142929 Nov 22 '19 at 16:40
3
+50
$\begingroup$

There are no other solutions than $n=3$ and those from Claim: $n=2^{p-1}$ such that $2^p-1$ is prime.

Consider several cases.

  1. $n=2^ks$ is even (here $k\geqslant 1$ and $s$ is odd). Then $$\frac{\psi(\sigma(n))}{n}=\frac{\psi((2^{k+1}-1)\sigma(s))}{(2^{k+1}-1)\sigma(s)}\cdot \frac{2^{k+1}-1}{2^k}\cdot \frac{\sigma(s)}s.\quad(1)$$ Note that $$\frac{\psi(ab)}{ab}=\prod_{p|ab}\left(1+\frac1p\right)\geqslant \prod_{p|a}\left(1+\frac1p\right)=\frac{\psi(a)}a$$ for positive integers $a,b$, therefore $$ \frac{\psi((2^{k+1}-1)\sigma(s))}{(2^{k+1}-1)\sigma(s)}\geqslant \frac{\psi(2^{k+1}-1)}{2^{k+1}-1}\geqslant \frac{2^{k+1}}{2^{k+1}-1},\quad (2) $$ the last inequality holds due to $k\geqslant 1$ and turns into equality if and only if $2^{k+1}-1$ is a Mersenne prime. Substitute (2) to (1), we get $$ \frac{\psi(\sigma(n))}{n}\geqslant \frac{2^{k+1}}{2^{k+1}-1}\cdot \frac{2^{k+1}-1}{2^k}\cdot \frac{\sigma(s)}s=2\frac{\sigma(s)}s\geqslant 2, $$ with equality if and only if $s=1$ and $2^{k+1}-1$ is a Mersenne prime. So for even $n$ all solutions come from Claim.

  2. $n$ is odd. Denote $\sigma(n)=p_1^{\alpha_1}\ldots p_m^{\alpha_m}$. Then $2n=\psi(\sigma(n))=(p_1^{\alpha_1}+p_1^{\alpha_1-1})\ldots (p_m^{\alpha_m}+p_m^{\alpha_m-1})$. Note that $p_i^{\alpha_i}+p_i^{\alpha_i-1}$ is even unless $p_i^{\alpha_i}=2$. But $2n$ is not divisible by 4, therefore either

(i) $m=1$ and $\sigma(n)=p^{\alpha}$; or

(ii) $m=2$ and $\sigma(n)=2p^{\alpha-1}$ for odd $p$.

In the case (i) we get $n=\frac{p+1}2 p^{\alpha-1}$. If $p=2$, then since $n$ should be odd we get $\alpha=2$, $n=3$. It is a solution. If $p$ is odd and $\alpha\geqslant 2$, then $p^\alpha=\sigma(n)=\sigma(\frac{p+1}2)\sigma(p^{\alpha-1})$, but $\sigma(p^{\alpha-1})$ is greater than 1 and not dividible by $p$. If $\alpha=1$, we get $\sigma(\frac{p+1}2)=p$. Then $n=\frac{p+1}2=q^s$ for a prime $q$ (otherwise $\sigma(\frac{p+1}2)$ is composite), $q$ is odd (since $q|n$) and $$2q^s-1=p=\sigma(n)=q^s+q^{s-1}+\ldots+1$$ that fails modulo $q$.

In the case (ii) we get $n=3\frac{p+1}2p^{\alpha-1}$ and $$\sigma(n)\geqslant n+\frac{n}3=2(p+1)p^{\alpha-1}>2p^\alpha,$$ a contradiction.

$\endgroup$
  • $\begingroup$ Many thanks I've understand all details. While I know that the theorems that great mathematicians, you and your colleagues of this MO, prove are more difficult and abstract than my question, let me tell you that I was impressed for your proof. I would like to dedicate thus your theorem to your excellence and the excellence of your colleagues. $\endgroup$ – user142929 Dec 1 '19 at 13:02
  • $\begingroup$ How are you getting that $2n=\psi(\sigma(n))=(p_1^{\alpha_1}+p_1^{\alpha_1-1})\ldots (p_m^{\alpha_m}+p_m^{\alpha_m-1})$? $\endgroup$ – JoshuaZ Dec 1 '19 at 13:46
  • 1
    $\begingroup$ @JoshuaZ $2n=\psi(\sigma(n))$ is given, then use the formula for $\psi(m)=m\prod_{p|m} (1+1/p)$ for $m=\sigma(n)$. $\endgroup$ – Fedor Petrov Dec 1 '19 at 14:55

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.