Numbers up to 1000 divisible by 2 or 3 and no other prime

Question

My task requires to find all numbers from $1-1000$ such that they are divisible by $2$ or $3$ and no other primes. I know that $2$ divides even numbers and I can use the formula $\left \lfloor{\frac{1000}{2}}\right \rfloor $ and the numbers divisible by three $\left \lfloor{\frac{1000}{3}}\right \rfloor $. Also we rule out the numbers that are divisible by both, so by $6$ $\left \lfloor{\frac{1000}{6}}\right \rfloor $. In total we get that there are $500+333-166=667$ numbers divisible by $2$ or $3$. However I also need to make sure that I $\textit{only}$ count numbers divisible by either of these $2$. Is there a quick way to do it?

Answer 1

Such a number should be in the form of $2^m3^n$ where $m$ and $n$ are non-negative integers such that $m$ and $n$ are not both zero.

If $n=0$, $m\ge1$ and $2^m\le1000$. So $1\le m\le 9$.

If $n=1$, $2^m\le\frac{1000}{3}$. So $0\le m\le 8$.

If $n=2$, $2^m\le\frac{1000}{9}$. So $0\le m\le 6$.

If $n=3$, $2^m\le\frac{1000}{27}$. So $0\le m\le 5$.

If $n=4$, $2^m\le\frac{1000}{81}$. So $0\le m\le 3$.

If $n=5$, $2^m\le\frac{1000}{243}$. So $0\le m\le 2$.

If $n=6$, $2^m\le\frac{1000}{729}$. So $m= 0$.

If $n=7$, $2^m\le\frac{1000}{2187}$, which is impossible.

Number of possibilities is $9+9+7+6+4+3+1=39$.

Answer 2

You want numbers of the form $2^a3^b$ where $a,b \geq 0$ and not both are equal to $0$. Trivial check gives that $a\leq9, b\leq6$. You can do case-by-case work:

$1)$ $a=0$. You get $6$ possibilities for $6$ since $b\neq0$ in this case

$2)$ $a=1$. You get $3^b\leq500$, hence $6$ solutions

$3)$ $a=2\Longrightarrow6$ solutions

$4)$ $a=3\Longrightarrow5$ solutions

$5)$ $a=4\Longrightarrow4$ solutions

$6)$ $a=5\Longrightarrow4$ solutions

$7)$ $a=6\Longrightarrow3$ solutions

$8)$ $a=7\Longrightarrow2$ solutions

$9)$ $a=8\Longrightarrow2$ solutions

$10)$ $a=9\Longrightarrow1$ solution

Sum all those solutions and you are good to go! The answer is 39

Answer 3

did you notice that the numbers which are divisible by 2 or 3 but not other prime are just all powers of 2 (below 1000), all powers of 3 (below 1000) and any product of them (below 1000)? and they are very few of them... $2^9$ is the last power of 2 below 1000, $3^6$ is the last power of 3 below 1000, and the biggest combination of them is $2^3\times 3^4$.

Answer 4

Consider:

Step 1:

$$ S_0 = \{1,2,3,4\} $$ $$ A_0 = 2S_0 = \{2,4,6,8\} $$ $$ B_0 = 3S_0 = \{3,6,9,12\} $$

Step 2:

$$ S_1 = S_0 \cup A_0 \cup B_0 = \{1,2,3,4,6,8,9,12\} $$ $$ A_1 = 2S_1 = \{2,4,6,8,12,16,18,24\} $$ $$ B_1 = 3S_1 = \{3,6,9,12,18,24,27,36\} $$

Step 3:

$$ S_2 = S_1 \cup A_1 \cup B_1 = \{1,2,3,4,6,8,9,12,16,18,24,27,36\} $$ $$ A_2 = 2S_2 = \{2,4,6,8,12,16,18,24,32,36,48,54,72\} $$ $$ B_2 = 3S_2 = \{3,6,9,12,18,24,27,36,48,54,72,81,108\} $$

Step 4:

$$ S_3 = S_2 \cup A_2 \cup B_2 = \{1,2,3,4,6,8,9,12,16,18,24,27,32,36,48,54,72,81,108\} $$

And soo on...

$$ S = \{1\} \cup 2S \cup 3S $$

Other Algorithm:

$$ A_0 = \{1,2,4,8,16,32,64,128,256,512,...\} $$ $$ A_1 = 3A_0 = \{3,6,12,24,48,96,192,384,768,...\} $$ $$ A_2 = 3A_1 = \{9,18,36,72,144,288,576,...\} $$ $$ A_3 = 3A_2 = \{27,54,108,216,432,864,...\} $$ $$ A_4 = 3A_3 = \{81,162,324,648,...\} $$ $$ A_5 = 3A_4 = \{243,486,972,...\} $$ $$ A_6 = 3A_5 = \{729,...\} $$

Then:

$$ S = A_0 \cup A_1 \cup A_2 \cup A_3 \cup A_4 \cup A_5 \cup A_6 \cup {...} $$ $$ S = \{1,2,3,4,6,8,9,12,16,18,24,27,32,36,48,54,64,72,81,96,108,128,144,162,192,...\} $$