Erdoes #1107 - working report - Erdős Problem a Day

Erdős problem #1107 — wave w034

Date of live check and computation: 2026-07-29 (UTC).

The labels required by the task are used as follows:

(a) elementary-rigorous: a proof is given here from definitions.
(b) rigorous-modulo-named-theorem: the claim uses the named published

theorem.

(c) plausible/structural-unverified: a heuristic, a non-exhaustive

literature conclusion, or a proposed analytic route.

(d) computational-only: an exhaustive finite computation, not a

statement about all sufficiently large integers.

0. Mandatory live-page audit

I fetched both the problem page and its discussion thread through the Bright Data cloud-browser route on 2026-07-29. Direct curl was not used as the authority. The relevant URLs are:

<https://www.erdosproblems.com/1107>
<https://www.erdosproblems.com/forum/thread/1107>

The live page's verbatim problem statement is:

Let $r\geq 2$. A number $n$ is $r$-powerful if for every prime $p$ which divides $n$ we have $p^r\mid n$. Is every large integer the sum of at most $r+1$ many $r$-powerful numbers?

(d: live-page observation) The status is OPEN. The page says this is open and cannot be resolved by a finite computation. It lists the following known information:

The question was given in the 1986 Oberwolfach problem book as a problem

of Erdős and Ivić.

The answer is true for $r=2$, proved by Heath-Brown [He88], with problem

[941] linked for that case.

Problem [940] is linked for the related question with at most $r$

summands.

The external-data section lists OEIS A056828, A392342, and A392343 as

possible related sequences.

(d: live-page observation) The live participation/claim state is:

claimed proofs: 0;
comment activity claiming a partial or complete solution: none;
interested in collaborating: None;
currently working: None;
likes: Dogmachine;
“looks difficult”, “looks tractable”, “results could be formalisable”, and

“working on formalising”: None in each case.

(d: live-page observation) There is one comment, by TerenceTao at 16:32 on 17 November 2025:

From context I would assume "every integer" should be "every sufficiently large integer".

The thread immediately adds:

(The site has been updated to address this comment.)

Thus neither stop condition was present: there is no claimed proof/solution and no current worker. I proceeded.

1. What was found

There are three concrete outputs.

(a) There is no obstruction modulo any fixed modulus: for every

$m$, every residue class modulo $m$ is a sum of at most three residue classes containing $r$-powerful integers. Since $3\leq r+1$, a finite congruence search cannot disprove the conjecture. A proof is in Section 4.

(d) An exact bitset computation gives the complete representability

table through $10^7$ for $r=3$, and through $10^8$ for $4\leq r\leq8$. In particular, every integer in $[150272,10^8]$ is the sum of at most five 4-full numbers. The analogous certified finite suffixes for $r=5,6,7,8$ are in Section 2.

(a) Every $r$-powerful integer has an exact, unique canonical

parametrisation. It turns the problem into a union of diagonal degree-$r$ equations with only $r+1$ variables. This identifies the analytic estimate still missing; see Sections 5–6.

None of these proves eventual coverage for any $r\geq3$.

2. Exact finite computation

2.1 Results

Let

A_r(N)=\{a:1\leq a\leq N,\;a\text{ is }r\text{-powerful}\}.

The “misses” column counts positive $n\leq N$ which are not sums of at most $r+1$ members of $A_r(N)$. A summand can be repeated. The zero used by the program is only padding for “at most”; it is not counted as a positive $r$-powerful number.

(d) Exact exhaustive table

