Erdős Problem #293

Erdős Problem #293

1) ROUND-2 OBJECTIVE

I pursue path (A): prove a strictly stronger theorem than the Round-1 upper bound. The main unresolved gap after Round 1 was that the bound \[ v(k)\le u_k+1=c_0^{(1+o(1))2^k} \] came from controlling the largest denominator in a single decomposition, whereas the definition of $v(k)$ depends on the union of all denominators occurring in all $k$-term decompositions. The most promising Round-2 move is therefore a counting argument.

2) Round-1 FOUNDATION USED

I use the following Round-1 ingredients without reproving them.

• The set \[ D_k=\{n>1:\ \mbox{$n$ occurs as some denominator in a $k$-term decomposition of $1$}\}. \]
• The definition \[ v(k):=\min\{n>1:\ n\notin D_k\}. \]
• The Round-1 upper bound $v(k)\le u_k+1$, where $u_1=1$ and $u_{j+1}=u_j(u_j+1)$.
• The exact values $v(1)=2$, $v(2)=2$, $v(3)=4$, $v(4)=11$, $v(5)=17$, $v(6)=103$.

3) NEW INSIGHT / TOOL (ROUND-2)

The new ingredient is to replace "largest denominator" control by "number of solutions" control.

Let $F(k)$ be the number of strictly increasing $k$-tuples \[ 1<n_1<\cdots<n_k,\qquad \frac1{n_1}+\cdots+\frac1{n_k}=1. \] Each such solution contributes at most $k$ denominators to $D_k$. Hence $D_k$ is controlled by $F(k)$, not by the largest possible denominator alone. This yields the elementary but asymptotically much stronger inequality \[ v(k)\le kF(k)+2. \]

4) ATTACK PLAN (ROUND-2)

The exact Round-1 gap is that the previous upper bound was of size $c_0^{(1+o(1))2^k}$, whereas the best currently available upper bound for $F(k)$ is much smaller, namely $c_0^{(\frac15+o(1))2^k}$.

So the plan is:

• prove the elementary inequality $v(k)\le kF(k)+2$ from the Round-1 definition of $D_k$;
• import the known upper bound for $F(k)$;
• compare the resulting bound with the Round-1 bound.

This overcomes the Round-1 obstacle because it uses the global combinatorics of all $k$-term solutions, not just a denominator bound inside one solution.

5) WORK (ROUND-2)

Lemma 1. For every $k\ge 1$, \[ |D_k|\le kF(k). \]

Proof. List all $F(k)$ many $k$-term decompositions of $1$: \[ 1=\frac1{n_1^{(j)}}+\cdots+\frac1{n_k^{(j)}} \qquad (1\le j\le F(k)). \] For each fixed $j$, the solution contributes at most $k$ denominators to $D_k$. Therefore \[ D_k\subseteq \bigcup_{j=1}^{F(k)} \{n_1^{(j)},\ldots,n_k^{(j)}\}, \] so by the union bound \[ |D_k|\le \sum_{j=1}^{F(k)} k = kF(k). \] This proves the claim.

Lemma 2. If $S\subseteq \{2,3,4,\ldots\}$ is finite, then the least integer $>1$ not contained in $S$ is at most $|S|+2$.

Proof. Among the $|S|+1$ integers \[ 2,3,\ldots,|S|+2 \] at least one is not in $S$, because $S$ contains only $|S|$ elements. Hence the least missing integer is at most $|S|+2$.

Corollary 3. For every $k\ge 1$, \[ v(k)\le |D_k|+2\le kF(k)+2. \]

Proof. Apply Lemma 2 with $S=D_k$, then use Lemma 1.

External input. Elsholtz and Planitzer proved the upper bound \[ F(k)\le c_0^{(\frac15+o(1))2^k}, \qquad c_0=1.264085\ldots, \] for the number of $k$-term Egyptian fraction decompositions of $1$.

Theorem 4 (Round-2 upper bound). As $k\to\infty$, \[ v(k)\le c_0^{(\frac15+o(1))2^k}. \]

