Vtgyjfy

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?

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$, $mge1$ and $2^mle1000$. So $1le mle 9$.

If $n=1$, $2^mlefrac{1000}{3}$. So $0le mle 8$.

If $n=2$, $2^mlefrac{1000}{9}$. So $0le mle 6$.

If $n=3$, $2^mlefrac{1000}{27}$. So $0le mle 5$.

If $n=4$, $2^mlefrac{1000}{81}$. So $0le mle 3$.

If $n=5$, $2^mlefrac{1000}{243}$. So $0le mle 2$.

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

If $n=7$, $2^mlefrac{1000}{2187}$, which is impossible.

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

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 $aleq9, bleq6$. You can do case-by-case work:

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

$2)$ $a=1$. You get $3^bleq500$, hence $6$ solutions

$3)$ $a=2Longrightarrow6$ solutions

$4)$ $a=3Longrightarrow5$ solutions

$5)$ $a=4Longrightarrow4$ solutions

$6)$ $a=5Longrightarrow4$ solutions

$7)$ $a=6Longrightarrow3$ solutions

$8)$ $a=7Longrightarrow2$ solutions

$9)$ $a=8Longrightarrow2$ solutions

$10)$ $a=9Longrightarrow1$ solution

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

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^3times 3^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,...} $$