1
$\begingroup$

I have been solving basic counting problems from Kenneth Rosen's Discrete Mathematics textbook (6th edition). These come from section 5-1 (the basics of counting), pages 344 - 347.

This question is not specifically about finding an answer to a problem or being given the correct equation, but whether my reasoning is sound. Therefore I would find it hard to argue this is a duplicate of seemingly similar questions like this one or this one.

The problems I have been dealing with come of the form How many positive integers in range [x,y] are divisible by d? All additional questions are based on the composition of the information learned in these, e.g. how many positive integers in range [x,y] are divisible by d or e?

To answer the simple question I wrote this "equation/algorithm," which takes as input an inclusive range of positive integers $[x,y]$ and a positive integer $d$, and returns $n$, the total number of positive integers in range $[x,y]$ which are divisible by $d$.

(1) $n = \left \lfloor{\frac{y}{d}}\right \rfloor - \left \lfloor{\frac{x}{d}}\right \rfloor$

The idea is that in order to count how many positive integers are divisible by $d$ from $[1,m]$, we simply calculate $\left \lfloor{\frac{m}{d}}\right \rfloor$, because every $dth$ positive integer must be divisible by $d$. However, this does not work when given a range $[x,y]$ where $x \not= 1$ or when $x > 1$. So we need to subtract the extra integers we counted, which is $\left \lfloor{\frac{x}{d}}\right \rfloor$, i.e. the number of positive integers divisible by $d$ from $[1,x]$.

For a sanity check, I also wrote a brute force algorithm that does a linear search over every positive integer in the range $[x,y]$ and counts it if $x \text{ mod } d == 0$. It also can list out the integers it picked, in case I am feeling really paranoid.

With (1) I've been getting the correct answers except on this problem/input: How many positive integers between 100 and 999 inclusive are odd? My solution was to calculate how many are even, and subtract this from the total number of positive integers in range $[100,999]$. To find the evens I simply use the algorithm in (1):

$\left \lfloor{\frac{999}{2}}\right \rfloor - \left \lfloor{\frac{100}{2}}\right \rfloor = 499 - 50 = 449$

But this answer is wrong, since there actually $450$ even numbers in range $[100,999]$ by the brute force algorithm. (1) is somehow counting off by 1. My question is, why is (1) failing for this input of $(2, [100,999])$ but so far it's worked on every other input? What do I need to do to fix (1) so it produces the correct answer for this case? Perhaps I'm actually over counting because $x$ should actually be $x - 1$?

(1') $n = \left \lfloor{\frac{y}{d}}\right \rfloor - \left \lfloor{\frac{x - 1}{d}}\right \rfloor$

(1') returns the correct answer for this specific input now, but I am not sure if it will break my other solutions.

$\endgroup$
1
$\begingroup$

After computing the number of positive multiples of $d$ less than or equal to $y,$ you correctly want to subtract the multiples that are not actually in the range $[x,y].$ Those are the multiples that are less than $x.$ When $x$ is divisible by $d,$ then $\left\lfloor \frac xd \right\rfloor$ counts all multiples of $d$ up to and including $x$ itself. So as you surmised, you want to subtract $\left\lfloor \frac {x-1}d \right\rfloor$ instead. This is true for any divisor, not just $d=2.$

$\endgroup$
  • $\begingroup$ You have identified and explained the problem nicely. $\endgroup$ – Ross Millikan Sep 14 '14 at 2:38
0
$\begingroup$

another counterexample is [13,6] and 2. the formula seems to be off by 1 if d exactly divides x or (x and y) because then the # of integers in the range [a, b] = b - a + 1.

$\endgroup$
0
$\begingroup$

Suppose you have $$ (k-1)d<x\leq kd<(k+1)d<\ldots<(k+n)d\leq y<(k+n+1)d. $$ Then, you always have $\lfloor{\frac{y}{d}}\rfloor=k+n$ is $k+n$. On the other hand, if $x$ is divisible by $d$, then $\lfloor{\frac{x}{d}}\rfloor=k$, whereas if $x$ isn't divisible by $d$, then $\lfloor{\frac{x}{d}}\rfloor=k-1$. To rectify this, instead use $\lceil{\frac{x}{d}}\rceil$ which always returns $k$. Your solution is then $$ n+1=(n+k)-k+1=\color{blue}{\left\lfloor{\frac{y}{d}}\right\rfloor-\left\lceil{\frac{x}{d}}\right\rceil+1}. $$


p.s. $$ (k-1)d<x\leq kd\implies(k-1)d\leq x-1<kd\implies\left\lfloor{\frac{x-1}{d}}\right\rfloor=k-1 $$ so that $$ n+1=(n+k)-(k-1)=\color{red}{\left\lfloor{\frac{y}{d}}\right\rfloor-\left\lfloor{\frac{x-1}{d}}\right\rfloor}. $$ The formulas in blue and red produce the same answer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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