| $r$ | cutoff $N$ | $\lvert A_r(N)\rvert$ | misses in $[1,N]$ | largest miss $\leq N$ | certified covered suffix | |---:|---:|---:|---:|---:|---:| | 3 | 10,000,000 | 713 | 45 | 2,039 | $[2,040,10,000,000]$ | | 4 | 100,000,000 | 464 | 1,318 | 150,271 | $[150,272,100,000,000]$ | | 5 | 100,000,000 | 211 | 6,018 | 449,560 | $[449,561,100,000,000]$ | | 6 | 100,000,000 | 121 | 37,036 | 4,034,495 | $[4,034,496,100,000,000]$ | | 7 | 100,000,000 | 77 | 274,426 | 41,892,928 | $[41,892,929,100,000,000]$ | | 8 | 100,000,000 | 52 | 1,887,385 | 99,954,776 | $[99,954,777,100,000,000]$ |

The $r=8$ largest miss lies very close to the cutoff, so it is especially important not to read that row as evidence that 99,954,776 is a global last exception. Every “largest” entry in this table is qualified by its finite cutoff.

For $r=3$, the 45 misses found from scratch are:

\begin{split} &5,6,7,12,13,14,15,20,21,22,23,31,38,39,46,47,53,58,69,77,79,85,\\ &95,101,103,111,175,196,212,228,231,247,327,444,458,490,606,662,\\ &860,975,1167,1470,1821,1967,2039. \end{split}

This agrees with OEIS A392342, but the verifier does not download or use the OEIS list.

2.2 Layer counts

The following are exact counts of positive integers at most $N$ representable with at most $k$ summands. Entry zero is included merely to show the indexing.

(d) Exact layer table

| $r,N$ | counts for $k=0,1,\ldots,r+1$ | |---|---| | $3,10^7$ | $0,713,204292,8881821,9999955$ | | $4,10^8$ | $0,464,94293,9555487,98712504,99998682$ | | $5,10^8$ | $0,211,19806,1075929,29391066,99647566,99993982$ | | $6,10^8$ | $0,121,6491,205590,4145453,43729370,98482450,99962964$ | | $7,10^8$ | $0,77,2622,53708,750606,7397528,44474702,95080280,99725574$ | | $8,10^8$ | $0,52,1237,18309,191523,1508112,9067169,38143527,84665785,98112615$ |

2.3 Boundary witnesses

The nonrepresentability of each preceding integer is computational, but the displayed representations themselves can be checked by hand.

(a) Explicit representations immediately after four computed last misses

\begin{aligned} 150272={}&16+256+50000+100000,\\ 449561={}&729+200000+248832,\\ 4034496={}&64+128+512+1024+32768+4000000,\\ 41892929={}&16384+279936+5764801+35831808. \end{aligned}

Their factorizations are:

for $r=4$:

$16=2^4$, $256=2^8$, $50000=2^4 5^5$, $100000=2^5 5^5$;

for $r=5$:

$729=3^6$, $200000=2^6 5^5$, $248832=2^{10}3^5$;

for $r=6$:

$64=2^6$, $128=2^7$, $512=2^9$, $1024=2^{10}$, $32768=2^{15}$, $4000000=2^8 5^6$;

for $r=7$:

$16384=2^{14}$, $279936=2^7 3^7$, $5764801=7^8$, $35831808=2^{14}3^7$.

Every prime exponent is at least the relevant $r$, and the number of summands is at most $r+1$.

2.4 Reproducibility fingerprints

Bits are stored little-endian, with bit $n$ indicating representability of $n$. The SHA-256 hash is taken over exactly $\lceil(N+1)/8\rceil$ bytes.

(d) Reachable-bitset hashes

| $r,N$ | SHA-256 | |---|---| | $3,10^7$ | c52eec526ab7564f8a361367ca75f05f41604e3148b4fb1efa8084522b4edc77 | | $4,10^8$ | 22b66404a9eaf38e0fd017740c872379dbd503f50a0fed96aee06e19f77c3c55 | | $5,10^8$ | 4ddcf98ec5b6d82b5d3eb41878f7691dcb9a168b92143c8e4bcbdd8549427e72 | | $6,10^8$ | 683e61d6c88e9a4940d911679490fc59172b941b4ba0242567bb3e5fc9bc7b6d | | $7,10^8$ | 487c76d10d375cf93c7801070f85efb7d8b68f03063fa6994dc5ed58706fbba3 | | $8,10^8$ | 77cf207094316160965f43034973dc2722bb356c287d3f9f96641c1c8adfab78 |

