What is the largest integer \(n\) such that \(n!\) can not be expressed as the sum of \(n\) distinct factors of itself?

[SOLVED]

3 comments

Ilan Mayer solved this puzzle:

The largest such \(n\) is \(2\).

\[3! = 6 = 3 + 2 + 1.\]

For \(4!\), create \(4\) factors from the factors of \(3\) above by multiplying the fisrt \(2\) factors by \(4\) each, and adding \(3\) and \(1\) as additional factors, yielding \(4! = 24 = 12 + 8 + 3 + 1\).

This can be continued for any integer \(n \gt 3\). Assuming that there is a set of \(n - 1\) factors of \((n - 1)!\) such that the set includes \(1\) and the sum of the numbers in the set is \((n - 1)!\), we can obtain \(n\) factors of \(n!\) such that their sum is \(n!\) by multiplying each number except \(1\) in the set by \(n\) and adding \(n - 1\) and \(1\) as additional factors.

Hagen von Eitzen solved this puzzle:

The answer is \(2\), which follows from theorem 1 below. \( \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \)

Let \(X\subseteq \N\) be the set of all natural numbers \(n\) such that \(n!\) can be expressed as a sum of \(n\) distinct divisors of \(n!\).

For a non-empty finite set \(S\) of natural numbers, let \(\#S\) denote the cardinality of \(S\), \(\lcm(S)\) the least common multiple of its elements and

\[ r(S) = \sum_{k \in S} \frac{1}{k} \]

the sum of reciprocals of elements of \(S\).

For \(x \in \mathbb{R}\), let \([x]\) denote the largest integer \(\le x\). For \(n \in \N\) and a prime \(p\), let \(\nu_p(n)\) be the exponent of the highest power of \(p\) dividing \(n\). It is well-known that

\begin{equation}\label{mdef} \nu_p(n!) = \left[\frac n{p}\right] + \left[\frac n{p^2}\right] + \left[\frac n{p^3}\right] +\dots. \end{equation}

Lemma 1. For \(n \in \N\), we have

\begin{align*} \nu_2(n!) & \ge 2 \left[ \frac{n + 1}{3} \right] - 1 \\ \nu_3(n!) & \ge \left[ \frac{n}{3} \right]. \end{align*}

Proof. All summands in \eqref{mdef} are non-negative, hence from using only the first summand we find immediately \(\nu_3(n!) \ge \left[ \frac{n}{3} \right]\). Let \(k = \left[ \frac{n+1}{3} \right]\). Then \(n = 3k + r\) with \(r \in \{-1, 0, 1\}\). Estimating the first two summands of \eqref{mdef} for \(p=2\) we find

\begin{align*} \nu_2(n!) & \ge \frac{n - 1}{2} + \frac{n - 3}{4} \\ & = \frac{3n - 5}{4} \\ & = \frac{9k + 3r - 5}{4} \\ & = (2k - 1) + \frac{k + 3r - 1}{4}. \\ \end{align*}

This shows the desired result if \(r = 1\) and \(k \ge 0\), or if \(r = 0\) and \(k \ge 1\), or if \(r = -1\) and \(k \ge 4\). This covers all \(n \in \N\) except \(n = 3k - 1\) with \(k \le 3\). These can be checked explicitly. \(\nu_2(2!) = 1 \ge 1\), \(\nu_2(5!) =3 \ge 3\), \(\nu_2(8!) = \left[ \frac{8}{2} \right] + \left[ \frac{8}{4} \right] + \left[ \frac{8}{8} \right] + \dots = 7 \ge 5\).

Lemma 2. If \(S\) is a set of \(n\) natural numbers such that \(r(S) = 1\) and \(\lcm(S) \mid n!\), then \(n \in X\).

Proof. Consider \[ \sum_{k \in S} \frac{n!}{k} = n! \cdot r(S) = n!.\] The \(n = \#S\) summands are clearly pairwise distinct. All \(k \in S\) are divisors of \(\lcm(S)\), hence of \(n!\), hence their co-factors \(\frac{n!}{k}\) are also divisors of \(n!\).

Lemma 3. Let \(k \ge 1\) and \begin{equation}\label{Adef} A = \{3 \cdot 2^j \mid 0 \le j \le 2k - 1\} \cup \{4^j \mid 1 \le j < k\}. \end{equation} Then \(\#A = 3k - 1\), \(\lcm(A) = 3 \cdot 2^{2k - 1}\) and \(r(A) = 1 - 2^{1-2k}\)

Proof. The two sets we are taking a union of are clearly disjoint (check divisibility by 3) and contain \(2k\) and \(k - 1\) elements, respectively. Hence \(\#A = 3k - 1\). Clearly \(3 \cdot 2^j \mid 3 \cdot 2^{2k-1}\) if \(j \le 2k - 1\) and \(4^j \mid 3 \cdot 2^{2k-1}\) if \(j < k\). Thus \(\lcm(A) = 3 \cdot 2^{2k-1}\) follows from \(3 \cdot 2^{2k-1} \in A\). Finally, from the formula for geometric series,

\begin{align*} r(A) & = \frac{2}{3} \sum_{j=1}^{2k} 2^{-j} + \sum_{j=1}^{k-1} 4^{-j} \\ & = \frac{2}{3} \cdot (1 - 2^{-2k}) + \frac{1 - 4^{1-k}}{3} \\ & = 1 - 2^{1 - 2k}. \end{align*}

Lemma 4. We have \(3k \in X\) if \(k \ge 1\) and \(3k \pm 1 \in X\) if \(k \ge 2\).

Proof. Assume \(k \ge 1\). Let \(A\) be the set given by \eqref{Adef}. Let \(B = A \cup \{2^{2k -1}\}\). Since \(2^{2k-1} \notin A\) (it is a power of 2, but not a power of 4), we conclude that \(\#B = \#A + 1= 3k\). Also from lemma 3, \(r(B) = r(A) + \frac{1}{2^{2k-1}} = 1\). Finally we see that \(\lcm(B) = \lcm(A) = 3 \cdot 2^{2k-1}\) because \(2^{2k - 1} \mid3 \cdot 2^{2k-1}\). From lemma 1 we see that \(\nu_3 \bigl((3k)! \bigr) \ge k\ge1\) and \(\nu_2 \bigl( (3k)! \bigr) \ge 2k-1\), hence lemma 2 applies to the set \(B\) and we obtain \(3k \in X\), the first claim.

For the rest of the proof assume \(k \ge 2\).

We have that \(6 \in B\), but \(9, 18 \notin B\). Let \(C = (B \setminus \{6\} ) \cup \{9, 18\}\). Then \(\#C = \#B+1 = 3k+1\), \(r(C) = r(B) -\frac{1}{6} + \frac{1}{9} + \frac{1}{18} = r(B) = 1\) and clearly \(\lcm(C) = \lcm(18, \lcm(B)) = 3^2 \cdot 2^{2k-1}\). From lemma 1 we see that \(\nu_3 \bigl( (3k+1)! \bigr) \ge k \ge 2\) and \(\nu_2 \bigl( (3k+1)! \bigr) \ge2k-1\), thus from lemma 2 applied to \(C\) we conclude that \(3k+1 \in X\) if \(k \ge 2\), the "\(+\)" part of the second claim.

For the last part observe that \(3, 6 \in B\), but \(2 \notin B\). Let \(D = (B \setminus \{3, 6\}) \cup \{2\}\). Then \(\#D = \#B -1 = 3k-1\) and \(r(D) = r(B) - \frac{1}{3} - \frac{1}{6} + \frac{1}{2} = r(B) = 1\). Finally, \(\lcm(D) \mid \lcm(B) = 3 \cdot 2^{2k-1}\) and once more lemma 1 shows \(\nu_3 \bigl( (3k-1)! \bigr) \ge k-1 \ge 1\) and \(\nu_2 \bigl( (3k-1)! \bigr) \ge 2k-1\), thus from lemma 2 applied to \(D\) we conclude that \(3k-1 \in X\) for \(k \ge 2\), the "\(-\)" part of the second claim.

Theorem 1. \(X = \N \setminus \{2\}\).

Proof. According to lemma 4, all natural numbers apart from possibly 1, 2 and 4 are in \(X\). We have \(4 \in X\) because \(4! = 24 = 12 + 6 + 4 + 2\) and \(1 \in X\) because \(1! = 1\). The number \(2!\) has only two divisors, 1 and 2, and \(1 + 2 \ne 2!\), hence \(2 \notin X\).

Roman Kogan solved this puzzle:

First, note that \(2\) is such an integer. It only has two distinct factors whose sum is \(3\).

Now, note that \(3! = 6 = 1 + 2 + 3 = \frac{3!}{2} + \frac{3!}{3} + \frac{3!}{6}\). To that end, define \(f_3 \colon 6Z \to \Z^3\) by \(n \mapsto (\frac{n}{2}, \frac{n}{3}, \frac{n}{6})\). That is, \(f_3\) gives a representation of a number divisible by \(6\) as a sum of \(3\) distinct factors of itself. We then proceed inductively, defining \(f_n \colon (n!)Z \to Z^n\) by

\begin{align*} f_4(n) & = \left( \frac{n}{2}, \frac{f_3(n)}{2} \right) \\ f_5(n) & = \left( \frac{n}{2}, \frac{f_4(n)}{2} \right) \\ f_6(n) & = \left( \frac{n}{2}, \frac{f_5(n)}{2} \right) \\ f_7(n) & = \left( \frac{n}{2}, \frac{n}{3}, \frac{f_4(n)}{6} \right) \\ & \vdots \\ f_{4k}(n) & = \left( \frac{n}{2}, \frac{f_{4k-1}(n)}{2} \right) \\ f_{4k+1}(n) & = \left( \frac{n}{2}, \frac{f_{4k}(n)}{2} \right) \\ f_{4k+2}(n) & = \left( \frac{n}{2}, \frac{f_{4k+1}(n)}{2} \right) \\ f_{4k+3}(n) & = \left( \frac{n}{2}, \frac{n}{3}, \frac{f_{4k+1}(n)}{6} \right) \\ \end{align*}

where \(k \geqslant 4\). It is not hard to verify that these definitions satisfy the claimed properties, i.e. \(f_k\) is well-defined as a map \(f_k \colon (k!)Z \to Z^k\), and that \(f_k(k!)\) gives a list of \(k\) distinct factors whose sum is \(k!\).

Credit

This puzzle is based on:

  • Savchev, Svetoslav; Andreescu, Titu. Mathematical Miniatures. Washington, D.C.: Mathematical Association of America, 2003. 53–54. Chapter 15.

Post a comment

RSS