# Test whether an interval contains integer points

I want to make a non-complex (for algorithmic implementation) logical condition to test whether some real interval contains any integer points.

Let $x$ be an interval with bounds $l, r$;

Let $LI(x)$ be a predicate that holds if $x$'s left boundary is inclusive and $RI(x)$ be a predicate that holds if $x$'s right boundary is inclusive.

Finally, let $P(x)$ be a predicate which holds if $x$ does contain at least one integer point.

Here's what I have produced so far:

$P(x) \equiv (\lfloor l \rfloor + 1 < r) \lor (RI(x) \land (r \in \mathbb Z) ) \lor (LI(x) \land (l \in \mathbb Z))$

Is this insufficient or superfluous? Can anyone make up a better formula? Thank you!

-
You don't need the $|x| \gt 1$ clause, as the next will take care of that case – Ross Millikan May 23 '11 at 21:32
Yes indeed, thank you. – wh1t3cat1k May 23 '11 at 21:35

Edit: fixing condition for the open set using proposal in comments.

Given that the interval $x$ is not empty, the open interval $(l,r)$ contains an integer if and only if:

$$\lfloor l \rfloor + 2 \leq \lceil r \rceil$$

Otherwise, the only way for an integer to be in the interval is if one of the boundaries is closed, and that value is an integer. That is:

$$(LI(x) \land \lfloor l \rfloor = l) \lor (RI(x) \land \lceil r \rceil=r)$$

I use floor and ceiling here just to be cute - so we only need to compute $\lceil r \rceil$ and $\lfloor l \rfloor$.

So the full expression is: $$(\lfloor l \rfloor + 2 \leq \lceil r \rceil) \lor$$ $$(LI(x) \land \lfloor l \rfloor = l) \lor$$ $$(RI(x) \land \lceil r \rceil=r)$$

If you need the condition that $x$ is not empty, then $\land$ the above expression with $$l\lt r \lor (l = r \land LI(x) \land RI(x))$$

-
There's a problem with the open interval condition you lead off with. Nonempty open interval $(1,2)$ does not contain an integer, but the ceiling of 1 is strictly less than the floor of 2. – hardmath May 24 '11 at 1:28
@amWhy - no, @hardmath is correct, I missed this edge case – Thomas Andrews May 24 '11 at 1:50
@hardmath: sorry 'bout that, hardmath: I didn't ready YOUR comment carefully! I'll delete my earlier comment. @Thomas: Thanks, for clarifying... – amWhy May 24 '11 at 1:54
Here's a proposed fix. It may strike one as counterintuitive since it relies on floor of $l$ and ceiling of $r$. The open interval $(l,r)$ contains an integer if and only $l \lt r$ and $( \lceil r \rceil - \lfloor l \rfloor ) \geq 2$. – hardmath May 24 '11 at 11:45
@hardmath: Is $l<r$ redundant here? – Thomas Andrews May 24 '11 at 14:25

I would go with $$P = (|x|>1) \vee(\lceil l\rceil \leq r \wedge LI) \vee (l \leq \lfloor r\rfloor \wedge RI)$$ Checking $|x|>1$ first, that is, $r-l>1$, is quite a good idea for when implementing this as an algorithm, chances are this condition will be true most of the time anyway, and with a good branch prediction the algorithm only costs one subtraction and one comparison, which makes it very fast.

The only trouble is it doesn't work for $x=\,].9,1.1[$... you need one extra logical summand, $$P = (|x|>1) \vee (LI \wedge \lceil l\rceil \leq r) \vee (RI \wedge l \leq \lfloor r\rfloor ) \vee (\lceil r\rceil - \lfloor l\rfloor =2)$$ ok, now it's longer that your original proposal... not so nice. It should still be faster as an algorithm, though.

$LI \wedge \lceil l\rceil \leq r$ means: if the left border value is inclusive, it's sufficient to know if the number next to the right side of $l$ is in the interval, that is, to know that this number is not further to the right than $r$.

-
Could you please explain what the second and the third clauses mean? – wh1t3cat1k May 23 '11 at 22:18

$$(\lfloor l(x) \rfloor \neq \lfloor r(x) \rfloor) \vee (LI(x) \wedge \lfloor l(x) \rfloor = l(x)) \vee (RI(x) \wedge \lfloor r(x) \rfloor = r(x))$$

-