Proving that this function has the same value for all integers $\geq4$. [duplicate]

Solution 1:

There is no way to prove $f(5)=9$.

Say $x+y=5$ and $x<y$ then $x<4$ and you can't use $f(5)=f(xy)$.
Say $xy=5$ then $x=1$ and $y=5$ (or vice versa) and now you can't use $f(5)=f(6)$.

So we are stuck with $f(5)$. We have the same problem with $f(6)$ and $f(7)$.

Perhaps for all $n\geq 8$ we can say $f(n)=9$

Solution 2:

We have no way to access $f(4)$, $f(5)$, $f(6)$, or $f(7)$ using only the information present.

(Due to time constraints, this is only a partial answer. I invite anyone else to finish it or skewer it for hasty thinking.)

However, we can track our progress of understanding using points on the plane. Let $n \geq 8$ and consider the line $y = n-x$ for $4 \leq x \leq n - 4$. On this line, $f(x+y) = f(n)$, so the function is constant on each of these lines (but still potentially has different values on different lines). (Note that we only speak of the points with integer coordinates on this line, but perhaps we draw a continuous line so we can more clearly visualize which points we have shown produce equal values in $f$.)

Now let $m \geq 16$ and consider the part of the hyperbola $y = \frac{m}{x}$ with $x \geq 4, y \geq 4$. From $f(xy) = f(m)$, we see that $f$ is constant on each of these hyperbolae.

From these two facts, we see that each line, $L$, $f$ is constant and $f$ is forced to be the same constant value on every hyperbola intersecting $L$ at an integer point. Symmetrically, each hyperbola forces the lines it integrally intersects to share its constant value for $f$.

These observations allow an inductive see-saw. For any point, follow its line to the point with $y=4$. Then follow that hyperbola to the point of minimum $|x - y|$. This sequence of points at the end of the hyperbola move must move closer to the origin. So we have a strictly decreasing bounded sequence of distances from the origin. This means such a path from any point eventually lands on the $n=8$ line.

