5
$\begingroup$

Given a number $n \in \mathbb{N}$, define $a(n)=\{(d_1,d_2,d_3): d_i|n,\ \gcd(d_1,d_2,d_3)=1,\ 1 \leq d_1 \leq d_2 \leq d_3\}$. What is $|a(n)|$?

There were similar questions asked about pairs rather than triples here: Number of pairs of nontrivial relatively prime divisors and here: Number of Relatively Prime Factors but the addition of the third component seems to make the arguments used in these two questions obsolete.

An example:

Let $n=p$ for some prime $p$. Then the divisors of $n$ are $\{1,p\}$, and the triples of those divisors whom are relatively prime (order does not matter) as a triple are $\{(1,1,1),(1,1,p),(1,p,p)\}$. Thus we see that for any prime, the answer is $|a(n)|=3$.

Similarly, (its not hard to check) for $n=p^2$, we have $|a(n)|=6$.

In fact, if you let $n=p^k$ for $0 \leq k \in \mathbb{Z}$, it seems that $|a(n)|={{k+2} \choose {2}}$.

Also for $n=pq$ where $p$ and $q$ are distinct primes, $|a(n)|=13$ (again, not hard to check).

This leads me to believe that like in the other answers for the two referenced questions, the answer may be found using some nice combinatorics, but if looked at just right from a Number Theoretic perspective, may be a multiplicative function or composition of multiplicative functions, based on how the answers seem to only depend on the powers of the primes in the prime factorization of the number.

$\endgroup$
  • $\begingroup$ If you forget about $d_1\leq d_2\leq d_3$, it becomes multiplicative. Then deal with $d_1=d_2$ and so on. $\endgroup$ – Michael Jul 12 '18 at 2:11
3
$\begingroup$

As in the pair case, let's first find the number of ordered triples without restrictions on the order of the entries.

Every prime factor $p_i$ with multiplicity $a_i$ occurs in at most two divisors.

There is $1$ way for $p_i$ to occur in zero divisors.

There are $3a_i$ ways for $p_i$ to occur in one divisor.

There are $3a_i^2$ ways for $p_i$ to occur in two divisors.

Thus, in total there are $3a_i^2+3a_i+1$ ways to distribute $p_i^{a_i}$ over the divisors, and hence there are $\prod_i(3a_i^2+3a_i+1)$ ordered triples. From this we want to deduce the number of unordered triples (or, equivalently, the number of ordered triples with the order restrictions on the entries).

There is one triple with three equal entries, namely $(1,1,1)$. There are $\prod_i(2a_i+1)-1$ ordered pairs of distinct coprime divisors, each of which corresponds to three ordered triples with two equal entries but only one unordered triple with two equal entries. Thus the count of unordered triples is

$$ \frac{\prod_i(3a_i^2+3a_i+1)-3\left(\prod_i(2a_i+1)-1\right)-1}6+\prod_i(2a_i+1)-1+1=\frac{\prod_i(3a_i^2+3a_i+1)+3\prod_i(2a_i+1)+2}6\;. $$

You can check that your examples all come out right.

$\endgroup$
1
$\begingroup$

In fact, if you let $n=p^k$ for $0 \leq k \in \mathbb{Z}$, it seems that $|a(n)|={{k+2} \choose {2}}$.

If $n=p^k$ we can write the triple as $(p^r, p^s, p^t)$ with $r \le s \le t$. Since the GCD of the triple is $1$, clearly $r = 0$. So you're counting integer values of $s, t$ such that $0 \le s \le t \le k$. If $s \neq t$ there are $\binom{k+1}{2}$ ways of choosing them from $k+1$ options; if $s = t$ there are $\binom{k+1}{1}$ ways; and $\binom{k+1}{2} + \binom{k+1}{1} = \binom{k+2}{2}$.


On the general question, let $q$ be prime and coprime to $n$, and consider $(d_1, d_2, d_3) \in a(nq^k)$. We can project $d_i$ onto $n$ and $q^k$ by taking the GCD, so $\textrm{sort}(\gcd(d_1, n), \gcd(d_2, n), \gcd(d_3, n)) \in a(n)$ (where $\textrm{sort}$ gives the ordered triple) and similarly for $q^k$. This gives a upper bound $$a(nq^k) \le 3!\, a(n)\, a(q^k)$$ where the factor of $3!$ is the number of ways to sort 3 items (wlog the triple from $q^k$, when pairing up its elements with the elements of the triple from $n$). However, we need to account for the fact that the triples are not required to have 3 distinct values, so that some of the orders will create duplicates.

We can split $a(n)$ up into three parts: triples with one distinct value $a_1(n) = \{(1,1,1)\}$; triples with two distinct values $a_2(n)$; and triples with three distinct values $a_3(n)$. Triples with two distinct values break down as $(r, r, s)$ or $(r, s, s)$. When $n=p^k$ we have $(1, 1, p^r)$ or $(1, p^r, p^r)$ with $0 < r \le k$, so $a_2(p^k) = 2k$. $a_3(p^k) = \binom{k}{2}$ by similar arguments to the first section. As a sanity check, $a_1(p^k) + a_2(p^k) + a_3(p^k) = 1 + 2k + \binom{k}{2} = \binom{k+2}{2}$.

Now we have nine cases for pairing an element of $a(n)$ with an element of $a(q^k)$. Five of them are covered by the observation that $(1,1,1)$ paired with an element of $i$ distinct values gives an element of $i$ distinct values. That leaves:

  • Two with two: $(d_1, d_1, d_2)$ paired with $(e_1, e_1, e_2)$ gives $(d_1 e_1, d_1 e_1, d_2, e_2)$ (two distinct elements) and $(d_1 e_1, d_1 e_2, d_2 e_1)$ which (since we're building from coprime parts) has three distinct elements.
  • Two with three: three permutations each of three distinct elements.
  • Three with three: the full six permutations, each of three distinct elements.

So we get the recurrence $$\begin{eqnarray} a_1(nq^k) &=& a_1(n) a_1(q^k) \\ a_2(nq^k) &=& a_1(n) a_2(q^k) + a_2(n) a_1(q^k) + a_2(n) a_2(q^k) \\ a_3(nq^k) &=& a_1(n) a_3(q^k) + a_3(n) a_1(q^k) + a_2(n) a_2(q^k) +\\&& 3a_2(n) a_3(q^k) + 3a_3(n) a_2(q^k) + 6a_3(n) a_3(q^k) \end{eqnarray}$$

and we can substitute in and simplify to

$$\begin{eqnarray} a_1(nq^k) &=& 1 \\ a_2(nq^k) &=& (2k+1)(a_2(n)+1) - 1 \\ a_3(nq^k) &=& \left(3k^2 + 3k + 1\right) a_3(n) + \frac{(3k+1)k}{2} a_2(n) + \frac{k(k-1)}{2} \end{eqnarray}$$

If we define $a_{1+2}(n) = a_1(n) + a_2(n)$, there's a nice simple recurrence $a_{1+2}(nq^k) = (2k+1)a_{1+2}(n)$, but not for $a_3$.

$\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.