SHARE
TWEET

Concatenation Inequality Proof

faubiguy May 24th, 2017 (edited) 90 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. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top