# Project Euler 881: Divisor Graph Width
# Pure Flow port. Branch-and-bound DFS over non-increasing exponent sequences.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function malloc(n: i64) -> ptr<void>
function free(p: ptr<void>) -> void
function memset(p: ptr<void>, c: i64, n: i64) -> ptr<void>
}
# Sieve primes up to limit, store into PRIMES array, return count.
function sieve_primes(limit: i64, PRIMES: ptr<i64>) -> i64 {
let sieve: ptr<i8> = calloc(limit + 1, 1)
memset(sieve, 1, limit + 1)
sieve[0] = 0
sieve[1] = 0
let mut p: i64 = 2
while p * p <= limit {
if sieve[p] != 0 {
let mut m: i64 = p * p
while m <= limit {
sieve[m] = 0
m = m + p
}
}
p = p + 1
}
let mut num: i64 = 0
let mut i: i64 = 2
while i <= limit {
if sieve[i] != 0 {
PRIMES[num] = i
num = num + 1
}
i = i + 1
}
free(sieve)
return num
}
# Convolve poly with (1 + x + ... + x^e), sliding window sum.
# Returns new array; writes length into out_len_ptr.
function convolve_with_ones(poly: ptr<i64>, poly_len: i64, e: i64, out_len_ptr: ptr<i64>) -> ptr<i64> {
let out_len: i64 = poly_len + e
out_len_ptr[0] = out_len
let out: ptr<i64> = calloc(out_len, 8)
let pref: ptr<i64> = calloc(poly_len + 1, 8)
let mut s: i64 = 0
let mut i: i64 = 0
while i < poly_len {
s = s + poly[i]
pref[i + 1] = s
i = i + 1
}
let mut j: i64 = 0
while j < out_len {
let mut lo: i64 = j - e
if lo < 0 { lo = 0 }
let mut hi: i64 = j
if hi >= poly_len { hi = poly_len - 1 }
if lo <= hi {
out[j] = pref[hi + 1] - pref[lo]
}
j = j + 1
}
free(pref)
return out
}
function max_array(arr: ptr<i64>, len: i64) -> i64 {
let mut m: i64 = arr[0]
let mut i: i64 = 1
while i < len {
if arr[i] > m {
m = arr[i]
}
i = i + 1
}
return m
}
# dfs with best_n passed as ptr<i128> (mutable global replacement).
function dfs(idx: i64, prev_e: i64, poly: ptr<i64>, poly_len: i64, peak: i64, n: i128, target: i64, PRIMES: ptr<i64>, num_primes: i64, best_n_ptr: ptr<i128>) -> void {
if n >= best_n_ptr[0] { return }
if peak >= target {
best_n_ptr[0] = n
return
}
if idx >= num_primes { return }
let p: i64 = PRIMES[idx]
let mut max_e: i64 = 0
let mut t: i128 = n
while max_e < prev_e {
t = t * (p as i128)
if t >= best_n_ptr[0] { break }
max_e = max_e + 1
}
if max_e == 0 { return }
let powers: ptr<i128> = malloc(64 * 16)
powers[0] = 1
let mut e: i64 = 1
while e <= max_e {
powers[e] = powers[e - 1] * (p as i128)
e = e + 1
}
e = max_e
while e >= 1 {
let n2: i128 = n * powers[e]
if n2 < best_n_ptr[0] {
let out_len_ptr: ptr<i64> = malloc(8)
let poly2: ptr<i64> = convolve_with_ones(poly, poly_len, e, out_len_ptr)
let out_len: i64 = out_len_ptr[0]
let peak2: i64 = max_array(poly2, out_len)
dfs(idx + 1, e, poly2, out_len, peak2, n2, target, PRIMES, num_primes, best_n_ptr)
free(poly2)
free(out_len_ptr)
}
e = e - 1
}
free(powers)
}
function initial_upper_bound(target: i64, PRIMES: ptr<i64>) -> i128 {
let poly: ptr<i64> = malloc(8)
poly[0] = 1
let mut poly_len: i64 = 1
let mut n: i128 = 1
let mut i: i64 = 0
while true {
let out_len_ptr: ptr<i64> = malloc(8)
let poly2: ptr<i64> = convolve_with_ones(poly, poly_len, 1, out_len_ptr)
let out_len: i64 = out_len_ptr[0]
free(poly)
free(out_len_ptr)
poly = poly2
poly_len = out_len
n = n * (PRIMES[i] as i128)
i = i + 1
if max_array(poly, poly_len) >= target {
free(poly)
return n
}
}
return 0
}
function main() -> i32 {
let PRIMES: ptr<i64> = malloc(400 * 8)
let num_primes: i64 = sieve_primes(400, PRIMES)
let target: i64 = 10000
let best_n_ptr: ptr<i128> = malloc(16)
best_n_ptr[0] = initial_upper_bound(target, PRIMES)
let initial_poly: ptr<i64> = malloc(8)
initial_poly[0] = 1
dfs(0, 60, initial_poly, 1, 1, 1, target, PRIMES, num_primes, best_n_ptr)
free(initial_poly)
printf("%lld\n", (best_n_ptr[0]) as i64)
free(PRIMES)
free(best_n_ptr)
return 0
}
Generated C
#include <stdint.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* Flow runtime helpers */
typedef struct flow_temp_node { struct flow_temp_node* next; } flow_temp_node;
static flow_temp_node* flow_temp_head = NULL;
static int flow_temp_atexit_set = 0;
__attribute__((unused)) static void flow_temp_free_all(void) {
while (flow_temp_head) {
flow_temp_node* n = flow_temp_head;
flow_temp_head = n->next;
free(n);
}
}
__attribute__((unused)) static void* flow_temp_alloc(size_t nbytes) {
flow_temp_node* node = (flow_temp_node*)malloc(sizeof(flow_temp_node) + nbytes);
if (!node) return NULL;
node->next = flow_temp_head;
flow_temp_head = node;
if (!flow_temp_atexit_set) {
flow_temp_atexit_set = 1;
atexit(flow_temp_free_all);
}
return (void*)(node + 1);
}
#ifndef FLOW_DIAG
#define FLOW_DIAG(msg) fprintf(stderr, "%s", (msg))
#endif
#ifndef FLOW_LOG
#define FLOW_LOG(fmt, ...) printf(fmt, __VA_ARGS__)
#endif
#ifndef FLOW_LOG_EMPTY
#define FLOW_LOG_EMPTY(fmt) printf(fmt)
#endif
static char* flow_strcat(const char* a, const char* b) {
size_t la = strlen(a ? a : ""), lb = strlen(b ? b : "");
char* r = (char*)flow_temp_alloc(la + lb + 1);
if (!r) return NULL;
if (la) memcpy(r, a, la);
if (lb) memcpy(r + la, b, lb);
r[la + lb] = '\0';
return r;
}
#define __flow_in_arr(arr, val) __extension__ ({ \
int _found = 0; \
size_t _n = sizeof(arr)/sizeof((arr)[0]); \
for (size_t _i = 0; _i < _n; _i++) { \
if ((arr)[_i] == (val)) { _found = 1; break; } \
} _found; })
/* Unified fault handler (MISRA #279) — override with -DFLOW_FAULT_HANDLER=fn */
#ifndef FLOW_FAULT_HANDLER
__attribute__((unused)) static inline void flow_fault_handler(const char* msg) {
fprintf(stderr, "flow: %s\n", msg ? msg : "fault");
abort();
#if defined(__GNUC__) || defined(__clang__)
__builtin_unreachable();
#endif
}
#else
#define flow_fault_handler FLOW_FAULT_HANDLER
#endif
#define flow_div_by_zero_handler() flow_fault_handler("division by zero")
#define flow_shift_ub_handler() flow_fault_handler("invalid shift (amount out of range or left-shift of negative)")
#ifndef FLOW_CHECKED_DIV
#define FLOW_CHECKED_DIV(L, R) (((R) != 0) ? ((L) / (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_MOD
#define FLOW_CHECKED_MOD(L, R) (((R) != 0) ? ((L) % (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHL
#define FLOW_CHECKED_SHL(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull)) && ((L) >= 0)) ? ((L) << (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHR
#define FLOW_CHECKED_SHR(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull))) ? ((L) >> (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif
#include <math.h>
void* _ui_state = NULL;
static inline float i32_to_f32(int32_t v) { return (float)v; }
/* Host stub for @gpu kernels (device codegen replaces this). */
static inline int32_t gpu_thread_id(void) { return 0; }
int64_t sieve_primes_i64_ptr_i64(int64_t limit, int64_t* PRIMES);
int64_t* convolve_with_ones_ptr_i64_i64_i64_ptr_i64(int64_t* poly, int64_t poly_len, int64_t e, int64_t* out_len_ptr);
int64_t max_array_ptr_i64_i64(int64_t* arr, int64_t len);
void dfs_i64_i64_ptr_i64_i64_i64_i128_i64_ptr_i64_i64_ptr_i128(int64_t idx, int64_t prev_e, int64_t* poly, int64_t poly_len, int64_t peak, __int128 n, int64_t target, int64_t* PRIMES, int64_t num_primes, __int128* best_n_ptr);
__int128 initial_upper_bound_i64_ptr_i64(int64_t target, int64_t* PRIMES);
int32_t main(void);
int64_t sieve_primes_i64_ptr_i64(int64_t limit, int64_t* PRIMES) {
int8_t* sieve = (int8_t*)(calloc((limit + 1), 1));
memset(sieve, 1, (limit + 1));
sieve[0] = 0;
sieve[1] = 0;
int64_t p = 2;
while ((p * p) <= limit) {
if (sieve[p] != 0) {
int64_t m = (p * p);
while (m <= limit) {
sieve[m] = 0;
m = (m + p);
}
}
p = (p + 1);
}
int64_t num = 0;
int64_t i = 2;
while (i <= limit) {
if (sieve[i] != 0) {
PRIMES[num] = i;
num = (num + 1);
}
i = (i + 1);
}
free(sieve);
return num;
}
int64_t* convolve_with_ones_ptr_i64_i64_i64_ptr_i64(int64_t* poly, int64_t poly_len, int64_t e, int64_t* out_len_ptr) {
int64_t out_len = (poly_len + e);
out_len_ptr[0] = out_len;
int64_t* out = (int64_t*)(calloc(out_len, 8));
int64_t* pref = (int64_t*)(calloc((poly_len + 1), 8));
int64_t s = 0;
int64_t i = 0;
while (i < poly_len) {
s = (s + poly[i]);
pref[(i + 1)] = s;
i = (i + 1);
}
int64_t j = 0;
while (j < out_len) {
int64_t lo = (j - e);
if (lo < 0) {
lo = 0;
}
int64_t hi = j;
if (hi >= poly_len) {
hi = (poly_len - 1);
}
if (lo <= hi) {
out[j] = (pref[(hi + 1)] - pref[lo]);
}
j = (j + 1);
}
free(pref);
return out;
}
int64_t max_array_ptr_i64_i64(int64_t* arr, int64_t len) {
int64_t m = arr[0];
int64_t i = 1;
while (i < len) {
if (arr[i] > m) {
m = arr[i];
}
i = (i + 1);
}
return m;
}
void dfs_i64_i64_ptr_i64_i64_i64_i128_i64_ptr_i64_i64_ptr_i128(int64_t idx, int64_t prev_e, int64_t* poly, int64_t poly_len, int64_t peak, __int128 n, int64_t target, int64_t* PRIMES, int64_t num_primes, __int128* best_n_ptr) {
if (n >= best_n_ptr[0]) {
return;
}
if (peak >= target) {
best_n_ptr[0] = n;
return;
}
if (idx >= num_primes) {
return;
}
int64_t p = PRIMES[idx];
int64_t max_e = 0;
__int128 t = n;
while (max_e < prev_e) {
t = (t * ((__int128)(p)));
if (t >= best_n_ptr[0]) {
break;
}
max_e = (max_e + 1);
}
if (max_e == 0) {
return;
}
__int128* powers = (__int128*)(malloc((64 * 16)));
powers[0] = 1;
int64_t e = 1;
while (e <= max_e) {
powers[e] = (powers[(e - 1)] * ((__int128)(p)));
e = (e + 1);
}
e = max_e;
while (e >= 1) {
__int128 n2 = (n * powers[e]);
if (n2 < best_n_ptr[0]) {
int64_t* out_len_ptr = (int64_t*)(malloc(8));
int64_t* poly2 = (int64_t*)(convolve_with_ones_ptr_i64_i64_i64_ptr_i64(poly, poly_len, e, out_len_ptr));
int64_t out_len = out_len_ptr[0];
int64_t peak2 = max_array_ptr_i64_i64(poly2, out_len);
dfs_i64_i64_ptr_i64_i64_i64_i128_i64_ptr_i64_i64_ptr_i128((idx + 1), e, poly2, out_len, peak2, n2, target, PRIMES, num_primes, best_n_ptr);
free(poly2);
free(out_len_ptr);
}
e = (e - 1);
}
free(powers);
}
__int128 initial_upper_bound_i64_ptr_i64(int64_t target, int64_t* PRIMES) {
int64_t* poly = (int64_t*)(malloc(8));
poly[0] = 1;
int64_t poly_len = 1;
__int128 n = 1;
int64_t i = 0;
while (1) {
int64_t* out_len_ptr = (int64_t*)(malloc(8));
int64_t* poly2 = (int64_t*)(convolve_with_ones_ptr_i64_i64_i64_ptr_i64(poly, poly_len, 1, out_len_ptr));
int64_t out_len = out_len_ptr[0];
free(poly);
free(out_len_ptr);
poly = poly2;
poly_len = out_len;
n = (n * ((__int128)(PRIMES[i])));
i = (i + 1);
if (max_array_ptr_i64_i64(poly, poly_len) >= target) {
free(poly);
return n;
}
}
return 0;
}
int32_t main(void) {
int64_t* PRIMES = (int64_t*)(malloc((400 * 8)));
int64_t num_primes = sieve_primes_i64_ptr_i64(400, PRIMES);
int64_t target = 10000;
__int128* best_n_ptr = (__int128*)(malloc(16));
best_n_ptr[0] = initial_upper_bound_i64_ptr_i64(target, PRIMES);
int64_t* initial_poly = (int64_t*)(malloc(8));
initial_poly[0] = 1;
dfs_i64_i64_ptr_i64_i64_i64_i128_i64_ptr_i64_i64_ptr_i128(0, 60, initial_poly, 1, 1, 1, target, PRIMES, num_primes, best_n_ptr);
free(initial_poly);
printf("%lld\n", ((int64_t)(best_n_ptr[0])));
free(PRIMES);
free(best_n_ptr);
return 0;
}