0
$\begingroup$

I recently asked what percentage of odd composite integers was divisible by three here. The best answer proved that since the frequency in the amount of primes goes to $0$ as they approach infinity, $\frac{1}{3}$ of all odd composites are divisible by three. This proved very helpful to me, but I am now looking for an upper bound for the amount of odd composites divisible by $3$. I am hoping for an upper bound less than $100$% of all odd composites.

$\endgroup$
  • 2
    $\begingroup$ I'n not sure why you keep stressing "composites". Other than $3$, any number divisible by $3$ is composite. $\endgroup$ – lulu Mar 14 '17 at 21:32
  • $\begingroup$ @lulu Well, $-3$ is also prime, but I doubt Linus was thinking about it. So alright, I'm just as puzzled as you are. $\endgroup$ – Mr. Brooks Mar 14 '17 at 22:16
  • $\begingroup$ Also...in the header you ask for odd composites but in the body of the question you leave off the "odd". I think that's what causes the confusion with the posted solution below. The same method works, of course. You want numbers less than $n$ of the form $6k+3$, excluding $3$. $\endgroup$ – lulu Mar 14 '17 at 23:16
  • $\begingroup$ @lulu Yes, but I am looking for the amount of composites divisible by 3. For instance, $25$ is composite, but not divisible by 3. $\endgroup$ – Linus Rastegar Mar 15 '17 at 1:48
  • $\begingroup$ Well, I don't get it. The posted solution (from @vrugtehagel) is correct other than for the confusion in your original post about "odd" or not. If you define $f(n)$ to be the number of odd multiples of $3$, other than $3$ itself, which are less than $n$ then $f(n)=\lfloor \frac {n-3}6\rfloor$ by a simple variation on the argument given in that solution. Thus $f(16)=\lfloor \frac {13}6\rfloor=2$ and we can check that by inspection ($9,15$ are the cases). Is that what you wanted? $\endgroup$ – lulu Mar 15 '17 at 11:02
2
$\begingroup$

Exactly $n-1$ numbers below $3n$ are divisible by three, in other words, there are exactly $\lfloor \frac n3\rfloor-1$ numbers below $n$ are divisible by $3$. This is because $3$ is the only prime divisible by three and so the rest of the numbers divisible by three are composite.

Exactly a third of the numbers $1,2,3,4,\cdots,3n$ is divisible by $3$. Only one is not composite. Thus, $n-1$ numbers are divisible by $3$. We can tweak this to say $\lfloor \frac n3\rfloor-1$ numbers less than $n$ are divisible by $3$.

Since this is the exact amount, it is both an upperbound and a lowerbound simultaneously.

$\endgroup$
  • $\begingroup$ I agree with your result on the amount of numbers that are divisible by $3$. I do not agree that the amount of composites less than $n$ that are divisible by $3$ is the same amount. In your sequence $1, 2, 3, 4, ... , 3n$, $2$ is prime, $5$, $7$, $11$, $13$ ... are all prime. This leaves you only with $1, 4, 6, 9, 15 ... $, of which $2$ are odd composites divisible by $3$, which is definitely not $\frac{n}{3} - 1$ $\endgroup$ – Linus Rastegar Mar 14 '17 at 22:14
  • 1
    $\begingroup$ I'm not saying it's the same, it's one less. $3$ is the only prime divisibly by three. Of the numbers $1,2,3,\cdots,3n$, the ones divisible by three are $3,6,9,\cdots,3n$, and of those, only $3$ is prime and thus the rest is composite. $\endgroup$ – vrugtehagel Mar 14 '17 at 22:21
  • $\begingroup$ I've been hesitant to accept this answer because I was convinced that the answer was more complicated. Your reasoning makes sense to me now. Can I apply this same logic to the amount of number divisible by $5$ or $7$? $\endgroup$ – Linus Rastegar Apr 27 '17 at 13:40
  • $\begingroup$ Yes you can. You can apply the same exact reasoning to find the amount of numbers divisible by any prime $p$. $\endgroup$ – vrugtehagel Apr 27 '17 at 20:23

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.