๐Ÿงฎ Brain Teaser

The Integers That Sum to Their Product

Find all finite multisets of positive integers greater than 1 whose sum equals their product.

In other words, find all ways to choose positive integers a1โ‰คa2โ‰คโ‹ฏโ‰คana_1 \leq a_2 \leq \cdots \leq a_n, each at least 2, such that

a1+a2+โ‹ฏ+an=a1โ‹…a2โ‹ฏan.a_1 + a_2 + \cdots + a_n = a_1 \cdot a_2 \cdots a_n.

List all solutions (there are only a few).

number theorycaseworkbounding argumentelegant identity

Answer: The Integers That Sum to Their Product

Key Idea / Intuition

The product grows much faster than the sum, so large numbers or many factors quickly make the product dwarf the sum. This means we only need to search a tiny region. The clever move is to bound nn (the number of terms) by noticing that if all aiโ‰ฅ2a_i \geq 2, the product is at least 2n2^n while the sum is at most 2nโ‹…maxโก(ai)2n \cdot \max(a_i) โ€” forcing nn to be small. Then we handle small nn by direct casework.


Formal Proof / Solution

Step 1: Bound the number of terms.

If we have nn integers each at least 2, then: Productโ‰ฅ2n,Sumโ‰คnโ‹…anโ‰คnโ‹…Product/2nโˆ’1.\text{Product} \geq 2^n, \qquad \text{Sum} \leq n \cdot a_n \leq n \cdot \text{Product}/2^{n-1}.

More directly: with all aiโ‰ฅ2a_i \geq 2, Sum=a1+โ‹ฏ+anโ‰คnโ‹…an,Product=a1โ‹ฏanโ‰ฅ2nโˆ’1an.\text{Sum} = a_1 + \cdots + a_n \leq n \cdot a_n, \quad \text{Product} = a_1 \cdots a_n \geq 2^{n-1} a_n.

So the equation forces nโ‹…anโ‰ฅ2nโˆ’1ann \cdot a_n \geq 2^{n-1} a_n, giving nโ‰ฅ2nโˆ’1n \geq 2^{n-1}. This only holds for nโ‰ค2n \leq 2 ... wait, let's be more careful. We need sum == product, so: Product=Sumโ‰คnโ‹…an.\text{Product} = \text{Sum} \leq n \cdot a_n. But also Productโ‰ฅ2nโˆ’1โ‹…an\text{Product} \geq 2^{n-1} \cdot a_n (since there are nโˆ’1n-1 other factors each โ‰ฅ2\geq 2).

So 2nโˆ’1anโ‰คnโ‹…an2^{n-1} a_n \leq n \cdot a_n, giving 2nโˆ’1โ‰คn2^{n-1} \leq n.

Checking: n=1n=1: 1โ‰ค11 \leq 1 โœ“; n=2n=2: 2โ‰ค22 \leq 2 โœ“; n=3n=3: 4โ‰ค34 \leq 3 โœ—.

So nโ‰ค2n \leq 2 only? But wait โ€” we're assuming all are โ‰ฅ2\geq 2. Let me redo more carefully for n=3n=3.

Actually 2nโˆ’1โ‰คn2^{n-1} \leq n fails for nโ‰ฅ3n \geq 3, so there are no solutions with nโ‰ฅ3n \geq 3 when all aiโ‰ฅ2a_i \geq 2? Let's verify directly.

Step 2: Case n=1n = 1.

a1=a1a_1 = a_1. Any single integer works trivially, but the product equals a1a_1 and sum equals a1a_1, so every single integer is a solution. However, this is trivial/degenerate. Most formulations require nโ‰ฅ2n \geq 2.

Step 3: Case n=2n = 2.

a1+a2=a1a2a_1 + a_2 = a_1 a_2. Rearrange: a1a2โˆ’a1โˆ’a2=0โ€…โ€ŠโŸนโ€…โ€Š(a1โˆ’1)(a2โˆ’1)=1.a_1 a_2 - a_1 - a_2 = 0 \implies (a_1 - 1)(a_2 - 1) = 1. Since a1,a2โ‰ฅ2a_1, a_2 \geq 2, we need a1โˆ’1=a2โˆ’1=1a_1 - 1 = a_2 - 1 = 1, so a1=a2=2a_1 = a_2 = 2.