Proof. By Corollary 3, \[ v(k)\le kF(k)+2. \] Insert the Elsholtz--Planitzer bound for $F(k)$. Since the prefactor $k$ and the additive term $2$ are both negligible on the logarithmic scale $2^k$, they are absorbed into the $o(1)$ term in the exponent. Hence \[ v(k)\le c_0^{(\frac15+o(1))2^k}. \]

Comparison with Round 1. Round 1 gave \[ v(k)\le u_k+1=c_0^{(1+o(1))2^k}. \] Round 2 improves the constant in the exponent from $1$ to $\frac15$.

6) ADVERSARIAL VERIFICATION

• Possible double-counting issue. The same denominator may occur in many solutions, but this only helps: the union of all denominator-sets is never larger than the sum of their sizes.
• Possible off-by-one issue in the passage from $|D_k|$ to $v(k)$. This is why Lemma 2 gives $|D_k|+2$, not $|D_k|+1$: the relevant integers start at $2$, not $1$.
• Compatibility with small cases. If $D_k=\emptyset$, Corollary 3 gives $v(k)\le 2$, which is sharp for $k=1,2$.
• Interaction with Round 1. The new bound does not replace the Round-1 Sylvester/Takenouchi bound pointwise for every small $k$; it improves the asymptotic upper bound. The two estimates are compatible and may be combined as \[ v(k)\le \min\{u_k+1,\ kF(k)+2\}. \]

7) FINAL (EXACTLY ONE)

UNRESOLVED (BUT STRICTLY ADVANCED).

Round 2 proves a substantially stronger upper bound, \[ v(k)\le c_0^{(\frac15+o(1))2^k}, \] improving the Round-1 exponent constant from $1$ to $\frac15$. The lower bound is still only of the shape $\exp(ck^2)$, so the main asymptotic order of growth remains open.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 48%

9) REFERENCES

1. T. F. Bloom, Erdős Problem #293, erdosproblems.com/293, accessed 2026-03-07.
2. W. van Doorn and Q. Tang, The smallest denominator not contained in a unit fraction decomposition of $1$ with fixed length, arXiv:2512.22083, 2025.
3. C. Elsholtz and S. Planitzer, The number of solutions of the Erdős--Straus equation and sums of $k$ unit fractions, Proc. Roy. Soc. Edinburgh Sect. A 150 $2020$, 1401--1427.

Erdős Problem #293: independent continuation

1) OBJECTIVE AND SOURCE AUDIT

2) WORK: SEPARATING SMALL AND LARGE DENOMINATORS

For reproducible finite checks, suppose a partial decomposition has remaining rational mass $r>0$, needs $j\ge2$ terms, and its last chosen denominator is $b$. The next denominator $x$ must satisfy \[ \max\{b+1,\lfloor1/r\rfloor+1\}\le x\le\lfloor j/r\rfloor. \] The lower bound follows from $1/x<r$; the upper bound follows because all remaining denominators are at least $x$. Replace $(r,b,j)$ by $(r-1/x,x,j-1)$ recursively. When $j=1$, accept precisely when $r=1/x$ for an integer $x>b$. Each branch is finite and the inequalities retain every possible representation; induction on $j$ proves completeness.

Executed with exact fractions, this yields \[ \begin{array}{c|rrr} k&F(k)&|D_k|&v(k)\\\hline 2&0&0&2\\3&1&3&4\\4&6&15&11\\5&72&77&17 \end{array} \] The companion verification/root_checks.py reproduces these counts. No numerical denominator cutoff is assumed.

3) VERIFICATION AND FINAL

8) COMPLETION ESTIMATE

Erdős Problem #293

1. FORMAL RESTATEMENT

The statement as written in the prompt is ambiguous: if we literally define "$v(k)$ is the minimal integer that does not appear as a denominator in any $k$--term Egyptian fraction decomposition of $1$," then $1$ never appears as a denominator when $k\ge 2$ (because $1=1/1$ uses only one term), hence $v(k)=1$ for all $k\ge2$, which is trivial and not the intended problem.

