## Adding factors of factorials

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.