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

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?

• @DietrichBurde important is "no other prime" – Yurii Savchuk Mar 1 '18 at 14:33
• @DietrichBurde yes I already solved that part. – mandella Mar 1 '18 at 14:34

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

• @mandella Yes. You can first fix $k$ (or $m$ or $n$). With a fixed $k$, say $k=2$, then $2^m3^n\le 40$. The problem reduces to the case of only $2$ and $3$ as prime factors. – CY Aries Mar 1 '18 at 14:57
• For the original problem, the numbers are $2$, $3$, $4$, $6$, $8$, $9$, $12$, $16$, $18$, $24$, $27$, $32$, $36$, $48$, $54$, $64$, $72$, $81$, $96$, $108$, $128$, $144$, $162$, $192$, $216$, $243$, $256$, $288$, $324$, $384$, $432$, $486$, $512$, $576$, $648$, $729$, $768$, $864$, $972$. – CY Aries Mar 1 '18 at 14:59
• For the new problem, the numbers are $2$, $3$, $4$, $5$, $6$, $8$, $9$, $10$, $12$, $15$, $16$, $18$, $20$, $24$, $25$, $27$, $30$, $32$, $36$, $40$, $45$, $48$, $50$, $54$, $60$, $64$, $72$, $75$, $80$, $81$, $90$, $96$, $100$, $108$, $120$, $125$, $128$, $135$, $144$, $150$, $160$, $162$, $180$, $192$, $200$, $216$, $225$, $240$, $243$, $250$, $256$, $270$, $288$, $300$, $320$, $324$, $360$, $375$, $384$, $400$, $405$, $432$, $450$, $480$, $486$, $500$, $512$, $540$, $576$, $600$, $625$, $640$, $648$, $675$, $720$, $729$, $750$, $768$, $800$, $810$, $864$, $900$, $960$, $972$, $1000$ – CY Aries Mar 1 '18 at 15:01
• $m$ and $n$ cannot be both zero ($2^03^0=1$ is neither divisible by $2$ nor $3$). But one of them can be zero. For example, both $2^33^0=8$ and $2^03^4=81$ are solutions. – CY Aries Mar 1 '18 at 15:38
• If we want to find "numbers divisible by $2$ or $3$ and no other prime", then we should not include $1$ as $1$ is not divisible by $2$ and is also not divisible by $3$. If you want to find "numbers which are not divisible by any prime other than $2$ and $3$, then $1$ should be included. – CY Aries Mar 4 '18 at 13:35

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

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

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,...\}$$