Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Proof that the concatenation (as decimal strings) of two positive a and b is
- necessarily greater than the lowest prime which is greater than their sum
- Formula for concatenation = a*10^(floor(log10(b))+1) + b
- Exclusive upper bound for prime (by Bertrand's Postulate) = 2*a + 2*b - 2
- We assume that the concatenation is less than the upper bound for the prime and
- derive a contradiction, proving that it must be greater or equal.
- a*10^(floor(log10(b))+1) + b < 2*a + 2*b - 2 Initial assumption
- a*10*10^floor(log10(b)) + b < 2*a + 2*b - 2 Factor 10 out of power
- a*10 + b < 2*a + 2*b - 2 1 < 10^floor(log10(b)), therefore it may be substituted
- a*8 + 2 < b Subtract 2*a + b
- a*10^(floor(log10(b))+1) + b < 2*a + 2*b - 2 Initial assumption
- a*10^log10(b) + b < 2*a + 2*b - 2 log10(b) < floor(log10(b)) + 1, therefore it may be substituted
- a*b + b < 2*a + 2*b - 2 Simplify left-hand side
- (a+1)*b < 2*a + 2*b - 2 Factor left-hand side
- (a-1)*b < 2*a - 2 Substract 2*b
- (a-1)*b < (a-1)*2 Factor right-hand side
- (a-1)*(b-2) < 0 Subtract (a-1)*2
- (a>1 and b<2) || (a<1 && b>2) Possibilities for factors
- a>1 and b<2 Eliminate right possiblility because a ≥ 1
- a>1 and b=1 1 ≤ b < 2 implies b = 1
- a*8 + 2 < 1 Substitute b = 1 into last step above
- 10 < 1 1 ≤ a, therefore it may be substituted
- This is a contradiction, therefore the assumed inequality must be false, and
- the concatenation must be greater than the prime.
- Note that while Bertrand's Postulate as used above only applies to a + b > 3
- it is trivial to verify that the result holds for the remaining cases:
- a = 1, b = 1, 11 > 3
- a = 1, b = 2, 12 > 5
- a = 2, b = 1, 21 > 5
- Context: https://codegolf.stackexchange.com/questions/122582/find-all-number-relations
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
