Number of solutions to $a\cdot b=c$

Question

Question: Let $a,b,c,n \in \mathbb{N}$ be natural numbers subject to $1<a<b<c<n$. For a given $n$ can we determine the number of unique solutions of the equation $a\cdot b = c$? In other words, is there an analytic expression for the function $$ f(n) = \lvert\{a,b,c\in\mathbb{N} : a\cdot b =c\}\rvert$$

Background: This is a simplified version of the problem of enumerating all solutions to an instance of the product partition problem, where the size of problem instance is constrained to 3.

What I tried so far: Naively, we can choose ${n-1 \choose 3}$ combinations of $a,b,c$ if we ignore the inequality. Moreover, we must have $a < \sqrt{c}$ and $b \le \frac{c}{2}$. But I do not see how this information helps me determining the number of solutions.

Answer 1

This problem seems to be difficult to solve nicely, but it's still possible to present an interesting solution. First I'll mark: $$ g(n) = |\{1 < a < b < n \mid a\cdot b = n\}| $$ But notice that for any $b$ that satisfies $b \mid n$ there is only one fitting $a$ that will give us $ab=n$. Thus one can notice that the function $\sigma_0 (n)$ (divisor function) can be used to calculate $g$. Of course: $$ \sigma_0(n) \neq g(n) $$ because of the imposed condition $1 < a < b < n$. To make it more clear what modification we need to do to $\sigma_0(n)$ I'll rephrase $g$ like so: $$ g(n) = |\{b < n \mid \exists_{a < b} a \cdot b = n\}| $$ Or in other words if we look at all of the divisors, paired up: $$(a_1, b_1), (a_2, b_2), \cdots$$ in a way such that $a_i\cdot b_i =n$ we get that $g$ counts those pairs exactly, except the $(1, n)$ pair and except any pair that has the same element (because $a < b$). Thus: $$g(n) = \frac{\sigma_0 (n) - \mathbb{1}_{\sqrt{n}\in \mathbb{N}}}{2} - 1$$ Finally:

$$f(n) = \sum_{i=2}^{n - 1} g(i) = \sum_{i=2}^{n - 1} (\frac{\sigma_0 (i) - \mathbb{1}_{\sqrt{i}\in \mathbb{N}}}{2} - 1) =$$ $$ = 0.5\cdot\sum_{i=2}^{n - 1} \sigma_0 (i) - 0.5\cdot\sum_{i=2}^{n - 1}\mathbb{1}_{\sqrt{i}\in \mathbb{N}} - (n - 2)$$ And finally we have two sums we'll want to evaluate. The first one is just the divisor summatory function and the second one counts the number of perfect squares until $n$. While this is not a full solution, I hope it's enough to get you on the right track.

Answer 2

The total number of divisors of a number $m= \prod p_i^{a_i}$ is given as $\tau (m)= \prod (a_i+1)$. Note that the factors exist in pairs with a product $m$, so there will be an even number of factors, unless $m$ is a perfect square, in which case every $a_i+1$ will be an odd number and the number of factors will be odd, with the perfect square root being the 'odd' (unpaired) member of the set of factors. The set of factors includes the pair $1,m$, which are to be excluded from the count per the conditions stated. Also note that if $m$ is prime, it will have only the two factors $1,m$ and so it will not properly contribute to the sum in your problem either.

For each $m<n$, the function $\tau (m)$ gives its total number of factors, so to count the number of pairs, we wish to count $\frac{\tau(m)}{2}$. To account for perfect squares, which would yield a half integer value of that expression, we round down using the floor function: $\lfloor \frac{\tau(m)}{2}\rfloor$. This changes nothing for the count of pairs with distinct members. Finally, to account for the pair of factors corresponding to $1,m$, we subtract $1$: $\lfloor \frac{\tau(m)}{2}\rfloor -1$.

To obtain the total you seek, we sum over appropriate $m$: $$\sum_{m=6}^{(n-1)}(\lfloor \frac{\tau(m)}{2}\rfloor -1)$$ I start summing at $m=6$ because we know that $1,2,3,4,5$ being units, primes, or perfect squares will contribute nothing to the sum in any event.