The hashes of the comma-separated increasing exception lists are, respectively:

r=3  ed6a284a3990b9862b0c5315478a8ef89f1b8f0b4f71cdf98f6f644aab1a3465
r=4  1c22814928be710da33478f0a8dff7bb72b70751a280a539614ba97e54a49c7d
r=5  76cbae6c3517f93c679086ead9f49b708b3ad96d25754f3c37ae23166fcbd1bd
r=6  a8295a3fcc3af74b8c2034d86dc11c44138b2919bbf188a79a78efca07823c8b
r=7  356eca32470f120b15caeb556d1259f30c55e61e1683e40d1e1c514ebcb1f774
r=8  409b4384887b6c7ed3df567bf7e27d35a047344d453af11db66ed6b84df627e1

3. Why the finite algorithm is exact

3.1 Enumeration of $r$-powerful numbers

(a) If $n\leq N$ is $r$-powerful and $p\mid n$, then $p^r\leq n\leq N$, so $p\leq\lfloor N^{1/r}\rfloor$. The verifier lists those primes. It recursively chooses distinct primes in increasing order and, for every chosen prime, tries exponents $r,r+1,r+2,\ldots$ until the product exceeds $N$.

Every generated integer is $r$-powerful. Conversely, the ordered prime factorisation of every $r$-powerful $n\leq N$ determines exactly one recursive branch and one exponent choice at each branch. Thus the enumeration is complete and duplicate-free.

3.2 Sumset recurrence

Let $R_0=\{0\}$, and define

R_k=R_{k-1}\cup \{x+a:x\in R_{k-1},\ a\in A_r(N),\ x+a\leq N\}.

(a) Induction on $k$ shows that $R_k$ is exactly the set of integers in $[0,N]$ which are sums of at most $k$ positive $r$-powerful integers. Hence the complement of $R_{r+1}$ in $[1,N]$ is exactly the finite exception set claimed above.

The implementation represents $R_k$ by a Python integer. Shifting it left by $a$ represents $R_{k-1}+a$; bitwise OR takes the union. The at-most-two layer is independently constructed by directly marking every unordered pair sum in a packed byte array. Subsequent layers use the shift/OR recurrence.

3.3 Independent checks

Before the large cases, the saved verifier performs all of the following:

(d) It compares the recursive $r$-powerful generator against

definition-level trial division for every $n\leq12000$ and $2\leq r\leq7$.

(d) It compares the packed-bit recurrence against an ordinary Python

set recurrence through 3,000 for the same $r$-range.

(d) It decomposes and reconstructs every small generated number using

the canonical form proved in Section 5, checking squarefreeness and pairwise coprimality.

(d) It exhaustively verifies the unit-sum modular lemma of Section 4

for every modulus $m\leq300$, independently of its all-$m$ proof.

(d) It verifies the unit-to-$r$-powerful construction for

$m\leq100$ and $2\leq r\leq8$.

(d) It trial-factors every displayed boundary witness.

The full saved run ended with ALL CHECKS PASSED. On this VM (Intel Xeon Platinum 8259CL), /usr/bin/time reported:

TOTAL elapsed=54.23 user=48.58 sys=5.62 maxrss_kb=130472

4. A uniform theorem: no congruence obstruction

Lemma 1: three units suffice

(a) For every modulus $m\geq1$, every residue class modulo $m$ is a sum of at most three units modulo $m$.

Proof. It is enough to prescribe residues modulo every prime power $p^e\Vert m$ and use the Chinese remainder theorem.

If $m$ is odd, write a target $x$ as $u+(x-u)$. For each

$p\mid m$, choose $u\bmod p$ different from both $0$ and $x\bmod p$. This is possible because $p\geq3$. Then both summands are units modulo every $p^e$, hence modulo $m$.

