faubiguy

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