Is there a way of cleverly counting the following scenario?
Given an $m\times n$ grid, with $m$ and $n$ relatively prime, imagine shading a subset of the squares of an $m\times n$ grid using this procedure:
For each $i \in \{1,\dots,m\}$ such that $\gcd(i,m)>1$, shade all of the squares in the $i^\text{th}$ row.
For each $j\in \{1,\dots,n\}$ such that $\gcd(j,n)>1$, shade all of the squares in the $j^\text{th}$ column.
Let $\sigma (x)$ be the number of ways to choose the ordered pair $(m,n)$ such $m$ and $n$ are relatively prime, and that there are exactly $x$ unshaded squares when you do this procedure.
Question: Is there a clever way to compute $\sigma(x)$?
For example $\sigma (8)$ represents the number of $m\times n$ squares such that it has $8$ holes. I can think of two grids which are in $\sigma(8$) and those are $3\times 5$ grids and the $4\times 5$ grids as drawn below (I shaded the third row and $5$th row for the $3\times 5$ grid as $3$ and $5$ are the only prime factors of the row and column numbers of $3$ and $5$ greater than $1$):
But there might be more than these two grids which are in $\sigma (8)$, so is there a formula for counting the total number of grids which fall under $\sigma(x)$ for any $0\le x $?
Best Answer
I do not think there is an explicit formula for this. However we can calculate it for a specific x. We find that the number of non shaded squares is $\phi(m) \phi(n)$. This is because $\phi(m)$ is the number of unshaded rows and $\phi(n)$ is the number of unshaded columns. We can simplify this to $\phi(mn)$ because they are relative prime. There is to my knowledge no explicit inverse function for $\phi$. In this link https://www.dcode.fr/euler-totient. It calculates it using an algoritm. (It also links how the algoritm works.) For example it gives for $x = 8$ the numbers $mn = 15,16,20,24,30$. We can find $\sigma(x)$ by finding al the different $m,n$ such that $m\times n = 15,16...30$ and counting these. (There are many ways to do this.) Thus for example is in this case $m = 4, n=4$ also a solution, because $4 \times 4 = 16$ and $\phi(16) = 8$. This is a long process, but I cannot make it easier.