If $m$ is even and $x$ is even, the same construction works, with

$u$ chosen odd at the 2-primary component; then $x-u$ is also odd.

If $m$ is even and $x$ is odd, use three units. Modulo 2 their sum is

automatically odd. For an odd prime $p$, every residue is a sum of three nonzero residues: among the $(p-1)^2$ nonzero pairs $(u,v)$, at most $p-1$ make $x-u-v=0$, leaving $(p-1)(p-2)>0$ choices. Choose these componentwise and apply CRT.

This proves the lemma.

Lemma 2: every unit class contains an $r$-powerful integer

(a) Fix a unit $u\bmod m$, and choose a positive representative $U$. Let $E\geq r$ satisfy

E\equiv1\pmod{\varphi(m)}.

Euler's theorem gives $U^E\equiv U\equiv u\pmod m$. Every prime exponent in $U^E$ is $E$ times a positive integer and is therefore at least $r$. Thus $U^E$ is $r$-powerful.

Consequence

(a) Apply Lemma 2 to each of the at most three units supplied by Lemma

Every residue modulo every $m$ is the sum of at most three

$r$-powerful integers. Since $r\geq2$, this uses at most $r+1$ summands.

Therefore:

no modulus has a residue class omitted by all sums allowed in problem

#1107;

a modular counterexample search cannot falsify the conjecture;
local solubility alone still does not prove global representation or a

uniform positive singular-series bound.

The theorem rules out one standard counterexample route completely, rather than merely reporting that a search over small moduli found nothing.

5. Exact canonical reduction

5.1 Unique parametrisation

(a) Every positive $r$-powerful integer $n$ has a unique expression

n=a^r\prod_{j=1}^{r-1} b_j^{\,r+j}, \tag{1}

where $a\geq1$, every $b_j$ is squarefree, and the $b_j$ are pairwise coprime.

Proof. For each $p^e\Vert n$, write $e=qr+j$ with $0\leq j<r$.

If $j=0$, put $p^q$ into $a$.
If $1\leq j<r$, then $q\geq1$; put $p^{q-1}$ into $a$ and put

$p$ into $b_j$.

The contribution is respectively $p^{qr}$ or $p^{(q-1)r+r+j}=p^e$. A prime enters at most one $b_j$, proving the squarefree and coprimality conditions. The Euclidean division of each exponent by $r$ also proves uniqueness. Conversely, every product in (1) is $r$-powerful.

5.2 Exact reformulation of #1107

(a) Allowing omitted terms as zero padding, #1107 asks whether for every fixed $r\geq2$ and all sufficiently large $n$ there are parameters satisfying

n=\sum_{\nu=1}^{r+1} a_\nu^r\prod_{j=1}^{r-1}b_{\nu,j}^{\,r+j}, \tag{2}

where within each $\nu$, the $b_{\nu,j}$ are squarefree and pairwise coprime. This is an exact equivalence, not a relaxation.

For example, for $r=3$, the summands are uniquely $a^3b^4c^5$ with $b,c$ squarefree and coprime. For $r=4$, they are $a^4b^5c^6d^7$ with the analogous conditions.

5.3 Correct order of magnitude, but not pointwise coverage

(a) Formula (1) gives

\lvert A_r(X)\rvert=\Theta_r(X^{1/r}).

The lower bound comes from the $r$-th powers. For the upper bound, sum the number $O((X/d)^{1/r})$ of choices for $a$ over $d=\prod b_j^{r+j}$, and ignore the coprimality restrictions. The resulting Euler product converges because every prime contribution has exponent $1+j/r>1$.

Thus $r+1$ is the first number of summands for which the raw tuple count has comfortable average multiplicity: the number of ordered tuples with summands at most $X$, averaged across their $O(X)$-sized range, is on the scale $X^{1/r}$. This counting fact does not imply that the representations are distributed uniformly among target integers.

6. The exact analytic wall

Let

