• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Concatenation Inequality Proof

faubiguy May 24th, 2017 (edited) 98 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Top