(Last thought: The case $y=4$, $m$ prime, makes me think we should actually take the minimum over all possible hyperbola moves from a line. Maybe I'm being overcautious.)

Solution 3:

If $n\geq 16$ has a factorization as $p_{1}^{r_{1}}p_{2}^{r_{2}}\cdots p_{k}^{r_{k}},$ where the $p_{k}$ are distinct primes and the $r_{k}\geq 1,$ then if there is some $p_{i}^{r_{i}}\geq 4$ such that $p_{i}^{-r_{i}}n\geq4,$ we may obtain $f(n)=f(p_{i}^{r_{i}}+p_{i}^{-r_{i}}n)$, and by so doing obtain some $8\leq m<n$ for which $f(m)=f(n)$ (note that $a<ab/2$ whenever $b>4$, and $b\leq ab/2$ whenever $a\geq 4,$ so $a+b<ab$ whenever $a\geq 4$ and $b>4,$ and $f(16)=f(4+4)=f(8)).$ Note also that if $p_{i}\geq 5$ for some $i,$ and $p_{i}^{-1}n\geq 4,$ we have $f(n)=f(p_{i}+p_{i}^{-1}n),$ and thus again we have $f(n)=f(m)$ for some $8\leq m<n.$ This also works if $6|n,$ and $n/6\geq 4$, in which case $f(n)=f(6+n/6),$ which also gives $f(n)=f(m)$ for some $8\leq m<n.$ Then the cases we need to consider are $n\geq 16$ of the form $2p$, $p\geq 5;$ $3p,$ $p\geq 5;$ $18;$ and $p$, where $p\geq 17$.

• $f(2p)=f(2(p-2)+4)=f(8(p-2))=f(p+6),$ and $p+6<2p$ whenever $6<p;$ but $2p>16$ only when $p>8,$ so this holds.

• $f(3p)=f(3(p-2)+6)=f(18(p-2))=f(p+16),$ and $p+16<3p$ whenever $16<2p$, or $8<p$; but $3p>16$ implies that $p\geq 7,$ so the only case to cover is $n=21,$ where we have $f(21)=f(4+17)=f(68)=f(5+63)=f(315)=f(21\cdot 15)=f(36)=f(4+9)=f(13).$

• $f(18)=f(12+6)=f(72)=f(9+8)=f(17).$

• $f(p)=f(p-8+8)=f(8(p-8))=f(4+2(p-8))=f(2p-12)=f(2(p-6)).$ Note that a prime number strictly smaller than $p$ must divide $p-6,$ and that this cannot be $2$ or $3$ (since this would mean $p$ is divisible by $2$ or $3$, respectively). But since this prime $q$ must be $\leq\sqrt{p-6},$ $2(p-6)/q\geq 2\sqrt{p-6}\geq 2\sqrt{10}\geq 6,$ and thus $f(2(p-6))=f(q+2(p-6)/q).$ We need to show that $q+2(p-6)/q<p$, but this is the case if and only if $q^{2}+2(p-6)<pq,$ if and only if $q\in[(p-\sqrt{p^2-8p+48})/2,(p+\sqrt{p^2-8p+48})/2]$. Note that $p\geq 17,$ so $0\leq 8/p-48/p^{2}\leq 8/p<1/2$, and that $e^{-(3/2)x}\leq 1-x$ for all $0\leq x\leq 1/2.$ Then \begin{align*}\frac{1}{2}(p-\sqrt{p^{2}-8p+48})&=\frac{p}{2}(1-\sqrt{1-8/p+48/p^{2}})\\&\leq\frac{p}{2}(1-\sqrt{e^{-(3/2)(8/p-48/p^{2})}})\\&=\frac{p}{2}(1-e^{-(3/4)(8/p(1-6/p))})\\&=\frac{p}{2}(1-e^{-6/p(1-6/p)}),\end{align*} which has a Taylor approximation which we bound with the term-by-term absolute value, and then use the fact that $|1-6/p|\leq 1$, to get \begin{align*}\frac{p}{2}\sum_{k=1}^{\infty}\frac{(-1)^{k+1}}{k!}\left(\frac{6}{p}\left(1-\frac{6}{p}\right)\right)^{k}&\leq\frac{p}{2}\sum_{k=1}^{\infty}\frac{1}{k!}\left(\frac{6}{p}\right)^{k}=\sum_{k=1}^{\infty}\frac{3}{k(k-1)!}\left(\frac{6}{p}\right)^{k-1}\\&\leq\sum_{k=1}^{\infty}\frac{3}{(k-1)!}\left(\frac{6}{p}\right)^{k-1}\leq 3e^{6/p}\\&\leq 3e^{6/17}<4.5,\end{align*} so we know that $q$ is greater than this lower bound already, since $q\geq 5.$ Similarly, $\frac{p}{2}(1+\sqrt{1-8/p+48/p^{2}})\geq \frac{p}{2}(1+e^{-6/p(1-6/p)})\geq \frac{p}{2}\geq\sqrt{p-6}$, the last bound holding if and only if $p^{2}\geq 4p-24,$ which is true whenever $p\geq 4,$ which is certainly true. But we already know that $q\leq\sqrt{p-6},$ which proves that $q+2(p-6)/q<p.$

This reduces the problem to showing that the numbers $n=9,10,\ldots,15$ all satisfy $f(n)=f(8).$ Since $9$ and $10$ have already been shown, this leaves $n=11,12,13,14,$ and $15.$

• $f(11)=f(5+6)=f(30)=f(10+3)=f(13).$
• $f(12)=f(6+6)=f(36)=f(4+9)=f(13)=f(8+5)=f(40)=f(4+10)=f(14)$ $f(15)=f(50)=f(25+25)=f(625)=f(600+25)=f(1500)=f(115)=f(23+5)=f(28)=f(7+4)=f(11)$
• $f(13)=f(7+6)=f(42)=f(10+32)=f(320)=f(80+4)=f(84)=f(21+4)=f(25)=f(10)$

This completes the proof.