Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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

3 Answers 3

up vote 6 down vote accepted

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

share|improve this answer
    
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$.

share|improve this answer
    
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)) $$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.