1
$\begingroup$

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

|cite|improve this question
$\endgroup$
  • $\begingroup$ Since the number has three digits k is 1 or 2. $\endgroup$ – Bernd Jan 11 '18 at 5:34
  • 1
    $\begingroup$ @Bernd and $k \not = 1$ because it is composite, so $k = 2$ $\endgroup$ – John Lou Jan 11 '18 at 5:35
  • $\begingroup$ @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. $\endgroup$ – Bernd Jan 11 '18 at 5:47
  • $\begingroup$ I just listed all of the possible combinations, and I got $27$ $\endgroup$ – John Lou Jan 11 '18 at 14:31
  • $\begingroup$ Check this link for a list. I don't think I missed any. desmos.com/calculator/bmlkim98ap $\endgroup$ – John Lou Jan 11 '18 at 14:34
1
$\begingroup$

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

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

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Why aren't you consider squares? $\endgroup$ – fleablood Jan 11 '18 at 7:46
  • $\begingroup$ @fleablood I guess I should have started with ${17}^2$... you are right. .. $\endgroup$ – Chris Custer Jan 11 '18 at 8:13
  • $\begingroup$ 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. $\endgroup$ – fleablood Jan 11 '18 at 8:16
  • $\begingroup$ 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. $\endgroup$ – fleablood Jan 11 '18 at 8:18
  • $\begingroup$ @fleablood you are on the ball... the accepted answer is incorrect : $171$ ah, I see, the other part comes out right. .. $\endgroup$ – Chris Custer Jan 11 '18 at 8:22

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.