This month’s problem is an extension of Problem 3 from Part B of the 2023 Canadian Intermediate Mathematics Contest. The original problem was stated as follows:
The positive integers are written into rows so that Row \(n\) includes every integer \(m\) with the following properties:
\(m\) is a multiple of \(n\),
\(m\leq n^2\), and
\(m\) is not in an earlier row.
The table below shows the first six rows.
| Row 1 | 1 |
| Row 2 | 2, 4 |
| Row 3 | 3, 6, 9 |
| Row 4 | 8, 12, 16 |
| Row 5 | 5, 10, 15, 20, 25 |
| Row 6 | 18, 24, 30, 36 |
Determine the smallest integer in Row \(10\).
Show that, for all positive integers \(n \geq 3\), Row \(n\) includes each of \(n^{2} - n\) and \(n^{2} - 2n\).
Determine the largest positive integer \(n\) with the property that Row \(n\) does not include \(n^2-10n\).
If you have not already done so, we suggest thinking about the parts above before proceeding.
For each positive integer \(k\), determine the largest positive integer \(n\) with the property that Row \(n\) does not include \(n^2-kn\). (This generalizes part (c) from the original problem.)
In the remaining questions, \(f(n)\) is defined for each \(n\geq 1\) to be the largest non-negative integer \(m\) such that \(m \leq n\) and \(mn\) is not in Row \(n\). For example, Row \(6\) is \(18,24,30,36\), so \(f(6)=2\) since \(2\times 6=12\) is not in Row \(6\) but \(3 \times 6\), \(4\times 6\), \(5\times 6\), and \(6\times 6\) are all in Row \(6\).
Show that \(f(p) = 0\) for all prime numbers \(p\). (Looking closely at the definition of \(f(n)\), \(f(p)=0\) means that every positive multiple of \(p\) from \(p\) through \(p^2\) appears in Row \(p\).)
Find an expression for \(f(pq)\) where \(p\) and \(q\) are prime numbers. Justify that the expression is correct.
Find an expression for \(f(p^d)\) where \(p\) is a prime number and \(d\) is a positive integer.
Take some time to explore the function \(f\) further on your own. Are there other results you can prove about the function beyond what is done in (b), (c) and (d)? Is there a nice way to compute \(f(n)\) in general without computing each of the first \(n-1\) rows?