9
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Since $\phi(1)=\phi(2)=1$, $\phi(a)$ isn't always even. $\endgroup$ – J.G. Dec 6 '18 at 9:12
  • $\begingroup$ 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. $\endgroup$ – Chris Culter Dec 27 '18 at 10:19
  • 1
    $\begingroup$ @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. $\endgroup$ – ploosu2 Dec 29 '18 at 9:41
  • $\begingroup$ 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). $\endgroup$ – Breakfastisready Dec 30 '18 at 2:19
  • 2
    $\begingroup$ If you sum over all $b$ for a fixed $a$, and then index a sequence by $a$, you get A057562 $\endgroup$ – alex.jordan Jan 1 at 6:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.