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

$\endgroup$
5
  • $\begingroup$ Since the number has three digits k is 1 or 2. $\endgroup$
    – Bernd
    Jan 11, 2018 at 5:34
  • 1
    $\begingroup$ @Bernd and $k \not = 1$ because it is composite, so $k = 2$ $\endgroup$
    – John Lou
    Jan 11, 2018 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, 2018 at 5:47
  • $\begingroup$ I just listed all of the possible combinations, and I got $27$ $\endgroup$
    – John Lou
    Jan 11, 2018 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, 2018 at 14:34

2 Answers 2

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.

$\endgroup$
3
  • $\begingroup$ $57$ is not prime $57 = 3*19$ $\endgroup$
    – John Lou
    Jan 11, 2018 at 14:27
  • $\begingroup$ Your answer should then be $27$ $\endgroup$
    – John Lou
    Jan 11, 2018 at 14:33
  • 1
    $\begingroup$ Well, that was stupid of me. $\endgroup$
    – fleablood
    Jan 11, 2018 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$...

$\endgroup$
11
  • $\begingroup$ Why aren't you consider squares? $\endgroup$
    – fleablood
    Jan 11, 2018 at 7:46
  • $\begingroup$ @fleablood I guess I should have started with ${17}^2$... you are right. .. $\endgroup$
    – user403337
    Jan 11, 2018 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, 2018 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, 2018 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$
    – user403337
    Jan 11, 2018 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.