# Problem concerning the number of 3-digit integers that are both composite and have no prime divisors less than 15

How many three-digit composite integers are not divisible by any prime less than $15$?

I guess this could be written as, if $a$ was a 3-digit integer that is prime factorized as: $a=p_1p_2...p_k$, the prime factors $p_1,p_2,...p_k >15$.

• Since the number has three digits k is 1 or 2. – Bernd Jan 11 '18 at 5:34
• @Bernd and $k \not = 1$ because it is composite, so $k = 2$ – John Lou Jan 11 '18 at 5:35
• @JohnLou Thanks - it's a little early. So since k = 2 one factor can be at most about 999/15. So there are left only some possible primes and you ar done combining them. – Bernd Jan 11 '18 at 5:47
• I just listed all of the possible combinations, and I got $27$ – John Lou Jan 11 '18 at 14:31
• Check this link for a list. I don't think I missed any. desmos.com/calculator/bmlkim98ap – John Lou Jan 11 '18 at 14:34

## 2 Answers

$p_i >15$ so $p_i\ge 17$

$999/17 =<59$ so $p_i <59$ so $p_i\le 57$

$17^3 >999$ so your $k <3$ and as the number is composite $k\ge 2$. So $k=2$

So $a=p_1*p_2$ where $p_1$ and $p_2$ are from $17,19,23,29,31,37,41,43,47,53$

If we assume $p_1\le p_2$ then $p_1 \le p_2 \le \frac {999}{p_1}$.

So if $p_1=17$ there between $17*17$ to $17*53$ there are $10$ acceptable numbers.

$999/19<53$ So between $19*19$ to $19*47$ there are $8$ acceptable numbers.

$999/23\approx 43$ so between $23*23$ to $23*43$ there are $6$ acceptable numbers.

(By the way. $999/23$ is so very close to $43$ that $23*43=989$ is the largest such number.)

$999/29<35$ so between $29*29$ and $29*31$ there are $2$ acceptable numbers.

$999/31\approx 32$ so $31*31$ is an acceptable number. And there can't be any with both factors greater than $31$ as $37*37 >999$.

So there are $27$ possible such composites.

• $57$ is not prime $57 = 3*19$ – John Lou Jan 11 '18 at 14:27
• Your answer should then be $27$ – John Lou Jan 11 '18 at 14:33
• Well, that was stupid of me. – fleablood Jan 11 '18 at 16:40

$\sqrt {999}<32$, and $\frac {999}{15}\lt 67$, so $15\lt p_1\le p_2\lt 67$... Consider all products $17\cdot 17,17\cdot 19, 17\cdot23, 17\cdot 29, 17\cdot 31, 17 \cdot 37$ etc formed by primes up to $61$, without both being over $32$

(You can save some time by dividing the first prime into $999$, thus getting a bound on the size of the other one )

Sorry I'm too lazy to finish this list right now. .. But repeat what was done for $17$ for the primes up to $61$...

• Why aren't you consider squares? – fleablood Jan 11 '18 at 7:46
• @fleablood I guess I should have started with ${17}^2$... you are right. .. – Chris Custer Jan 11 '18 at 8:13
• Your method is good. I absolutely can not understand the accept answer. But oddly it got the same number , 28, that I did so it could be weirdly explained. Or it could be coincidence. – fleablood Jan 11 '18 at 8:16
• By the way $15$ isn't prime so we can get our upper limit by $999/17=58.7$ so we don't need any prime over 57. – fleablood Jan 11 '18 at 8:18
• @fleablood you are on the ball... the accepted answer is incorrect : $171$ ah, I see, the other part comes out right. .. – Chris Custer Jan 11 '18 at 8:22