41
$\begingroup$

It's my observation.

Let $$n=p_1×p_2×p_3×\dots×p_r$$ where $p_i$ are prime factors and $f$ and $g$ are the functions $$f(n)=1+2+\dots+n$$ And $$g(n)=p_1+p_2+\dots+p_r$$ If we put $n=21$ then $$g(f(21))=g(231)=21.$$ I checked it upto $n=10000$, I did not find another number with this property $g(f(n))=n$.

Can we prove that other such numbers do not exist?

$\endgroup$
6
  • $\begingroup$ To clarify, is $g(12)=5$ or $=7$? $\endgroup$ Commented Mar 1, 2019 at 7:22
  • $\begingroup$ 12=3*2*2 then g(12)=2+2+3=7 $\endgroup$
    – Pruthviraj
    Commented Mar 1, 2019 at 7:35
  • 2
    $\begingroup$ @PruthvirajHajari Did you come up with this problem by yourself? If so, please state that in your question and include the program code used to run it. $\endgroup$
    – TheSimpliFire
    Commented Mar 1, 2019 at 7:47
  • $\begingroup$ I encourage you to accept my answer by clicking the tick you see beside it. $\endgroup$ Commented Mar 1, 2019 at 13:37
  • 1
    $\begingroup$ @PruthvirajHajari sure it is. $\endgroup$ Commented Mar 1, 2019 at 14:01

1 Answer 1

54
$\begingroup$

This is a very interesting question…

$\newcommand{sopfr}{\operatorname{sopfr}}$ $f(n)=\frac{n(n+1)}2$ and $g(n)=\sopfr(n)$, the sum of prime factors of $n$ with repeats (OEIS A001414). We want $n$ such that $g(f(n))=n$ or $$\sopfr\left(\frac{n(n+1)}2\right)=n\tag1$$ which can be split into two cases due to the property $\sopfr(ab)=\sopfr(a)+\sopfr(b)$.

  • If $n$ is even, then $\sopfr\left(\frac n2\right)+\sopfr(n+1)=n$. We know that $\sopfr(n)\le n$, so $\sopfr\left(\frac n2\right)\le\frac n2$ and consequently $\sopfr(n+1)\ge\frac n2$. Either $n+1$ is a prime, in which case the LHS of $(1)$ is greater than $n$ and so the equality cannot hold, or $n+1$ is odd composite and so has a least prime factor at least 3*, yielding $\sopfr(n+1)\le3+\frac{n+1}3$ and thus $$\frac n2\le3+\frac{n+1}3$$ which is only true for $n\le20$. Checking those $n$ reveals no solutions to $(1)$.
  • If $n$ is odd, the reasoning is similar: $\sopfr\left(\frac{n+1}2\right)+\sopfr(n)=n$, where $\sopfr\left(\frac{n+1}2\right)\le\frac{n+1}2$ and so $\sopfr(n)\ge\frac{n-1}2$. Since $n$ is odd, either it is prime and the LHS of $(1)$ is greater than $n$, or it has a least prime factor at least 3* and $\sopfr(n)\le3+\frac n3$, giving $$\frac{n-1}2\le3+\frac n3$$ which only holds for $n\le21$. 21 is the solution to $(1)$ pointed out in the original question; we have just shown it is the only one.

*Technically we have to repeat the argument for other possible least prime factors $k$ of $n$ or $n+1$ – and the upper bound $N_k$ of the solution to the inequalities in $n$ increases accordingly, each 3 replaced with $k$. However, the least composite number with least prime factor $k$ is $k^2$, and this increases much faster than $N_k$ (which is $\sim\frac k2$). Indeed, $5^2$ already exceeds $N_5$ for both inequalities.

The method I use above has very strong similarities to the method I used in my most famous answer of all. It is sheer coincidence that 21 is a solution to both the problems I answered.

$\endgroup$
1
  • 1
    $\begingroup$ To elaborate on the footnote: If $n$ is composite and $p$ its minimal prime factor, then $\operatorname{sopfr}(n)=p+\operatorname{sopfr}(n/p)\le p+\frac np$ and $x\mapsto x+\frac nx$ is a decreasing function on $(0,\sqrt n)$, hence $n$ odd and composite implies $\operatorname{sopfr}(n)\le 3+\frac n3$. $\endgroup$ Commented Mar 1, 2019 at 15:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .