 Concatenation Inequality Proof

May 24th, 2017
153
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. Proof that the concatenation (as decimal strings) of two positive a and b is
2. necessarily greater than the lowest prime which is greater than their sum
3.
4. Formula for concatenation = a*10^(floor(log10(b))+1) + b
5. Exclusive upper bound for prime (by Bertrand's Postulate) = 2*a + 2*b - 2
6.
7. We assume that the concatenation is less than the upper bound for the prime and
8. derive a contradiction, proving that it must be greater or equal.
9.
10. a*10^(floor(log10(b))+1) + b < 2*a + 2*b - 2 Initial assumption
11. a*10*10^floor(log10(b)) + b < 2*a + 2*b - 2 Factor 10 out of power
12. a*10 + b < 2*a + 2*b - 2 1 < 10^floor(log10(b)), therefore it may be substituted
13. a*8 + 2 < b Subtract 2*a + b
14.
15. a*10^(floor(log10(b))+1) + b < 2*a + 2*b - 2 Initial assumption
16. a*10^log10(b) + b < 2*a + 2*b - 2 log10(b) < floor(log10(b)) + 1, therefore it may be substituted
17. a*b + b < 2*a + 2*b - 2 Simplify left-hand side
18. (a+1)*b < 2*a + 2*b - 2 Factor left-hand side
19. (a-1)*b < 2*a - 2 Substract 2*b
20. (a-1)*b < (a-1)*2 Factor right-hand side
21. (a-1)*(b-2) < 0 Subtract (a-1)*2
22. (a>1 and b<2) || (a<1 && b>2) Possibilities for factors
23. a>1 and b<2 Eliminate right possiblility because a ≥ 1
24. a>1 and b=1 1 ≤ b < 2 implies b = 1
25. a*8 + 2 < 1 Substitute b = 1 into last step above
26. 10 < 1 1 ≤ a, therefore it may be substituted
27.
28. This is a contradiction, therefore the assumed inequality must be false, and
29. the concatenation must be greater than the prime.
30.
31. Note that while Bertrand's Postulate as used above only applies to a + b > 3
32. it is trivial to verify that the result holds for the remaining cases:
33. a = 1, b = 1, 11 > 3
34. a = 1, b = 2, 12 > 5
35. a = 2, b = 1, 21 > 5
36.
37. Context: https://codegolf.stackexchange.com/questions/122582/find-all-number-relations
RAW Paste Data