Following the standard formulation used in the literature on this Erdős problem, I will interpret $v(k)$ as the smallest integer $>1$ that does not appear.

Definitions.

• For $k\ge 1$, let $\mathcal{D}_k$ be the set of integers $n>1$ for which there exists a strictly increasing $k$--tuple of integers \[ 2\le n_1< n_2<\cdots<n_k,\qquad \sum_{i=1}^k \frac1{n_i}=1, \] with $n\in\{n_1,\dots,n_k\}$.
• Define \[ v(k) := \min\{n>1: n\not\in \mathcal{D}_k\}. \]

Goal. Estimate the growth of $v(k)$ as $k\to\infty$ (e.g. find the best possible lower/upper bounds in terms of $k$, and ideally its correct order of magnitude).

2. QUICK LITERATURE/CONTEXT CHECK (only if browsing is available)

From the current problem page and recent literature:

• Bleicher--Erdős proved a factorial lower bound $v(k)\gg k!$.
• The Erdős Problems site records an elementary double--exponential upper bound of the shape \[ v(k)\le k\,c_0^{2^k}\qquad (c_0=1.264\dots), \] coming from known upper bounds on the largest denominator in a $k$--term decomposition.
• A recent preprint by van Doorn--Tang (Dec 2025) improves the lower bound to \[ v(k)\ge \exp(c k^2) \] for some absolute constant $c>0$, and proves monotonicity $\mathcal{D}_k\subseteq \mathcal{D}_{k+1}$ for $k\ge2$.

(These items are context; below I re-derive elementary bounds and compute small values exactly.)

3. ATTACK PLAN

1. Upper bounds from "largest denominator" control. Use Takenouchi/Curtiss-type results: among all $k$--term unit-fraction decompositions of $1$, the largest denominator is at most a specific Sylvester-type number $u_k$ defined by $u_1=1$ and $u_{j+1}=u_j(u_j+1)$. Then any integer $>u_k$ cannot belong to $\mathcal{D}_k$, yielding $v(k)\le u_k+1$.
2. Small cases. Compute $\mathcal{D}_k$ (hence $v(k)$) for small $k$ by exhaustive search, using the same upper bound on denominators to keep the search finite.
3. Lower bounds. Record what is known (factorial / $\exp(c k^2)$), and outline where one might try to improve: forcing congruence obstructions, controlling the structure of short Egyptian fraction identities, etc.

4. WORK

4.1 A Sylvester identity and the Sylvester numbers

Define the integer sequence $(u_k)_{k\ge1}$ by \[ u_1=1,\qquad u_{k+1}=u_k(u_k+1)\quad (k\ge1). \] Thus $u_2=2$, $u_3=6$, $u_4=42$, $u_5=1806$, $u_6=3263442$, etc.

This shows, in particular, that there exist $k$--term decompositions of $1$ whose largest denominator equals $u_k$.

4.2 Takenouchi/Curtiss bound and an immediate upper bound on $v(k)$

A classical theorem of Curtiss $1922$, refined by Takenouchi $1921$ in this context, states that no $k$--term Egyptian fraction decomposition of $1$ can have last denominator exceeding $u_k$.

Remark. For purposes of this writeup I use Theorem Theorem (Takenouchi--Curtiss bound on the largest denominator) as a known input (it is explicitly stated in modern expositions, e.g. Lagarias notes that the maximum possible last denominator equals the Sylvester number $u_k$).

Since $u_{k+1}=u_k^2+u_k$, the recursion implies $\log u_k$ grows on the order of $2^k$, i.e. $u_k$ (hence the bound on $v(k)$) is doubly exponential in $k$.

4.3 Exact small values $v(k)$ for $k\le 6$ (computer-assisted)

Using Theorem Theorem (Takenouchi--Curtiss bound on the largest denominator) to bound denominators (hence make the search finite), one can enumerate all solutions for fixed $k$ by backtracking with the standard pruning rule \[ \frac1{n_j}+\frac1{n_{j+1}}+\cdots+\frac1{n_k}\le \frac{k-j+1}{n_j}. \] I implemented such a search (exact rational arithmetic) and obtained the following.