F_r(X;\alpha)= \sum_{\substack{1\leq n\leq X\\n\ r\text{-powerful}}}e(\alpha n), \qquad e(t)=e^{2\pi i t},

and put $G_r=1+F_r$, where 1 supplies zero padding. By (1),

F_r(X;\alpha)= \sum_{\substack{b_1,\ldots,b_{r-1}\ {\rm squarefree}\\ (b_i,b_j)=1\\ d=\prod b_j^{r+j}\leq X}} \ \sum_{1\leq a\leq(X/d)^{1/r}} e(\alpha d a^r). \tag{3}

(a) The number of ordered representations of $n\leq X$ by at most $r+1$ summands is exactly

R_r(n)=\int_0^1G_r(X;\alpha)^{r+1}e(-n\alpha)\,d\alpha. \tag{4}

Consequently, a sufficient circle-method lemma would provide, uniformly in large $n$, a major/minor-arc split with

\Re\int_{\mathfrak M}G_r^{r+1}e(-n\alpha)\,d\alpha \geq c_r n^{1/r} \tag{5}

and

\left|\int_{\mathfrak m}G_r^{r+1}e(-n\alpha)\,d\alpha\right| < c_r n^{1/r}. \tag{6}

Equations (5)–(6), or a comparable pointwise convolution theorem, are the precise missing lemma. The all-moduli result in Section 4 removes the simplest local obstruction, but does not supply either uniform estimate.

(a) The elementary $L^\infty/L^2$ machinery is quantitatively far too weak. With $M=\lvert A_r(X)\rvert+1=\Theta_r(X^{1/r})$, orthogonality gives $\int_0^1|G_r|^2=M$, while $\lVert G_r\rVert_\infty\leq M$. Hence

\int_0^1|G_r|^{r+1} \leq M^{r-1}\int_0^1|G_r|^2=M^r=\Theta_r(X),

where the pointwise target scale in (5)–(6) is only $X^{1/r}$. The generic bound loses a factor $X^{1-1/r}$. One needs cancellation exploiting the coupled family of degree-$r$ Weyl sums in (3), at the critical count of only $r+1$ variables.

(c) My literature search did not locate such an estimate for $r\geq3$. This is a search result, not a proof that no paper exists.

7. Literature check

7.1 Verified primary sources

(b) D. R. Heath-Brown, *Ternary quadratic forms and sums of three

square-full numbers*, Séminaire de Théorie des Nombres, Paris 1986–87, Progress in Mathematics 75 (1988), pp. 137–163. The bibliographic record is present in the source trail used by the live page. The theorem's conclusion is independently stated as a corollary in the next primary source.

(b) B. Z. Moroz, *On the representation of large integers by

integral ternary positive definite quadratic forms*, Astérisque 209 (1992), pp. 275–278: <https://www.numdam.org/article/AST_1992__209__275_0.pdf>. The paper defines square-full integers and explicitly gives the corollary that every sufficiently large positive integer is a sum of at most three square-full numbers. It cites Heath-Brown's pp. 137–163 paper.

(b) D. R. Heath-Brown, Sums of three square-full numbers, in

Number Theory, Vol. I (Budapest, 1987), Colloq. Math. Soc. János Bolyai 51 (1990), pp. 163–171. The official volume contents verify the paper and pagination: <https://www.bolyai.hu/files/kotetek_51_1990.pdf>.

(b) P. Shiu, The distribution of cube-full numbers, Glasgow

Mathematical Journal 33 (1991), pp. 287–295: <https://www.cambridge.org/core/services/aop-cambridge-core/content/view/3ABFFD38026AAA654392D87FACB82762/S0017089500008351a.pdf/the-distribution-of-cube-full-numbers.pdf>. This is a distribution/short-interval paper, not a proof of four-term additive coverage.

(b) Hong-Quan Liu, The number of cube-full numbers in an interval,

