5
$\begingroup$

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!

  • 0
    You don't need the $|x| \gt 1$ clause, as the next will take care of that case2011-05-23
  • 0
    Yes indeed, thank you.2011-05-23

3 Answers 3

6

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))$$

  • 0
    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.2011-05-24
  • 0
    @amWhy - no, @hardmath is correct, I missed this edge case2011-05-24
  • 0
    @hardmath: sorry 'bout that, hardmath: I didn't ready YOUR comment carefully! I'll delete my earlier comment. @Thomas: Thanks, for clarifying...2011-05-24
  • 0
    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$.2011-05-24
  • 0
    @hardmath: Is $l redundant here?2011-05-24
  • 0
    Yes, it is redundant! You only need to retain it if you weaken the latter inequality to include the closed interval with integer endpoint cases (by disjunction).2011-05-24
2

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$.

  • 0
    Could you please explain what the second and the third clauses mean?2011-05-23
0

$$ (\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)) $$