Check: 2+2=4=2ร—22 + 2 = 4 = 2 \times 2. โœ“

Step 4: Case n=3n = 3.

a1+a2+a3=a1a2a3a_1 + a_2 + a_3 = a_1 a_2 a_3 with 2โ‰คa1โ‰คa2โ‰คa32 \leq a_1 \leq a_2 \leq a_3.

Take a1=2a_1 = 2: then 2+a2+a3=2a2a32 + a_2 + a_3 = 2a_2 a_3, so a2+a3โˆ’2a2a3=โˆ’2a_2 + a_3 - 2a_2 a_3 = -2, i.e., 2a2a3โˆ’a2โˆ’a3=2.2a_2 a_3 - a_2 - a_3 = 2. With a2=2a_2 = 2: 4a3โˆ’2โˆ’a3=2โ‡’3a3=44a_3 - 2 - a_3 = 2 \Rightarrow 3a_3 = 4. Not an integer.

With a2=3a_2 = 3: 6a3โˆ’3โˆ’a3=2โ‡’5a3=5โ‡’a3=16a_3 - 3 - a_3 = 2 \Rightarrow 5a_3 = 5 \Rightarrow a_3 = 1. But a3โ‰ฅa2=3a_3 \geq a_2 = 3, contradiction.

With a2โ‰ฅ4a_2 \geq 4: LHS โ‰ฅ2โ‹…4โ‹…4โˆ’4โˆ’4=24>2\geq 2 \cdot 4 \cdot 4 - 4 - 4 = 24 > 2. No solution.

Take a1=3a_1 = 3: 3+a2+a3=3a2a33 + a_2 + a_3 = 3a_2 a_3. With a2=3a_2 = 3: 3a3โ‹…3โˆ’3โˆ’a3=3โ‡’9a3โˆ’a3=6โ‡’a3=3/43a_3 \cdot 3 - 3 - a_3 = 3 \Rightarrow 9a_3 - a_3 = 6 \Rightarrow a_3 = 3/4. No.

Larger a1a_1 only makes the product larger. No solutions for n=3n=3.

Wait โ€” I made an error in Step 1. Let me recheck: for n=3n=3 with a 1 included.

Actually the problem states each aiโ‰ฅ2a_i \geq 2, so indeed n=3n=3 has no solutions as shown.

Step 5: Case nโ‰ฅ3n \geq 3 โ€” general argument.

With all aiโ‰ฅ2a_i \geq 2 and nโ‰ฅ3n \geq 3: the product Pโ‰ฅ2nP \geq 2^n but the sum Sโ‰คnโ‹…amaxโกS \leq n \cdot a_{\max}. Since P=a1โ‹ฏanโ‰ฅ2nโˆ’1anP = a_1 \cdots a_n \geq 2^{n-1} a_n, we need 2nโˆ’1anโ‰คS=P=a1โ‹ฏan2^{n-1} a_n \leq S = P = a_1 \cdots a_n, yet also Sโ‰คnanS \leq n a_n, so 2nโˆ’1โ‰คn2^{n-1} \leq n, which fails for nโ‰ฅ3n \geq 3. Hence no solutions.


Complete Solution Set

The only solution (with all integers โ‰ฅ2\geq 2 and nโ‰ฅ2n \geq 2) is:

(2,ย 2):2+2=2ร—2=4.\boxed{(2,\ 2) \quad : \quad 2 + 2 = 2 \times 2 = 4.}

If we allow n=1n = 1: every single integer aa satisfies a=aa = a trivially (degenerate).


Why This Is Beautiful

The factoring trick (a1โˆ’1)(a2โˆ’1)=1(a_1-1)(a_2-1) = 1 is a classic rearrangement. The bounding argument 2nโˆ’1โ‰คn2^{n-1} \leq n shows in one line why large nn is impossible โ€” the product wins. The problem has exactly one nontrivial answer, which is both surprising and satisfying.

Source: Mathematical folklore / Putnam warmup

Type: PutnamSource: Mathematical folklore / Putnam warmupEdit on GitHub โ†—