Acta Arithmetica 67 (1994), pp. 1–12: <https://matwbn.icm.edu.pl/ksiazki/aa/aa67/aa6711.pdf>. This also concerns distribution rather than #1107.

(b) Hong-Quan Liu, The distribution of 4-full numbers, Acta

Arithmetica 67 (1994), pp. 165–176, DOI 10.4064/aa-67-2-165-176. Its opening and theorem concern the counting function $Q_4(x)$, not sums of five 4-full numbers.

No arXiv identifier is assigned above because these older papers were verified through their actual journal/proceedings records rather than by inventing an arXiv version.

7.2 Current computational records (not theorems)

(d) OEIS A392342 currently reports the same 45 cubefull exceptions and a separate computation with no additional exception below $10^9$: <https://oeis.org/A392342>. Its linked Python program is a nested-tuple enumeration; it is not used by this report.

(d) OEIS A392343 records the 4-full sequence but its displayed Mathematica calculation uses cutoff 31,000: <https://oeis.org/A392343>.

(d) A 7 January 2026 SeqFan thread contains Robert Gerbicz's statement that the $r=4$ last exception “could be 150271” and gives PARI/GP code: <https://groups.google.com/g/seqfan/c/CuGGGmq6qpw>. The independent computation here agrees and certifies no further miss through $10^8$, but still does not promote 150,271 to a global last exception.

7.3 Search miss, stated narrowly

(c) Exact-phrase and subject searches for combinations of “$r$-full”, “$k$-full”, “$r$-powerful”, “sum of $r+1$”, “cubefull numbers”, and “additive basis” were run across general web indexing, arXiv results, zbMATH-visible metadata, and primary journal repositories. They recovered Heath-Brown's $r=2$ work, distribution papers for cube-full and 4-full numbers, and unrelated additive equations among powerful numbers. They did not recover a primary paper proving or disproving #1107 for any $r\geq3$. This is necessarily non-exhaustive and is not presented as a theorem about the literature.

8. Reverification code and commands

The standalone standard-library verifier is:

runs/verify_erdos1107_wavew034.py

Its file SHA-256 after the full run and final regression update is:

6bc78c79340818008d3c9d33fc5aefff5a20b6081104c3567736a179aa934ad0

The later regression-only edit adds the already computed $r=3$ expected hash; it does not change any algorithm or output.

Run the complete suite:

python runs/verify_erdos1107_wavew034.py

Run the fast independent tests and a small case:

python runs/verify_erdos1107_wavew034.py --quick

Recompute one chosen finite regime and print its entire exception list:

python runs/verify_erdos1107_wavew034.py \
  --r 4 --limit 100000000 --print-exceptions

The code uses no downloaded tables and no third-party Python package.

9. Honest stopping point and cost

(d) At $r=4,N=10^8$, the saved case took 21.51 seconds. The post-pair-layer work is roughly proportional to $(r-1)\lvert A_r(N)\rvert N$ bit traffic. Since $\lvert A_4(10^8)\rvert=464$ and $\lvert A_4(10^9)\rvert=906$, a direct $10^9$ run is estimated from the measured scaling at about 7 CPU-minutes and about 1.3 GB peak transient memory. That is roughly 0.12 core-hours (about $0.006 at an illustrative $0.05/core-hour compute rate, before memory/VM overhead). I did not run it because the task limits this box to a few CPU-minutes, and a finite extension cannot settle eventual coverage.

(a) No finite cutoff, however large, supplies the uniformity step in the phrase “every large integer.” To advance from this report to a solution, the needed result is the pointwise analytic lemma represented by (5)–(6), or a different uniform construction proving (2) for every sufficiently large target. The exact modular route is closed by Section 4; the remaining wall is global cancellation/coverage, not an undiscovered small congruence or an unrun finite search.

PARTIAL: proved no fixed-modulus obstruction and exactly certified the stated finite suffixes through $10^7$ for $r=3$ and $10^8$ for $4\le r\le8$; eventual coverage for every $r\ge3$ remains open.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger