How to find number of integers not divisible by 2 nor 3 in a range?

Question

I'm trying to come up with a formula to find the number of numbers in a range that are neither divisible by 2 nor 3. For example between 20 and 30 their are 3, namely 23, 25 and 29.

I had the formula $f(a, b)=b−⌊b/2⌋−⌊b/3⌋+⌊b/6⌋- a-⌊a/2⌋+⌊a/3⌋-⌊a/6⌋$ where $a<b$ but it doesn't always work. For example for $a=5,b=10$ it gives 1 but should give 2 (because 5 and 7 are in the range of 5 to 10). The formula should be inclusive of $a$ and $b$ in the sense they are counted if they are not divisible by 2 or 3.

I don't mind if it's a piecewise function.

Answer 1

The formula

$$f(a,b)=\left(b-\left\lfloor b\over2\right\rfloor-\left\lfloor b\over3\right\rfloor+\left\lfloor b\over6\right\rfloor \right) -\left((a-1)-\left\lfloor a-1\over2\right\rfloor-\left\lfloor a-1\over3\right\rfloor+\left\lfloor a-1\over6\right\rfloor \right)$$

will do the trick: The first piece counts the number of positive integers up to (and including) $b$ not divisible by $2$ or $3$; the second piece subtracts those that are. (strictly) less than $a$.

As someone noted in a now-deleted comment, there can be no formula for $f$ that is purely a function of $b-a$, since, for example, $f(22,31)\not=f(21,30)$ even though $31-22=30-21$.

Added later: Here's another, arguably simpler formula.

$$f(a,b)=\left(\left\lceil b\over6\right\rceil+\left\lfloor b+1\over6\right\rfloor\right)-\left(\left\lfloor a\over6\right\rfloor+\left\lceil a-1\over6\right\rceil\right)$$

Where the floor function $\lfloor x\rfloor$ rounds down to the nearest integer and the ceiling function $\lceil x\rceil$ rounds up. The idea is to round $a$ down to the nearest multiple of $6$ and $b$ up to the nearest multiple of $6$, say $A=6\lfloor a/6\rfloor$ and $B=6\rceil b/6\rceil$. There are $2(B-A)/6=2(\lceil b/6\rceil-\lfloor a/6\rfloor)$ numbers between $A$ and $B$ not divisible by $2$ or $3$. But this includes $A+1$ and $B-1$, which shouldn't be counted if $A+1\lt a$ and/or $B-1\gt b$, so it's necessary to subtract $\lceil(a-A-1)/6\rceil$ and $\lceil(B-1-b)/6\rceil$. When you simplify the expression

$$2\left(\left\lceil b\over6\right\rceil-\left\lfloor a\over6\right\rfloor\right)-\left(\left\lceil{a-1\over6}-\left\lfloor a\over6\right\rfloor \right\rceil+\left\lceil\left\lceil b\over6\right\rceil-{b+1\over6} \right\rceil \right)$$

using the fact that integer quantities move additively outside the ceiling function and $-\lceil-x\rceil=\lfloor x\rfloor$, you get the given formula.

Answer 2

When $b-a \gt 0$ and $6 \mid (b-a+1)$ you can use this equation,

$\quad f(a,b)=b-a + 1 -\bigg\lfloor\frac{b-a+1}{2}\bigg\rfloor-\bigg\lfloor\frac{b-a+1}{3}\bigg\rfloor+\bigg\lfloor\frac{b-a+1}{6}\bigg\rfloor$

Note that $f(20,30) = 4$, which is incorrect.

Answer 3

6q +1 is such a number,6q+2 is not, 6q+3is not,6q+4 is not ,6q +5 is ,6q is not.

if u can break the range in sets each containg 6 elements with q constant , each set give 2 desired numbers.

for extremeties which can't be broken in such a way check them out yourself (can't be more than 10 numbers which u will have to check).

Answer 4

The perfect solution will be $$ $$ $$f(a,b)=(b-[\frac{b}{2}]-[\frac{b}{3}]+[\frac{b}{6}])-((a-1)-[\frac{a-1}{2}]-[\frac{a-1}{3}]+[\frac{a-1}{6}])$$ Where [ ] is greatest integer function.