Erdős Problem #306

Problem #306

1) ROUND-2 OBJECTIVE

Path C (obstruction/correction). The full statement remains open, so the realistic round-2 target is a corrected proven statement covering genuinely new infinite subclasses. In this round I prove two such subclasses:

1. a graph-theoretic construction for many fractions whose denominator is a product of distinct primes;
2. a short explicit three-term criterion for certain unit fractions $1/p$ with $p$ prime.

These are strictly stronger than the isolated examples from Round 1.

2) Round-1 FOUNDATION USED

I use the following Round 1 facts.

1. If a rational number is representable as a sum of reciprocals of distinct semiprimes, then its reduced denominator is squarefree.
2. Round 1 recorded explicit semiprime decompositions for $1/3,1/5,1/2,2/5$, and a 48-term semiprime decomposition of $1$.

3) NEW INSIGHT / TOOL (ROUND-2)

The new insight is that the allowed denominators $p_i p_j$ naturally correspond to edges of a graph on the prime factors of the target denominator. This gives an immediate exact formula for a large family of fractions. A second new observation is that for prime $p$, a three-term semiprime decomposition of $1/p$ appears whenever \[ (q-1)(r-1)=p+1 \] for suitable distinct primes $q,r$.

4) ATTACK PLAN (ROUND-2)

The specific gap after Round 1 was the lack of any systematic constructive theorem beyond a few hand-picked examples. To close that gap I will:

1. prove a general graph formula for denominators $P=\prod p_i$;
2. extract from it a concrete infinite family for three-prime denominators;
3. prove a separate three-term criterion for $1/p$ and show that it subsumes several Round 1 examples.

5) WORK (ROUND-2)

Theorem A (graph construction). Let $p_1,\dots,p_t$ be distinct primes, and let \[ P:=p_1p_2\cdots p_t. \] For any simple graph $G$ on the vertex set $\{1,\dots,t\}$, define \[ a_G:=\sum_{\{i,j\}\in E(G)} \prod_{k\ne i,j} p_k. \] Then \[ \frac{a_G}{P}=\sum_{\{i,j\}\in E(G)} \frac{1}{p_i p_j}. \] In particular, every such $a_G/P$ has a semiprime Egyptian-fraction decomposition with distinct denominators.

Proof. For each edge $\{i,j\}$, \[ \frac{1}{p_i p_j}=\frac{1}{P}\prod_{k\ne i,j} p_k. \] Summing over all edges of $G$ gives exactly the claimed identity. Since different edges give different unordered pairs $\{i,j\}$, the denominators $p_i p_j$ are distinct semiprimes. $\square$

Corollary A1 (three-prime denominator family). Let $p,q,r$ be distinct primes. Then each of the seven fractions \[ \frac{p}{pqr},\ \frac{q}{pqr},\ \frac{r}{pqr},\ \frac{p+q}{pqr},\ \frac{p+r}{pqr},\ \frac{q+r}{pqr},\ \frac{p+q+r}{pqr} \] has a semiprime Egyptian-fraction decomposition. Indeed, \[ \frac{p}{pqr}=\frac1{qr}, \qquad \frac{q}{pqr}=\frac1{pr}, \qquad \frac{r}{pqr}=\frac1{pq}, \] \[ \frac{p+q}{pqr}=\frac1{pr}+\frac1{qr}, \qquad \frac{p+r}{pqr}=\frac1{pq}+\frac1{qr}, \qquad \frac{q+r}{pqr}=\frac1{pq}+\frac1{pr}, \] \[ \frac{p+q+r}{pqr}=\frac1{pq}+\frac1{pr}+\frac1{qr}. \] This gives an explicit infinite family of squarefree denominators with three prime factors for which several nontrivial numerators are provably representable.

Theorem B (a three-term criterion for $1/p$). Let $p,q,r$ be distinct primes. If \[ (q-1)(r-1)=p+1, \] then \[ \frac1p=\frac1{pq}+\frac1{pr}+\frac1{qr}. \] Equivalently, whenever \[ qr-q-r=p, \] we obtain a three-term semiprime Egyptian-fraction decomposition of $1/p$.

