Number of ways a natural number can be written as a sum of naturals that are all coprime to it.

let $$X: \mathbb{N}^2 \to \mathbb{N}$$

Let $$X(a ,b)$$ be the number of unique ways we can write $$a$$ as the sum of $$b$$ many numbers, where each of the $$b$$ numbers are co-prime to $$a$$. Where $$a$$ $$\in \mathbb{N}$$ and $$b$$ $$\in \mathbb{N}$$

Example:

$$X(a ,2) = |\{(x, y): x + y = a$$, $$gcd(a, x) = gcd(a, y) = 1\}|$$

I can easily show that $$X(a, 2) = \frac{\phi(a)}{2}$$, where $$\phi$$ is Euler's totient function, when $$a > 2$$.

Proof:

Let $$\Phi_{a} = \{k: gcd(a, k) = 1, k \in \mathbb{N}\}$$

let $$k \in \mathbb{N}$$, then it is easy to see $$\forall k < a$$, $$\exists n \in \mathbb{N}$$ such that $$a = k + n$$

Specifically, this is $$n = a - k$$

Now if we only consider $$k \in \Phi_{a}$$ we can see that $$n \in \Phi_{a}$$. Why is this so? Here is why:

Let $$k \in \Phi_{a}$$ i.e. $$gcd(a, k) = 1$$, now if we assume $$n \notin \Phi_{a}$$ i.e. $$gcd(a, n) \neq 1$$ it implies that $$\exists m \in \mathbb{N}$$ such that $$m | a$$ and $$m | n$$. But this means that $$m | k$$ (because $$n = a - k$$) which contradicts $$gcd(a, k) = 1$$. Thus our assumption was wrong and therefore $$n \in \Phi_{a}$$.

Hence it follows that, $$\forall x \in \Phi_{a}$$ $$\exists y \in \Phi_{a}$$ such that $$x + y = a$$. We also know that $$|\Phi_{a}| = \phi(a)$$ thus once we pair our numbers together we have exactly $$\frac{\phi(a)}{2}$$ unique pairs $$(x, y)$$. Here unique means if we have counted the pair $$(x, y)$$ then we do not count the pair $$(y, x)$$ as we consider them to be the same pair.

End of proof

Now to my actual question: Can we find the value of $$X(a, b)$$ in terms of $$a$$ and $$b$$ when $$b > 2$$? So far I have only defined the trivial cases:

$$X(a ,b) = \begin{cases} 0, & b \gt a\ &OR& b + 1\equiv a\equiv 0\pmod 2 &OR& b = 1, a\gt 1\\ 1, & b = a\\ \frac{\phi(a)}{2},& b = 2, a \gt 2\\ ?,& Otherwise\end{cases}$$

Just so that my question is clear, for $$b = 3$$ we have:

$$X(a ,3) = |\{(x, y, z): x + y + z = a$$, $$gcd(a, x) = gcd(a, y) = gcd(a, z) = 1\}|$$

This question is purely out of interest, thanks in advance for any answers.

• Since $\phi(1)=\phi(2)=1$, $\phi(a)$ isn't always even. – J.G. Dec 6 '18 at 9:12
• Here are the values of $X(a,3)$ for $3\leq a\leq27$: 1, 0, 6, 0, 15, 0, 9, 0, 45, 0, 66, 0, 12, 0, 120, 0, 153, 0, 30, 0, 231, 0, 150, 0, 81. This is enough to show that the sequence isn't known to OEIS or Google. – Chris Culter Dec 27 '18 at 10:19
• @ChrisCulter You must be counting all the tuples $(x,y,z)$ as different (that is integer combinations). I think the question asks for integer partitions (see the last sentence of op's proof). Although then the notation $(x,y,\dots)$ isn't correct. We should demand $x\leq y \leq\dots$. For this partition definition I got the values for $X(a, 3)$ for $a\geq 0$: $$0, 0, 0, 1, 0, 2, 0, 4, 0, 3, 0, 10, 0, 14, 0, 4, 0, 24, 0, 30, 0, 8, 0, 44,\dots$$. That isn't found either. – ploosu2 Dec 29 '18 at 9:41
• If you allow repetitions (that is, $(2,3)$ and $(3,2)$ are both counted in the sum $X(5,2)$ ) then you can write a nice recursive relation between $X(a,b)$ and some $X(?,b-1)$s. It's unlikely that you can find something better than that (as others have checked on OEIS). – Breakfastisready Dec 30 '18 at 2:19
• If you sum over all $b$ for a fixed $a$, and then index a sequence by $a$, you get A057562 – alex.jordan Jan 1 at 6:53