1
$\begingroup$

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?

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

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

$\endgroup$
  • 1
    $\begingroup$ @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. $\endgroup$ – CY Aries Mar 1 '18 at 14:57
  • 1
    $\begingroup$ 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$. $\endgroup$ – CY Aries Mar 1 '18 at 14:59
  • 1
    $\begingroup$ 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$ $\endgroup$ – CY Aries Mar 1 '18 at 15:01
  • 1
    $\begingroup$ $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. $\endgroup$ – CY Aries Mar 1 '18 at 15:38
  • 1
    $\begingroup$ 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. $\endgroup$ – CY Aries Mar 4 '18 at 13:35
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

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