Smallest i with 1/i == 1/(i+1)?

user_12671057 0
Viewed 109

Someone reverse-sorted by 1/i instead of the usual -i and it made me wonder: What is the smallest positive integer case where that fails*? I think it must be where two consecutive integers i and i+1 have the same reciprocal float. The smallest I found is i = 6369051721119404:

i = 6369051721119404
print(1/i == 1/(i+1))

import math
print(math.log2(i))

Output (Try it online!):

True
52.50000001100726

Note that it's only a bit larger than 252.5 (which I only noticed after finding the number with other ways) and 52 is the mantissa bits stored by float, so maybe that is meaningful.

So: What is the smallest where it fails? Is it the one I found? And is there a meaningful explanation for why?

* Meaning it fails to sort correctly, for example sorted([6369051721119404, 6369051721119405], key=lambda i: 1/i) doesn't reverse that list, as both key values are the same.

floating-accuracy ieee-754 precision floating-point python
1 Answers

Suppose i is between 2^n and 2^(n+1) for some n.

Then 1/i is between 2^(-n-1) and 2^-n. Its representation as double-precision floating point is 1.xxx...xxx * 2^(-n-1), where there are 52 x's. The smallest difference that can be expressed at that magnitude is 2^-52 * 2^(-n-1) = 2^(-n-53).

1/i and 1/(i+1) may get rounded to the same number if the difference between them is at most 2^(-n-53). Solving for i: 1/i - 1/(i+1) = 2^(-n-53) ==> i(i+1) = 2^(n+53). The solution is approximately i = 2^((n+53) / 2). This matches our range for i if n = 52. Then i = 2^52.5.

Starting at this value of i there is a possibility to get the same value for 1/i and 1/(i+1). But it won't happen for every i as it depends on how the numbers are rounded. We can start searching at that point, and as you discovered shortly after that we'll find the first occurrence.

Note: We also need to rule out n=51 as it seems to have solutions that fall in range. However, the only integer i that falls in the range 2^51 to 2^52 and is at least the minimal value calculated above is 2^52 itself, which can be ruled out. For larger values we need to switch to n=52 as above.

user_1892050
Related