1

A set of positive integers has the properties that

  • Every member in th set, apart form 1, is divisible by at least one of $2,3,$ or $5$.
  • If the set contains $2n, 3n,$ or $5n$ for some integer $n$, then it contains all three and $n$ as well.

The set contains between $300$ and $400$ numbers. Exactly how many does it contain?

I started with $\{1,2,3,5\}$, and tried to add some more numbers: say when $n=2$, we can add $2\times2=4, 3\times2=6, 5\times2=10$, it became $\{1,2,3,5,4,6,10\}$. Now we had $6=2\times3$, which $n=3$, we should add $3\times3=9$ and $5\times3=15$. Also $10=2\times5$, we need to add $3\times5=15$ and $5\times5=25$. Now we had set $\{1,2,3,5,4,6,10,9,15,25\}$. But this step is too slow, and I got lost finally.

Kenta S
  • 16,151
  • 15
  • 26
  • 53
Oziter
  • 349
  • 1
  • 2
  • 9

1 Answers1

6

Here are some hints:

  • Any number belonging to the set is of the form $2^a3^b5^c$ for some non-negative $a, b$ and $c$.
  • If $2^a3^b5^c$ lies in the set the so does every number of the form $2^s3^t5^u$ where $s+t+u \le a+b+c$.
Oliver Clarke
  • 1,425