1
$\begingroup$

I've recently learnt that every integer $n>210$ can be written as the sum of two coprime composites.

Similar to the totient function, is there any known function that works out the number of ways in which a positive integer $n$ can be written as the sum of two coprime composites $-$ in terms of the prime factors of $n$ and their respective exponents only?

EDIT:

Here's an example - There are $58$ different ways in which $211$ (a prime) can be written as the sum of two composite coprimes and $63$ different ways for $223$

One observation that I've made is that primes have the highest density of such composite coprime sums whilst primorials have the lowest density of those.

By density I'm referring to the ratio of all composite coprime sums (that add up to $n$) to all possible sums of two integers (that add up to $n$) which is $\lfloor{\frac{n}{2}}\rfloor$.

$\endgroup$
3
  • $\begingroup$ Please edit to include your efforts. A natural starting point might be to see if you can compute this for primes. $\endgroup$
    – lulu
    Commented Nov 19, 2022 at 17:47
  • $\begingroup$ I don't know if I missed the point with my answer, feel free to add a comment under my answer if anything is unclear. Otherwise, I'd be happy if you approved it. (: In any case, a "good" formula only depending on the prime factorization (similar to the formula for $\phi$) is not possible, as the function you describe ($\Psi$ in my answer) is not multiplicative. $\endgroup$ Commented Nov 21, 2022 at 16:14
  • $\begingroup$ @LurchiDerLurch - Your answer is quite detailed and I really appreciate it. However, it's the last sentence of your comment above that answers my question. Therefore if you include it in your answer I'll be able to approve it. Thanks. $\endgroup$
    – Filemath
    Commented Nov 21, 2022 at 18:18

1 Answer 1

2
$\begingroup$

Let $\Psi(n)$ be the number of possibilities to write $n$ as a sum of two coprime composites.

First of all, you ask for a formula for calculating $\Psi$ similar to the formula $$ \phi({p_1}^{e_1} \cdots {p_k}^{e_k}) = \prod_{i=1}^k \phi({p_i}^{e_i}) = \prod_{i=1}^k p_i^{e_i-1}(p_i-1).$$ Note that this expansion only exists because $\phi$ is multiplicative, i.e., for any two coprime integers $n$ and $m$ it holds that $\phi(nm) = \phi(n) \phi(m)$. However, $\Psi$ is not multiplicative (although the numbers are too big and I don't want to calculate an example right now).

Note that numbers $k$ and $n-k$ are coprime if and only if $n$ and $k$ are coprime, so the number of ways to write $n$ as the sum of two coprimes is $\frac 12 (\phi(n)-2)$, where $\phi$ is euler's totient function (we have to subtract two in order to exclude the representations $n = 1 + (n-1) = (n-1) + 1$). You also wanted the pairs to consist of composites only, so we need to subtract the number of primes $p \leq n$ which do not divide $n$, and by inclusion-exclusion, we need to add the number of ways to write $n$ as a sum of two primes again. Hence we get $$ \Psi(n) = \frac 12 (\phi(n)-2) - \pi'(n) + G(n),$$ where

  • $\pi'(n)$ is the number of primes $< n-1$ which are coprime to $n$
  • $G(n)$ is the number of ways to write $n$ as a sum of two different primes. (This is related to the Goldbach conjecture).

We can trivially bound $\pi'$ and $G$. If $\pi$ denotes the prime counting function, we get $$ \pi'(n) \leq \pi(n) \ll \frac n {\log n}$$ (you can read $\ll n/\log n$ as $\leq 10 \cdot n /\log n$) In case where $n$ is odd, we trivially have $G(n) \leq 1$, but in general $G(n) \leq \pi(n)$ is also good enough. Finally, it is known that $$ \liminf \phi(n) \frac{\log \log (n)}{n} = e^{-\gamma},$$ which shows that the approximation $$ \Psi(n) = \frac 12 \phi(n) + O\left( \frac{n}{\log n}\right)$$ is asymptotic.

We can do a bit better, $\pi'$ should be replacable with $\pi$ at the cost of a small error. Indeed, if $\omega(n)$ denotes the number of prime divisors of $n$, we find $\pi'(n) = \pi(n) - \omega(n)$, and it is easily verified that $\omega(n) \ll \log(n)$, which much smaller than $\pi(n)$. Unfortunately I don't know of a good way to bound $G(n)$ for even $n$. For odd $n$ we obtain $$ \Psi(n) = \frac 12 \phi(n) - \pi(n) + O(\log n), $$ for even $n$ we can't do better than $$ \Psi(n) = \frac 12 \phi(n) - \pi(n) + G(n) + O(\log n).$$ In both instances we can also use the prime number theorem in the form $$ \pi(x) = \mathrm{Li}(x) + O(xe^{-c \sqrt{\log(x)}}).$$

One way or another, the main term is $\frac 12 \phi(n)$, which explains what you observed: If $n$ is prime we find $$\Psi(n) \approx \frac 12 \phi(n) = \frac 12 (n-1)$$ while for primorials $n = \prod_{i \leq k} p_i$ we find $$ \Psi(n) \approx \frac 12 \phi(n) = \frac 12 \prod_{i \leq k} (p_i - 1),$$ which gets arbitrarily small compared to $n/2$.

$\endgroup$
3
  • 1
    $\begingroup$ +1. At one point you wrote $\pi'(n) \leq \pi(n) \ll \frac n {\log n}$. I think this should be $\pi'(n) \leq \pi(n) \sim \frac n {\log n}.$ $\endgroup$ Commented Nov 21, 2022 at 21:33
  • $\begingroup$ @DanielWainfleet This probably is a bit confusing. For the asymptotic we only need the upper bound, which is much easier to proof than the prime number theorem. But of course, you could directly state and use the PNT. $\endgroup$ Commented Nov 22, 2022 at 10:11
  • $\begingroup$ I see your point. $\endgroup$ Commented Nov 23, 2022 at 8:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .