From the set $S=\{1,...,n\}$, count the number of ways to have $ab=cd$ So I found an interesting pattern when looking at the number of zero divisors in a set of matrices, but proving that it works will involve solving the following

Say $S=\{1,...,n\}$ for some positive integer $n$.

How many $4$-tuples $(a,b,c,d)$ of elements of $S$ are there with$\,\;a\le b,\;c\le d,\;a < c\;\,$such that $ab=cd\,$?

For example, say $S=\{1,...,8\}$.
Then we have
\begin{align*}
1 \times 4 &= 2 \times 2\\[4pt]
1 \times 6 &= 2 \times 3\\[4pt]
1 \times 8 &= 2 \times 4\\[4pt]
2 \times 6 &= 3 \times 4\\[4pt]
2 \times 8 &= 4 \times 4\\[4pt]
3 \times 8 &= 4 \times 6\\[4pt]
\end{align*}
so the count is $6$.

I believe there is some sort of general pattern for the count for any such set $S$, but I've been having trouble figuring it out. 
 A: This is the Erdos multiplication table problem. There is a lot of literature on it. No closed-form solution, but very good asymptotics. See, for example, https://mathoverflow.net/questions/31663/distinct-numbers-in-multiplication-table
A: For each positive integer $n$, let $f(n)$ be the number of $4$-tuples $(a,b,c,d)$ of integers such that


*

*$1\le a \le b\le n$$\\[4pt]$

*$a < c \le d\le n$$\\[4pt]$

*$ab=cd$
Your preferred goal is to find a closed-form expression for $f(n)$.

My sense is that's probably not possible, however, using an auxiliary function $g(n)$ expressible as a summation, we can get a recursion . . .

For each positive integer $n$, let $g(n)$ be the number of pairs $(a,b)$ of integers such that


*

*$1 < a \le b < n$$\\[4pt]$

*$n{\,\mid\,}ab$
Then we have the recursion
$$
f(n)=
\begin{cases}
0&\;\;\;\text{if}\;n=1\\[4pt]
f(n-1)+g(n)&\;\;\;\text{if}\;n > 1\\
\end{cases}
$$
and where $g(n)$ can be computed via the summation
$$
g(n)
=
\sum_{a=1}^{n-1}
\left(
\gcd(a,n)
-
\left\lceil
\frac{a{\,\cdot}\gcd(a,n)}{n}
\right\rceil
\right)
$$
hence, $f(n)$ can be expressed as
$$
f(n)
=
\sum_{k=1}^n g(k)
=
\sum_{k=1}^n
\sum_{a=1}^{k-1}
\left(
\gcd(a,k)
-
\left\lceil
\frac{a{\,\cdot}\gcd(a,k)}{k}
\right\rceil
\right)
$$
Using the above, here are the results for $1\le n\le 16\,$:
\begin{array}
{c
|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|
}
\hline
n&
1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16
\\ 
\hline
g(n)&
0&0&0&1&0&2&0&3&3&4&0&9&0&6&8&10
\\
\hline
f(n)&
0&0&0&1&1&3&3&6&9&13&13&22&22&28&36&46
\\
\hline
\end{array}

Some explanations . . .

$\bullet\;$Explanation for the recursion for $f(n)$ . . .


*
Fix $n > 1$.


Any $4$-tuple $(a,b,c,d)$ counted by $f(n-1)$ is a qualifying $4$-tuple for $f(n)$.

The $4$-tuples $(a,b,c,d)$ for $f(n)$ that are not counted by $f(n-1)$ are those where one of $a,b,c,d$ is equal to $n$, which is what $g(n)$ counts.

Thus $f(n)=f(n-1)+g(n)$.



$\bullet\;$Explanation for the summation for $g(n)$ . . .


*
By the conditions on $a,b,c,d$, it's not possible for more than one of $a,b,c,d$ to be equal to $n$.


Thus, $g(n)$ counts the number of pairs $(a,b)$ with $1 \le a \le b\le n-1$ such that $n{\,\mid\,}ab$.

Fix $a\in \{1,...,n-1\}$.

Then the qualifying values of $b$ are the elements of $\{a,...,n-1\}$ which are divisible by 
$$\frac{n}{\gcd(a,n)}$$

Each such $b$ has the form 
$$b=w{\,\cdot\,}\frac{n}{\gcd(a,n)}$$
where $w$ is any positive integer (if any) such that
$$a\le w{\,\cdot\,}\frac{n}{\gcd(a,n)} < n$$
The smallest such $w$ is
$$
\left\lceil
\frac{a{\,\cdot}\gcd(a,n)}{n}
\right\rceil
$$
and the largest such $w$ is
$$\gcd(a,n)-1$$
For the given value of $a$, the number of qualifying values of $b$ is the same as the number of qualyfing values of $w$, which is just
$$
\gcd(a,n)
-
\left\lceil
\frac{a{\,\cdot}\gcd(a,n)}{n}
\right\rceil
$$
Then $g(n)$ is just the sum of the above for $1\le a\le n-1$.

