Sum Product Conjecture

[size=500][center]The Sum Product Conjecture[/center][/size]

Step 1: Pick a number $n$. Step 2: Let $S(n)$ be the sum of the digits of $n$. Step 3: Find the solution to $a+b=S(n)$ such that $a, b \geq 0$ and $|a-b|$ is as close to $0$ as possible. Now your number is $ab$.

Repeat.

[b]The Sum-Product Conjecture[/b] states that you will eventually end up at 0 or 4. [list] [*][b]Claim 1:[/b] Going through all these steps, you will eventually end up at a one-digit integer. First, we prove that we will eventually reach a number with less than four digits, and then we will prove the for a number less than or equal to 4 digits, that it will eventually reach a previous case and onto the 1 digit cases, which is proved below. [color=#f00][b]Lemma.[/b][/color] For all $k\geq 4$, $\tfrac{81}4k^2<10^{k-1}$.

[i]Proof by djmathman:[/i] Proceed by induction. The case $k=4$ can be computed by hand, since $\tfrac{81}4\cdot 4^2 = 324 < 1000$. For the inductive step, write \[ \tfrac{81}4(k+1)^2 = \tfrac{81}4k^2\cdot(\tfrac{k+1}k)^2 \stackrel{\textrm{(IH)}}<10^{k-1}\cdot 2^2\leq 10^k, \] where in the second-to-last equality we use the fact that $\tfrac{k+1}k = 1 + \tfrac 1k\leq 2$ for all positive integers $k$.

To proceed, observe now that, by the AM-GM inequality, \[ ab\leq \left(\frac{a+b}2\right)^2= \frac{S(n)^2}4. \] We now split into cases. [list] [*][b]Case 1.[/b] If $n$ has two digits, then $S(n)\leq 18$, so in accordance with your notation $\tfrac{S(n)^2}4\leq 81$. Using this value as our new value of $n$, we get $S(n)\leq S(79) = 16$, so $ab\leq 64$; then $S(n)\leq S(59) = 14$, so $ab\leq 49$; then $S(n)\leq S(49) = 13$, so $ab\leq 43$; then $S(n)\leq S(39) = 12$, so $ab\leq 36$; then $S(n)\leq S(29) = 11$, so $ab\leq 31$.

Unfortunately, we can't press on using this logic anymore, so we need to brute-force this part: [list] [*] For $n = 11,12,13,14,15,20,21,22,23,24,30,31$, $S(n)$ is at most $6$, so $ab\leq 9$ is a single-digit integer. [*] For $n=16,25$, $S(n) = 7$, so $ab = 12$. Then we're in the previous case. [*] For $n=17,26$, $S(n) = 8$, so $ab = 16$. Then we're in the previous case. [*] For $n=18,27$, $S(n) = 9$, so $ab = 20$. Then we're in the very first case. [*] For $n=19,28$, $S(n) = 10$, so $ab= 25$. Then we're in the second case. [*] For $n=29$, $S(n) = 11$, so $ab= 30$. Then we're in the very first case. [/list] [*][b]Case 2.[/b] Suppose $n$ has three digits. Then $S(n)\leq 27$, so $ab\leq \tfrac{27^2}4 \leq 183$. In turn, using $ab$ as our new value of $n$, $S(n)\leq S(179) = 17$, so $ab\leq \tfrac{17^2}4 \leq 73$. Now we're in Case 1. [*][b]Case 3.[/b] Finally, suppose $n$ has at least $4$ digits. Choose $k$ such that $10^{k-1}\leq n < 10^{k}$, noting that $k\geq 4$. Then $S(n)$ is at most $9k$ (when all $k$ digits are nines), and so \[ ab\leq \frac{S(n)^2}4 \leq \frac{(9k)^2}4 = \frac{81}4k^2 \stackrel{(*)}< 10^{k-1} \leq n. \][/list] This means that the process strictly decreases the value of $n$. Hence, after a finite number of iterations, our integer will have fewer than $4$ digits, which reduces the problem to one of the previous few cases. [*][b]Claim 2:[/b] If your number is a one-digit integer, then you will end up 0 or 4. [list] [*][b]Proof: The sum of the digits of one-digit integers is itself.[/b] [list] [*]Case 1: 1. We have $a+b=1$, so that $a=1$ and $b=0$ (symmetry, $b=1$ and $a=0$ is the same), so that $ab=0$. We have ended at 0, and we repeat, finding the $a=0$ and $b=0$, so that we end up at $0$ again. [*]Case 2: 2. We have that $a+b=2$, and $a=1$ and $b=1$, and $ab=1$. We already proved it for 1, so this is done [*]Case 3: 3. We have that $a+b=3$, so that $a=2, b=1$, $ab=2$, but we already proved it for 2, and we are done. [*]Case 4: 4. We have that $a+b=4$, so that $a=2, b=2$, and we end up at $4$ again. [*]Case 5: 5. We have that $a+b=5$, and $a=3, b=2$, so that $ab=6$. Now, we have $a+b=6$, $a=3, b=3$, so that $ab=9$. Now, we have $a+b=9$, $a=5, b=4$, and $ab=20$. $2+0=2$, we already proved it for 2, and we are done. This step also proves it for $6$ and $9$ because we went through 6 at one step. [*]Case 6: 6. We are done because of Case 5. [*]Case 7: 7. We have $a+b=7$, $a=3, b=4$, so that $ab=12$. Sum of digits is 3, and we already proved it for 3, so we are done. [*]Case 8: 8. We have that $a+b=8$, and $a=b=4$, so that $ab=16$. Sum of digits is $7$, but we already proved it for $7$, so we are done. [*]Case 9: 9. We are done because of Case 5. [/list] [/list] [/list] We have proved this claim. Q.E.D. $\blacksquare$