Difference between revisions of "Sum Product Conjecture"

Latest revision as of 09:47, 12 June 2020

[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$

@@ Line 13: / Line 13: @@
 [color=#f00][b]Lemma.[/b][/color] For all <math>k\geq 4</math>, <math>\tfrac{81}4k^2<10^{k-1}</math>.
-[i]Proof.[/i] Proceed by induction.  The case <math>k=4</math> can be computed by hand, since <math>\tfrac{81}4\cdot 4^2 = 324 < 1000</math>.  For the inductive step, write
+[i]Proof by djmathman:[/i] Proceed by induction.  The case <math>k=4</math> can be computed by hand, since <math>\tfrac{81}4\cdot 4^2 = 324 < 1000</math>.  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,

Page

Toolbox

Search

Difference between revisions of "Sum Product Conjecture"

Latest revision as of 09:47, 12 June 2020