Problem of the Month
Hint for Problem 3: December 2023

For positive integers $m$ and $n$ with $m\le n$, the integer $mn$ is not in Row $n$ if and only if there are integers $a$ and $b$ with $m<a\le b<n$ such that $mn=ab$. This fact will likely be useful in all parts of this problem.

1. With the above fact in mind, convince yourself that if $n^2-kn$ is not in Row $n$, then there must be positive integers $x$ and $y$ such that $x\le y<k$ and $n^2-kn=(n-x)(n-y)$. Now solve for $n$ and try to determine how to choose $x$ and $y$ to maximize this expression for $n$.

2. If integers $a$, $b$, $n$, and $p$ satisfy $mp=ab$ and $p$ is prime, then at least one of $a$ and $b$ must be a multiple of $p$.

3. The general formula is $f(pq)=(p-1)(q-1)$. In this part and the rest of the parts, you might find the following observation useful: If $u$ and $v$ are integers with $u<v$, then $u\le v-1$.

4. Consider the cases when $d$ is even and when $d$ is odd separately.

5. To formulate a guess at how to find $f(n)$ in general, consider some values of $n$ for which you know the value of $f(n)$ and list the positive factors of $n$ in increasing order. If you are so inclined, you could write some computer code to compute $f(n)$ for some moderately sized values of $n$.

   The value of $f(n)$ depends on how $n$ factors, so it is probably unreasonable to expect a general algebraic expression for $f(n)$ similar to $f(pq)=(p-1)(q-1)$. Instead, try to find a simple procedure to compute $f(n)$ assuming that you already know all the positive factors of $n$.