IBM Ponder This, March 2024

2024-04-09

Solution to the IBM Ponder This problem for March 2024. Here is the problem statement, and here is the official solution.

X_1000	115192665
X_2024	117778830159

Approach

A prime sieve is initially populated by following Sieve of Eratosthenes. As an optimization, a bitset is used (instead of individual bytes) for 8-fold memory savings.

The whole sieve still took around 30 GB of RAM, which just about my system memory. An additional optimization could be populating the sieve contiguous segments at a time (instead of walking the whole memory space for each prime) to leverage RAM NUMA caching. (This is called the “Segmented Sieve” approach).

After that, a brute force approach is used, testing every integer starting from 1. The numbers seem to be all safely within the 64-bit range, so they can be efficiently computed by a modern 64-bit processor (without slow big integer libraries).

The code below uses a single core and takes around one hour of wall clock time on my machine to both compute the sieve and find the solutions for X_i, with i from 1 to 2024. The solution from the previous i-1 is the starting point for the brute force search for X_i to save on some recomputation.

Source code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

typedef int64_t i64;
typedef uint64_t u64;


// #define END 1000
// #define MAX_N 120000000LL
// #define SQRT_MAX_N 11000LL

#define END 2024
#define MAX_N 250000000000LL
#define SQRT_MAX_N 500000LL

#define BASE 64
u64 bitset[(MAX_N/BASE)+1];
#define bitset_test(X) (bitset[((u64)(X))/BASE] & ((u64)1 << (((u64)(X)) % BASE)))
#define bitset_set(X) do{ bitset[((u64)(X))/BASE] |= ((u64)1 << (((u64)(X)) % BASE)); }while(0)

#undef assert
#define assert(X) if(!(X)) { \
	fprintf(stderr, "%s:%d: assert failed '%s'\n", __FILE__, __LINE__, #X); exit(1); }

static int is_prime(i64 x) {
	assert(x < MAX_N);
	return !bitset_test(x);
}

static int is_valid_fast(i64 n, i64 i) {
	if (is_prime(i)) { return 0; }
	i64 x = i;
	for (i64 k = 1; k < n; k++) {
		x = x + k;
		if (is_prime(x)) { return 0; }
	}
	return 1;
}

static i64 solve_fast(i64 n, i64 hint) {
	for (i64 i = hint; i < MAX_N; i++) {
		if (is_valid_fast(n, i)) {
			return i;
		}
	}
	return -1;
}

static void populate_sieve() {
	memset(bitset, 0, sizeof(bitset));
	bitset_set(1);
	for (i64 i = 2; i <= SQRT_MAX_N; i++) {
		if (bitset_test(i)) { continue; }
		for (i64 k = i*i; k <= MAX_N; k += i) {
			bitset_set(k);
		}
	}
}

int main() {
	fprintf(stderr, "Computing sieve up to %ld\n", MAX_N);
	populate_sieve();
	fprintf(stderr, "done\n");

	i64 hint = 1;
	for (int i = 1; i <= END; i++) {
		i64 sol = solve_fast(i, hint);
		if (hint != sol || i == END) {
			printf("%d\t%ld\n", i, sol);
			fflush(stdout);
		}
		hint = sol;
	}
}