(i) $k=1$. There is no solution with $n_1>1$, so $\mathcal{D}_1=\emptyset$ and $v(1)=2$.

(ii) $k=2$. There is no solution with distinct denominators, so $\mathcal{D}_2=\emptyset$ and $v(2)=2$.

(iii) $k=3$. The unique solution is \[ 1=\frac12+\frac13+\frac16, \] so $\mathcal{D}_3=\{2,3,6\}$ and therefore $v(3)=4$.

(iv) $k=4$. All $4$--term solutions are: \[ \begin{aligned} 1&=\frac12+\frac13+\frac17+\frac1{42},\\ 1&=\frac12+\frac13+\frac18+\frac1{24},\\ 1&=\frac12+\frac13+\frac19+\frac1{18},\\ 1&=\frac12+\frac13+\frac1{10}+\frac1{15},\\ 1&=\frac12+\frac14+\frac15+\frac1{20},\\ 1&=\frac12+\frac14+\frac16+\frac1{12}. \end{aligned} \] Hence \[ \mathcal{D}_4=\{2,3,4,5,6,7,8,9,10,12,15,18,20,24,42\}, \] and the smallest integer $>1$ missing is $11$, i.e. $v(4)=11$.

(v) $k=5$. Exhaustive enumeration with the bound $n_5\le u_5=1806$ yields $72$ solutions. Every integer $2\le m\le 16$ appears in at least one solution, but $17$ does not. Hence \[ v(5)=17. \]

(vi) $k=6$. Exhaustive enumeration with the bound $n_6\le u_6=3263442$ yields $2320$ solutions. The set $\mathcal{D}_6$ contains every integer $2\le m\le 102$ but does not contain $103$. Hence \[ v(6)=103. \] (As a sanity check that new denominators can appear when increasing $k$: $17\notin\mathcal{D}_5$ but $17\in\mathcal{D}_6$, e.g. $1=\frac12+\frac13+\frac1{12}+\frac1{17}+\frac1{68}+\frac1{102}$.)

5. VERIFICATION

• The $k=3$ and $k=4$ solution lists were verified by direct exact summation.
• For $k=5$ and $k=6$, completeness of the enumeration uses the input $n_k\le u_k$ from Theorem Theorem (Takenouchi--Curtiss bound on the largest denominator); within that finite search space, the backtracking algorithm checks every increasing $k$--tuple whose reciprocal sum could still reach $1$.
• The computed values $v(k)$ are nondecreasing for $k\ge2$ in this range (consistent with $\mathcal{D}_k\subseteq\mathcal{D}_{k+1}$).

6. FINAL (exactly ONE label and ONE sub-label)

LABEL: UNRESOLVED
SUBLABEL: (PARTIAL RESULTS)

• What I proved (complete arguments here):
  • The Sylvester telescoping identity giving an explicit $k$--term decomposition whose largest denominator is $u_k$.
  • Using the known Takenouchi/Curtiss bound $n_k\le u_k$, the immediate upper bound $v(k)\le u_k+1$.
  • Exact small values $v(k)$ for $k\le 6$ (computer-assisted, with justification of finiteness via $n_k\le u_k$).
• What remains missing for a full solution: an asymptotically sharp estimate of $v(k)$; in particular narrowing the current gap between known lower bounds (currently at least $\exp(c k^2)$) and double--exponential upper bounds.
• Most promising next steps: exploit the monotonicity $\mathcal{D}_k\subseteq\mathcal{D}_{k+1}$ and study which integers are "forced" into $\mathcal{D}_k$ via systematic splitting identities; on the lower-bound side, seek structural obstructions preventing small denominators from appearing (e.g. via congruence classes or density arguments for admissible denominators).

7. COMPLETION ESTIMATE

I would rate the above as 35% complete toward an "estimate" in the spirit of the problem: we have a clean (but very loose) doubly exponential upper bound and exact values for $k\le 6$, but no new asymptotically sharp growth law.