Proof. The condition $(q-1)(r-1)=p+1$ expands to \[ qr-q-r=p. \] Therefore \[ \frac1{pq}+\frac1{pr}+\frac1{qr} =\frac{p+q+r}{pqr} =\frac{qr}{pqr} =\frac1p. \] The denominators are distinct semiprimes because $p,q,r$ are distinct primes. $\square$

Examples from Theorem B.

1. If $p+2$ is prime, then taking $q=2$ and $r=p+2$ gives \[ \frac1p=\frac1{2p}+\frac1{p(p+2)}+\frac1{2(p+2)}. \] Thus \[ \frac1{17}=\frac1{34}+\frac1{38}+\frac1{323}. \]
2. If $(p+3)/2$ is prime, then taking $q=3$ and $r=(p+3)/2$ gives \[ \frac1p=\frac1{3p}+\frac1{p(p+3)/2}+\frac1{3(p+3)/2}. \] Thus \[ \frac1{11}=\frac1{21}+\frac1{33}+\frac1{77}, \qquad \frac1{19}=\frac1{33}+\frac1{57}+\frac1{209}. \]
3. Taking $(p,q,r)=(23,5,7)$ gives \[ \frac1{23}=\frac1{35}+\frac1{115}+\frac1{161}. \]

These formulas subsume several of the isolated small examples from Round 1 and show that there is a genuine infinite-pattern mechanism behind them.

6) ADVERSARIAL VERIFICATION

1. Are the denominators really distinct in Theorem A? Yes. Different edges correspond to different unordered pairs $\{i,j\}$, and for distinct primes the products $p_i p_j$ are distinct.
2. Is Theorem A compatible with the original squarefree-denominator hypothesis? Yes. The target denominator before reduction is $P=\prod p_i$, which is squarefree; after reduction, the denominator still divides $P$, so it remains squarefree.
3. Could Theorem B fail because one denominator repeats another? No. The theorem explicitly assumes $p,q,r$ are distinct primes, so $pq,pr,qr$ are pairwise distinct semiprimes.
4. Did I accidentally claim necessity in Theorem B? No. The theorem is only a sufficient criterion. It does not classify all three-term semiprime decompositions of $1/p$.
5. Does any of this solve the full problem? No. The full question asks for every rational with squarefree denominator. The new theorems produce large explicit subclasses, but not all of them.

7) FINAL (EXACTLY ONE)

UNRESOLVED (BUT STRICTLY ADVANCED). Round 2 proves two new constructive theorems. First, the graph construction gives a systematic infinite family of representable rationals with squarefree denominator $P=\prod p_i$. Second, Theorem B gives a clean explicit three-term criterion for many prime-denominator unit fractions $1/p$. This is a genuine step beyond the Round 1 list of isolated examples, but it still falls short of the full conjecture for arbitrary $a/b$.

8) COMPLETION ESTIMATE

COMPLETION: 34%

9) REFERENCES

• Round 1 output in this conversation (used as fixed foundation).
• T. F. Bloom, Erdős Problem #306.
• S. Butler, P. Erdős and R. Graham, Egyptian fractions with each denominator having three distinct prime divisors.
• T. Watanabe, New examples of the representation of $1$ by the sum of reciprocals of semiprime numbers, arXiv:2009.03275.

Erdős Problem #306: independent continuation

Date: 23 September 2026. Source versions read in full: 306.tex in gpt_pro_5.4.

1) OBJECTIVE AND SOURCE AUDIT

The question concerns every positive rational with squarefree reduced denominator, using distinct products of two distinct primes. The supplied graph sum identity is correct but selects the numerator rather than representing an arbitrary prescribed one. I use the same graph to obtain necessary cancellation constraints on any putative representation.

2) WORK: WHERE LEAVES ARE ALLOWED

