U(N) = sum_{n=1..N} u(n) where u(n) is the smallest prime p such that (n mod p) is NOT a multiple of 7. Compute U(10^17) using CRT residue construction + explicit enumeration. Pure Flow port of the native C solver.
# Project Euler 934: Unlucky Primes
# U(N) = sum_{n=1..N} u(n) where u(n) is the smallest prime p
# such that (n mod p) is NOT a multiple of 7.
# Compute U(10^17) using CRT residue construction + explicit enumeration.
# Pure Flow port of the native C solver.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
function malloc(n: i64) -> ptr<void>
function realloc(p: ptr<void>, n: i64) -> ptr<void>
function printf(fmt: ptr<i8>, ...) -> i32
}
# Extended Euclid for modular inverse
function inv_mod(a0: i64, m: i64) -> i64 {
let mut a: i64 = a0 % m
if a < 0 { a = a + m }
let mut t0: i64 = 0
let mut t1: i64 = 1
let mut r0: i64 = m
let mut r1: i64 = a
while r1 != 0 {
let q: i64 = r0 / r1
let tmp: i64 = t0 - q * t1
t0 = t1
t1 = tmp
let tmp2: i64 = r0 - q * r1
r0 = r1
r1 = tmp2
}
if r0 != 1 { return -1 }
let mut res: i64 = t0 % m
if res < 0 { res = res + m }
return res
}
function is_prime(x: i32) -> bool {
if x < 2 { return false }
if x == 2 { return true }
if x % 2 == 0 { return false }
let mut i: i32 = 3
while (i as i64) * (i as i64) <= (x as i64) {
if x % i == 0 { return false }
i = i + 2
}
return true
}
function main() -> i32 {
let mut N: i64 = 1
let mut i: i32 = 0
while i < 17 {
N = N * 10
i = i + 1
}
let mut ans: i64 = 0
let mut c_prev: i64 = N
# Phase 1: CRT mode
let mut M: i64 = 1
let mut residues: ptr<i64> = (malloc(8)) as ptr<i64>
residues[0] = 0
let mut num_residues: i32 = 1
# Phase 2: explicit survivors
let mut survivors: ptr<i64> = null as ptr<i64>
let mut num_survivors: i32 = 0
let mut p: i32 = 2
while true {
if !is_prime(p) {
p = p + 1
continue
}
# Allowed residues mod p: multiples of 7 in [0, p-1]
let num_allowed: i32 = (p + 6) / 7
let c: i64 = 0
if survivors == (null as ptr<i64>) {
# CRT mode
let M_new: i128 = (M as i128) * (p as i128)
if M_new <= (N as i128) {
# Extend residues using CRT
let inv: i64 = inv_mod(M, (p as i64))
let M_old: i64 = M
let new_cap: i32 = num_residues * num_allowed
let new_residues: ptr<i64> = (malloc((new_cap as i64) * 8)) as ptr<i64>
let mut nr: i32 = 0
let mut ii: i32 = 0
while ii < num_residues {
let r: i64 = residues[ii]
let mut s: i32 = 0
while s < p {
let diff: i64 = (s as i64) - r
let mut t: i64 = ((diff % (p as i64)) * inv) % (p as i64)
if t < 0 { t = t + (p as i64) }
let new_r: i64 = r + M_old * t
new_residues[nr] = new_r
nr = nr + 1
s = s + 7
}
ii = ii + 1
}
free(residues as ptr<void>)
residues = new_residues
num_residues = nr
M = (M_new as i64)
# Count numbers <= N matching these residues (period M)
let q: i64 = N / M
let rem: i64 = N % M
let mut extra: i64 = 0
let mut iii: i32 = 0
while iii < num_residues {
if residues[iii] > 0 && residues[iii] <= rem {
extra = extra + 1
}
iii = iii + 1
}
let cc: i64 = q * (num_residues as i64) + extra
# Numbers that stop at prime p have u(n) = p
ans = ans + (p as i64) * (c_prev - cc)
c_prev = cc
} else {
# Switch to explicit enumeration
let inv: i64 = inv_mod(M, (p as i64))
let M_old: i64 = M
survivors = (malloc((num_residues * num_allowed) as i64 * 8)) as ptr<i64>
num_survivors = 0
let mut ii2: i32 = 0
while ii2 < num_residues {
let r: i64 = residues[ii2]
let mut s: i32 = 0
while s < p {
let diff: i64 = (s as i64) - r
let mut t: i64 = ((diff % (p as i64)) * inv) % (p as i64)
if t < 0 { t = t + (p as i64) }
let x: i64 = r + M_old * t
if x > 0 && x <= N {
survivors[num_survivors] = x
num_survivors = num_survivors + 1
}
s = s + 7
}
ii2 = ii2 + 1
}
free(residues as ptr<void>)
residues = null as ptr<i64>
M = (M_new as i64)
let cc2: i64 = num_survivors as i64
ans = ans + (p as i64) * (c_prev - cc2)
c_prev = cc2
}
} else {
# Explicit enumeration mode: filter survivors
let mut j: i32 = 0
let mut jj3: i32 = 0
while jj3 < num_survivors {
let n: i64 = survivors[jj3]
if (n % (p as i64)) % 7 == 0 {
survivors[j] = n
j = j + 1
}
jj3 = jj3 + 1
}
num_survivors = j
let cc3: i64 = num_survivors as i64
ans = ans + (p as i64) * (c_prev - cc3)
c_prev = cc3
}
if c_prev == 0 { break }
p = p + 1
}
if residues != (null as ptr<i64>) {
free(residues as ptr<void>)
}
if survivors != (null as ptr<i64>) {
free(survivors as ptr<void>)
}
printf("%lld\n", ans)
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 inv_mod_i64_i64(int64_t a0, int64_t m);
bool is_prime_i32(int32_t x);
int32_t main(void);
int64_t inv_mod_i64_i64(int64_t a0, int64_t m) {
int64_t a = FLOW_CHECKED_MOD((a0), (m));
if (a < 0) {
a = (a + m);
}
int64_t t0 = 0;
int64_t t1 = 1;
int64_t r0 = m;
int64_t r1 = a;
while (r1 != 0) {
int64_t q = FLOW_CHECKED_DIV((r0), (r1));
int64_t tmp = (t0 - (q * t1));
t0 = t1;
t1 = tmp;
int64_t tmp2 = (r0 - (q * r1));
r0 = r1;
r1 = tmp2;
}
if (r0 != 1) {
return (-1);
}
int64_t res = FLOW_CHECKED_MOD((t0), (m));
if (res < 0) {
res = (res + m);
}
return res;
}
bool is_prime_i32(int32_t x) {
if (x < 2) {
return 0;
}
if (x == 2) {
return 1;
}
if (FLOW_CHECKED_MOD((x), (2)) == 0) {
return 0;
}
int32_t i = 3;
while ((((int64_t)(i)) * ((int64_t)(i))) <= ((int64_t)(x))) {
if (FLOW_CHECKED_MOD((x), (i)) == 0) {
return 0;
}
i = (i + 2);
}
return 1;
}
int32_t main(void) {
int64_t N = 1;
int32_t i = 0;
while (i < 17) {
N = (N * 10);
i = (i + 1);
}
int64_t ans = 0;
int64_t c_prev = N;
int64_t M = 1;
int64_t* residues = (int64_t*)(((int64_t*)(malloc(8))));
residues[0] = 0;
int32_t num_residues = 1;
int64_t* survivors = (int64_t*)(((int64_t*)(NULL)));
int32_t num_survivors = 0;
int32_t p = 2;
while (1) {
if ((!(is_prime_i32(p)))) {
p = (p + 1);
continue;
}
int32_t num_allowed = FLOW_CHECKED_DIV(((p + 6)), (7));
int64_t c = 0;
if (survivors == ((int64_t*)(NULL))) {
__int128 M_new = (((__int128)(M)) * ((__int128)(p)));
if (M_new <= ((__int128)(N))) {
int64_t inv = inv_mod_i64_i64(M, ((int64_t)(p)));
int64_t M_old = M;
int32_t new_cap = (num_residues * num_allowed);
int64_t* new_residues = (int64_t*)(((int64_t*)(malloc((((int64_t)(new_cap)) * 8)))));
int32_t nr = 0;
int32_t ii = 0;
while (ii < num_residues) {
int64_t r = residues[ii];
int32_t s = 0;
while (s < p) {
int64_t diff = (((int64_t)(s)) - r);
int64_t t = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD((diff), (((int64_t)(p)))) * inv)), (((int64_t)(p))));
if (t < 0) {
t = (t + ((int64_t)(p)));
}
int64_t new_r = (r + (M_old * t));
new_residues[nr] = new_r;
nr = (nr + 1);
s = (s + 7);
}
ii = (ii + 1);
}
free(((void*)(residues)));
residues = new_residues;
num_residues = nr;
M = ((int64_t)(M_new));
int64_t q = FLOW_CHECKED_DIV((N), (M));
int64_t rem = FLOW_CHECKED_MOD((N), (M));
int64_t extra = 0;
int32_t iii = 0;
while (iii < num_residues) {
if ((residues[iii] > 0 && residues[iii] <= rem)) {
extra = (extra + 1);
}
iii = (iii + 1);
}
int64_t cc = ((q * ((int64_t)(num_residues))) + extra);
ans = (ans + (((int64_t)(p)) * (c_prev - cc)));
c_prev = cc;
} else {
int64_t inv = inv_mod_i64_i64(M, ((int64_t)(p)));
int64_t M_old = M;
survivors = ((int64_t*)(malloc((((int64_t)((num_residues * num_allowed))) * 8))));
num_survivors = 0;
int32_t ii2 = 0;
while (ii2 < num_residues) {
int64_t r = residues[ii2];
int32_t s = 0;
while (s < p) {
int64_t diff = (((int64_t)(s)) - r);
int64_t t = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD((diff), (((int64_t)(p)))) * inv)), (((int64_t)(p))));
if (t < 0) {
t = (t + ((int64_t)(p)));
}
int64_t x = (r + (M_old * t));
if ((x > 0 && x <= N)) {
survivors[num_survivors] = x;
num_survivors = (num_survivors + 1);
}
s = (s + 7);
}
ii2 = (ii2 + 1);
}
free(((void*)(residues)));
residues = ((int64_t*)(NULL));
M = ((int64_t)(M_new));
int64_t cc2 = ((int64_t)(num_survivors));
ans = (ans + (((int64_t)(p)) * (c_prev - cc2)));
c_prev = cc2;
}
} else {
int32_t j = 0;
int32_t jj3 = 0;
while (jj3 < num_survivors) {
int64_t n = survivors[jj3];
if (FLOW_CHECKED_MOD((FLOW_CHECKED_MOD((n), (((int64_t)(p))))), (7)) == 0) {
survivors[j] = n;
j = (j + 1);
}
jj3 = (jj3 + 1);
}
num_survivors = j;
int64_t cc3 = ((int64_t)(num_survivors));
ans = (ans + (((int64_t)(p)) * (c_prev - cc3)));
c_prev = cc3;
}
if (c_prev == 0) {
break;
}
p = (p + 1);
}
if (residues != ((int64_t*)(NULL))) {
free(((void*)(residues)));
}
if (survivors != ((int64_t*)(NULL))) {
free(((void*)(survivors)));
}
printf("%lld\n", ans);
return 0;
}