1
$\begingroup$

In a previous post, it was explained that the number of integers relatively prime to $6$ that are below a given $x$ is roughly $\frac{x}{3}$.

I am wondering if it is possible use this result to estimate the number of composite integers relatively prime to $6$ that are below a given $x$.

The goal would be to count the number of ways that these $\frac{x}{3}$ integers can be paired up.

To do this estimation, we would only need to consider how many ways the first $\frac{\sqrt{x}}{3}-1$ integers relatively prime to $6$ (not including $1$) pair up.

For example if $x = 144$, we would only need to consider the first $\frac{\sqrt{144}}{3} - 1 = 3$ which are $\{ 5, 7, 11\} < \sqrt{144}$

$5$ pairs up with $\frac{144}{5}\left(\frac{1}{3}\right)-1 = 8$ which are $\{5,7,11,13,17,19,23,25\}$ with each $< \frac{144}{5}$

$7$ pairs up with $\frac{144}{7}\left(\frac{1}{3}\right)-1 = 5$ which are $\{7, 11, 13, 17, 19\}$ with each $< \frac{144}{7}$

$11$ pairs up with $\frac{144}{11}\left(\frac{1}{3}\right)-1 = 2$ which are $\{11, 13\}$ with each $< \frac{144}{11}$

Does this approach make any sense? Is there a way to estimate the number of pairings for a given $x$?

$\endgroup$
3
$\begingroup$

All of the primes less than $x$, except exactly two (namely $2$ and $3$) are coprime to $6$. So to get the number of composite numbers less than $x$ that are coprime to $6$ all you need to do is estimate the number of coprimes (close to $x/3$) and subtract the number of primes less than $x$, minus 2, and then subtract one more because $1$ is usually considered neither prime not composite.

The number of primes less than $x$ can be approximated using the prime number theorem and its various variants and strenghtenings.

$\endgroup$

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.