Suppose \[ a/b=\sum_{\{p,q\}\in E(G)}\frac1{pq},\qquad (a,b)=1, \] where $G$ is a finite simple graph on its nonisolated prime vertices. Put $P=\prod_{p\in V(G)}p$. Necessarily $b\mid P$. Multiplying the equation by $P$ and reducing modulo a vertex prime $p\nmid b$ gives \[ \sum_{q\in N_G(p)}q^{-1}\equiv0\pmod p. \tag{1} \] Indeed, the left side $aP/b$ is divisible by $p$, as are all edge contributions not incident with $p$. Dividing the remaining congruence by $P/p$, which is invertible modulo $p$, proves $1$.

In particular every leaf prime must divide $b$: a single inverse cannot vanish. Hence a representation of an integer has minimum graph degree at least two. A representation with prime reduced denominator also cannot have a forest as its support graph. Every nonempty finite forest has at least two leaves, whereas at most one vertex prime can divide such a denominator. Thus these representations must use at least one cycle, not merely a tree of independently introduced primes.

More generally every nonempty tree component requires at least two distinct prime factors of $b$ among its leaves. If the graph has $t$ tree components, then $2t\le\omega(b)$. This is useful before any large-integer factorization in a proposed construction.

3) ADVERSARIAL VERIFICATION

The constraints are necessary only. A cycle does not automatically represent the required rational. The source's triangle identity passes this test, but provides no decomposition for arbitrary $a/b$. Also, repeating the same identity to represent multiples is invalid if it repeats denominators; simplicity of $G$ records that restriction.

7) FINAL AND REFERENCE

UNRESOLVED. This attempt supplies structural obstructions, not a general construction. The indexed official discussion reports a claimed formalized solution; I have not checked its axiom boundary or proof and do not adopt that claim. The saved repository status is still open. Target checked at https://www.erdosproblems.com/306.

8) COMPLETION ESTIMATE

COMPLETION: 8% This is a subjective estimate of progress toward the entire stated problem, not a probability that the conjecture or an unverified proof is correct.

Problem #306

1) FORMAL RESTATEMENT

Let $a/b\in\mathbb{Q}_{>0}$ with $b$ squarefree. The question asks whether there always exist an integer $k\ge 1$ and integers \[ 1<n_1<n_2<\cdots<n_k \] so that \[ \frac{a}{b} = \frac{1}{n_1}+\frac{1}{n_2}+\cdots+\frac{1}{n_k}, \] and each denominator $n_i$ is the product of two distinct primes (equivalently, $n_i$ is a squarefree semiprime).

2) QUICK LITERATURE/CONTEXT CHECK

From the ErdosProblems #306 entry and the Simons Foundation discussion of Butler--Graham $2015$:

• Erdős and Graham conjectured that every integer can be written as a sum of distinct unit fractions whose denominators have exactly two distinct prime factors; this "two primes" version remains open.
• Butler and Graham proved the "three distinct prime factors" version for integers (published 2015).
• An explicit identity (attributed to Graham/Erdős) expresses $1$ as a sum of $48$ reciprocals of semiprimes.

The general question here asks for  every rational with squarefree denominator, which appears to remain open.

3) ATTACK PLAN

1. Necessary conditions. Identify obvious obstructions (e.g. why $b$ being squarefree is necessary).
2. Explicit base identities. Use known identities (e.g. a semiprime decomposition of $1$) to generate many other rationals via subset sums.
3. Search small cases. For small squarefree $b$ and $a$, search for explicit decompositions with bounded denominators.
4. General strategy. If a systematic method existed, it would likely resemble a "covering" argument: build a finite set of allowed denominators whose reciprocal sum is an integer and whose subset sums are rich enough to hit all residue classes needed.

4) WORK

4.1. Squarefree denominator is necessary.

If each $n_i$ is a product of two distinct primes, then each $n_i$ is squarefree. Let $L=\operatorname{lcm}(n_1,\dots,n_k)$. Since the lcm of squarefree integers is squarefree, $L$ is squarefree. Writing the sum over the common denominator $L$ gives $ \sum_i 1/n_i = m/L $ for some integer $m$, hence the reduced denominator divides $L$ and is also squarefree. Therefore any rational representable as such a sum must have squarefree denominator in lowest terms; this justifies the hypothesis on $b$.

4.2. An explicit 48-term semiprime decomposition of $1$.

The Simons Foundation article (Dec 10, 2015) records the identity \[ 1=\sum_{j=1}^{48} \frac{1}{d_j} \] with the following $48$ denominators, each a product of two distinct primes: \begin{align*} &6,21,34,46,58,77,87,115,155,215,287,391,\\ &10,22,35,51,62,82,91,119,187,221,299,689,\\ &14,26,38,55,65,85,93,123,203,247,319,731,\\ &15,33,39,57,69,86,95,133,209,265,323,901. \end{align*} (One can verify by direct exact arithmetic that the sum of reciprocals is $1$.)

4.3. Many other rationals via subset sums (explicit examples).

Because the above list sums to $1$, any subset of the $48$ denominators gives a rational with squarefree denominator. In particular, the following exact identities hold (all denominators are semiprimes and distinct): \begin{align*} \frac{1}{3} &= \frac{1}{6}+\frac{1}{10}+\frac{1}{15},\\ \frac{1}{5} &= \frac{1}{10}+\frac{1}{14}+\frac{1}{35},\\ \frac{1}{2} &= \frac{1}{6}+\frac{1}{10}+\frac{1}{15}+\frac{1}{21}+\frac{1}{26}+\frac{1}{35}+\frac{1}{39}+\frac{1}{65}+\frac{1}{91},\\ \frac{2}{5} &= \frac{1}{6}+\frac{1}{10}+\frac{1}{14}+\frac{1}{38}+\frac{1}{57}+\frac{1}{95}+\frac{1}{133}. \end{align*} From these and the $1$-identity one can also get, e.g., $\frac{2}{3}=1-\frac{1}{3}$ by taking the complement of the denominators $\{6,10,15\}$ inside the 48-term representation of $1$; similarly $\frac{3}{5}=1-\frac{2}{5}$. These give (long but explicit) semiprime Egyptian decompositions of $2/3$ and $3/5$.

4.4. Computational small-case search.

A bounded search over semiprime denominators up to $5000$ found short decompositions for several small fractions (including the ones displayed above), suggesting the conjecture is plausible for small squarefree denominators. However, no general constructive proof for arbitrary squarefree $b$ was obtained.

5) VERIFICATION

• The "squarefree denominator" necessity argument is rigorous: the lcm of squarefree integers is squarefree and any reduced denominator divides the lcm.
• Each displayed denominator in the 48-term list factors as $pq$ with $p\ne q$ primes (e.g. $6=2\cdot 3$, $21=3\cdot 7$, $34=2\cdot 17$, etc.).
• The identities for $1/3$, $1/5$, $1/2$, $2/5$ can be verified by clearing denominators (or exact arithmetic); for instance $1/6+1/10+1/15=(5+3+2)/30=10/30=1/3$.

6) FINAL

UNRESOLVED.

1. Progress achieved. I proved that squarefree denominators are necessary, recorded an explicit 48-term decomposition of $1$ into reciprocals of semiprimes, and exhibited explicit decompositions for several other rationals (including $1/2,1/3,1/5,2/5$, and hence also $2/3,3/5$ via complements).
2. Where it got stuck. No method was found to handle an arbitrary target $a/b$ with arbitrary squarefree $b$.
3. What next steps would look like. One would try to develop a general "covering"/iteration scheme (similar in spirit to Butler--Graham for the three-prime case) that generates, for each squarefree $b$, a finite set of allowed denominators whose reciprocal sums can realize every residue class $a\bmod b$ (after scaling to a common squarefree denominator).
4. Falsifiable conjecture. For every squarefree $b$ and every $1\le a<b$, there exists a semiprime Egyptian fraction expansion of $a/b$ with distinct denominators.

7) COMPLETION ESTIMATE

To resolve the problem affirmatively, one needs a uniform construction that takes $(a,b)$ with squarefree $b$ and outputs an explicit semiprime-denominator Egyptian expansion. To resolve it negatively, one needs an explicit squarefree $b$ and $a$ for which one can prove that no such expansion exists (e.g. via congruence obstructions), which would require identifying an invariant that all semiprime-denominator sums satisfy but some $a/b$ violates.