Hint for Problem 3: December 2023

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

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\leq 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\).

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

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\leq v-1\).

Consider the cases when \(d\) is even and when \(d\) is odd separately.

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