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$
  • $\begingroup$ To clarify, is $g(12)=5$ or $=7$? $\endgroup$ – Hagen von Eitzen Mar 1 '19 at 7:22
  • $\begingroup$ 12=3*2*2 then g(12)=2+2+3=7 $\endgroup$ – Pruthviraj Mar 1 '19 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 Mar 1 '19 at 7:47
  • $\begingroup$ I encourage you to accept my answer by clicking the tick you see beside it. $\endgroup$ – Parcly Taxel Mar 1 '19 at 13:37
  • 1
    $\begingroup$ @PruthvirajHajari sure it is. $\endgroup$ – Parcly Taxel Mar 1 '19 at 14:01
53
$\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.

| cite | improve this answer | |
$\endgroup$
  • 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$ – Hagen von Eitzen Mar 1 '19 at 15:47

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.