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

Question

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 2^52.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.

Rewire

It depends on what floating-point support is provided by the underlying platform that hosts the Python implementation. Python itself does not define any particular floating-point behavior. – Classicize

@Classicize Using IEEE-754, as tagged. 64 bits. As probably used by almost (?) everyone's Python. (Ok maybe there are still some configuration possibilities that one could set, at least the rounding mode, but probably almost nobody does that. I do believe this to be identical for pretty much everybody.) – Rewire

@Classicize Answer saying it's IEEE 754 binary64 practically everywhere (by someone very involved in the subject). – Rewire

@KellyBundy: Please keep in mind that practically everywhere is not everywhere, and both nation-states and well-funded criminals are eager to exploit any weakness they can find. This makes the mentality that we can mostly neglect rare situations very dangerous. Even if it does not matter particularly in this question, it should be avoided as a habitual way of thinking. – Its

@EricPostpischil I don't apply that "mentality" everywhere. Plus it was mainly a quick counterpoint to chepner's comment, which in my opinion made it sound far worse than it is, as if we practically couldn't say anything about this and couldn't learn anything from this. Also, in this case, I'm really not in any danger from those states/criminals, since I'm never going to use 1/i like that. I was just curious and wanted to learn (and share) something about floats. Then again, I might use the gained knowledge elsewhere. Not being applicable everywhere doesn't mean it's not useful anywhere. – Rewire

Answer 1

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.

Brott

With n=52 it matches i's range, but I think it also does with n=51 and n=53, no? The latter is too large to be interesting, but what about n=51? – Rewire

@KellyBundy Substituting n=51 gives the minimal i as 2^52, which does not fall between 2^n and 2^(n+1). – Brott

But it does. 2^52 does fall within 2^51 and 2^52. Especially since the "approximately" actually means it's slightly smaller than 2^52, so it falls within that range even if you mean the upper bound as an exclusive one. – Rewire

@KellyBundy It's only very slightly (less than 1) below 2^52. So the first relevant integer is 2^52, which is a single edge case that can be quickly ruled out. Any larger integers don't fall in the range so we need to switch to n=52. – Brott

Ok, yes, that fills that hole. Could you mention it in the answer? – Rewire