Problem 542

Geometric Progression with Maximum Sum — T(10^17) via piecewise S(k).

View problem on Project Euler

Performance comparison

Flow source

# Project Euler 542
# Geometric Progression with Maximum Sum — T(10^17) via piecewise S(k).

const N: i64 = 100000000000000000

function ipow128(base: i64, exp: i64) -> i128 {
    let mut r: i128 = 1 as i128
    let mut b: i128 = base as i128
    let mut e: i64 = exp
    while e > 0 {
        if (e & 1) != 0 { r = r * b }
        b = b * b
        e = e >> 1
    }
    return r
}

function iroot(n: i64, k: i64) -> i64 {
    if k <= 1 { return n }
    if n <= 0 { return 0 }
    if n == 1 { return 1 }
    let mut lo: i64 = 1
    let mut hi: i64 = 2
    while ipow128(hi, k) <= (n as i128) {
        if hi > 2000000000 { break }
        hi = hi * 2
    }
    while lo + 1 < hi {
        let mid: i64 = (lo + hi) / 2
        if ipow128(mid, k) <= (n as i128) {
            lo = mid
        } else {
            hi = mid
        }
    }
    return lo
}

function ipow(base: i64, exp: i64) -> i64 {
    let mut r: i128 = 1 as i128
    let mut b: i128 = base as i128
    let mut e: i64 = exp
    while e > 0 {
        if (e & 1) != 0 { r = r * b }
        b = b * b
        e = e >> 1
    }
    return r as i64
}

function S_val_brute(k: i64) -> i64 {
    if k < 4 { return 0 }
    let mut best: i64 = 0
    let mut t_max: i64 = 0
    let mut tmp: i64 = k
    while tmp > 1 {
        t_max = t_max + 1
        tmp = tmp >> 1
    }
    let mut t: i64 = t_max
    while t >= 2 {
        let p_max: i64 = iroot(k, t)
        if p_max < 2 {
            t = t - 1
            continue
        }
        let mut p: i64 = 2
        while p <= p_max {
            let d: i64 = ipow(p, t)
            let b: i64 = k / d
            if b == 0 { break }
            let c: i64 = ipow(p, t + 1) - ipow(p - 1, t + 1)
            let val: i64 = b * c
            if val > best { best = val }
            p = p + 1
        }
        t = t - 1
    }
    return best
}

function S_val(k: i64) -> i64 {
    if k < 4 { return 0 }
    if k <= 1249 { return S_val_brute(k) }
    let mut best: i64 = 0
    # t=3: floor-division blocking with P = k^(1/4)
    let p_max3: i64 = iroot(k, 3)
    if p_max3 >= 2 {
        let mut P: i64 = iroot(k, 4)
        if P < 2 { P = 2 }
        if P > p_max3 { P = p_max3 }
        let mut p: i64 = 2
        while p <= P {
            let d: i64 = p * p * p
            let b: i64 = k / d
            let c: i64 = ipow(p, 4) - ipow(p - 1, 4)
            let val: i64 = b * c
            if val > best { best = val }
            p = p + 1
        }
        let Pp1: i64 = P + 1
        let Pp1cubed: i64 = ipow(Pp1, 3)
        let b_max: i64 = k / Pp1cubed
        let mut b: i64 = 1
        while b <= b_max {
            let p2: i64 = iroot(k / b, 3)
            if p2 >= Pp1 {
                let mut pp: i64 = p2
                if pp > p_max3 { pp = p_max3 }
                let c: i64 = ipow(pp, 4) - ipow(pp - 1, 4)
                let val: i64 = b * c
                if val > best { best = val }
            }
            b = b + 1
        }
    }
    # t >= 4: check all p
    let mut t_max: i64 = 0
    let mut tmp: i64 = k
    while tmp > 1 {
        t_max = t_max + 1
        tmp = tmp >> 1
    }
    let mut t: i64 = 4
    while t <= t_max {
        let p_max: i64 = iroot(k, t)
        if p_max >= 2 {
            let mut p: i64 = 2
            while p <= p_max {
                let d: i64 = ipow(p, t)
                let b: i64 = k / d
                if b == 0 { break }
                let c: i64 = ipow(p, t + 1) - ipow(p - 1, t + 1)
                let val: i64 = b * c
                if val > best { best = val }
                p = p + 1
            }
        }
        t = t + 1
    }
    return best
}

function alt_sum(a: i64, b: i64) -> i64 {
    if a > b { return 0 }
    let len: i64 = b - a + 1
    if (len & 1) == 0 { return 0 }
    if (a & 1) == 0 { return 1 }
    return -1
}

function T(n: i64) -> i64 {
    if n < 4 { return 0 }
    let mut total: i64 = 0
    let mut k: i64 = 4
    while k <= n {
        let v: i64 = S_val(k)
        let mut step: i64 = 1
        let mut hi: i64 = k + step
        if hi > n { hi = n }
        let mut v_hi: i64 = S_val(hi)
        while v_hi == v && hi < n {
            step = step * 2
            hi = k + step
            if hi > n { hi = n }
            v_hi = S_val(hi)
        }
        if hi == n && v_hi == v {
            total = total + v * alt_sum(k, n)
            break
        }
        let mut lo: i64 = k + 1
        let mut r: i64 = hi
        while lo < r {
            let mid: i64 = (lo + r) / 2
            if S_val(mid) == v {
                lo = mid + 1
            } else {
                r = mid
            }
        }
        total = total + v * alt_sum(k, lo - 1)
        k = lo
    }
    return total
}

function main() -> i32 {
    printf("%lld\n", T(N))
    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; }

__int128 ipow128_i64_i64(int64_t base, int64_t exp);
int64_t iroot_i64_i64(int64_t n, int64_t k);
int64_t ipow_i64_i64(int64_t base, int64_t exp);
int64_t S_val_brute_i64(int64_t k);
int64_t S_val_i64(int64_t k);
int64_t alt_sum_i64_i64(int64_t a, int64_t b);
int64_t T_i64(int64_t n);
int32_t main(void);

static const int64_t N = 100000000000000000;

__int128 ipow128_i64_i64(int64_t base, int64_t exp) {
    __int128 r = ((__int128)(1));
    __int128 b = ((__int128)(base));
    int64_t e = exp;
    while (e > 0) {
        if ((e & 1) != 0) {
            r = (r * b);
        }
        b = (b * b);
        e = FLOW_CHECKED_SHR((e), (1));
    }
    return r;
}

int64_t iroot_i64_i64(int64_t n, int64_t k) {
    if (k <= 1) {
        return n;
    }
    if (n <= 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    int64_t lo = 1;
    int64_t hi = 2;
    while (ipow128_i64_i64(hi, k) <= ((__int128)(n))) {
        if (hi > 2000000000) {
            break;
        }
        hi = (hi * 2);
    }
    while ((lo + 1) < hi) {
        int64_t mid = FLOW_CHECKED_DIV(((lo + hi)), (2));
        if (ipow128_i64_i64(mid, k) <= ((__int128)(n))) {
            lo = mid;
        } else {
            hi = mid;
        }
    }
    return lo;
}

int64_t ipow_i64_i64(int64_t base, int64_t exp) {
    __int128 r = ((__int128)(1));
    __int128 b = ((__int128)(base));
    int64_t e = exp;
    while (e > 0) {
        if ((e & 1) != 0) {
            r = (r * b);
        }
        b = (b * b);
        e = FLOW_CHECKED_SHR((e), (1));
    }
    return ((int64_t)(r));
}

int64_t S_val_brute_i64(int64_t k) {
    if (k < 4) {
        return 0;
    }
    int64_t best = 0;
    int64_t t_max = 0;
    int64_t tmp = k;
    while (tmp > 1) {
        t_max = (t_max + 1);
        tmp = FLOW_CHECKED_SHR((tmp), (1));
    }
    int64_t t = t_max;
    while (t >= 2) {
        int64_t p_max = iroot_i64_i64(k, t);
        if (p_max < 2) {
            t = (t - 1);
            continue;
        }
        int64_t p = 2;
        while (p <= p_max) {
            int64_t d = ipow_i64_i64(p, t);
            int64_t b = FLOW_CHECKED_DIV((k), (d));
            if (b == 0) {
                break;
            }
            int64_t c = (ipow_i64_i64(p, (t + 1)) - ipow_i64_i64((p - 1), (t + 1)));
            int64_t val = (b * c);
            if (val > best) {
                best = val;
            }
            p = (p + 1);
        }
        t = (t - 1);
    }
    return best;
}

int64_t S_val_i64(int64_t k) {
    if (k < 4) {
        return 0;
    }
    if (k <= 1249) {
        return S_val_brute_i64(k);
    }
    int64_t best = 0;
    int64_t p_max3 = iroot_i64_i64(k, 3);
    if (p_max3 >= 2) {
        int64_t P = iroot_i64_i64(k, 4);
        if (P < 2) {
            P = 2;
        }
        if (P > p_max3) {
            P = p_max3;
        }
        int64_t p = 2;
        while (p <= P) {
            int64_t d = ((p * p) * p);
            int64_t b = FLOW_CHECKED_DIV((k), (d));
            int64_t c = (ipow_i64_i64(p, 4) - ipow_i64_i64((p - 1), 4));
            int64_t val = (b * c);
            if (val > best) {
                best = val;
            }
            p = (p + 1);
        }
        int64_t Pp1 = (P + 1);
        int64_t Pp1cubed = ipow_i64_i64(Pp1, 3);
        int64_t b_max = FLOW_CHECKED_DIV((k), (Pp1cubed));
        int64_t b = 1;
        while (b <= b_max) {
            int64_t p2 = iroot_i64_i64(FLOW_CHECKED_DIV((k), (b)), 3);
            if (p2 >= Pp1) {
                int64_t pp = p2;
                if (pp > p_max3) {
                    pp = p_max3;
                }
                int64_t c = (ipow_i64_i64(pp, 4) - ipow_i64_i64((pp - 1), 4));
                int64_t val = (b * c);
                if (val > best) {
                    best = val;
                }
            }
            b = (b + 1);
        }
    }
    int64_t t_max = 0;
    int64_t tmp = k;
    while (tmp > 1) {
        t_max = (t_max + 1);
        tmp = FLOW_CHECKED_SHR((tmp), (1));
    }
    int64_t t = 4;
    while (t <= t_max) {
        int64_t p_max = iroot_i64_i64(k, t);
        if (p_max >= 2) {
            int64_t p = 2;
            while (p <= p_max) {
                int64_t d = ipow_i64_i64(p, t);
                int64_t b = FLOW_CHECKED_DIV((k), (d));
                if (b == 0) {
                    break;
                }
                int64_t c = (ipow_i64_i64(p, (t + 1)) - ipow_i64_i64((p - 1), (t + 1)));
                int64_t val = (b * c);
                if (val > best) {
                    best = val;
                }
                p = (p + 1);
            }
        }
        t = (t + 1);
    }
    return best;
}

int64_t alt_sum_i64_i64(int64_t a, int64_t b) {
    if (a > b) {
        return 0;
    }
    int64_t len = ((b - a) + 1);
    if ((len & 1) == 0) {
        return 0;
    }
    if ((a & 1) == 0) {
        return 1;
    }
    return (-1);
}

int64_t T_i64(int64_t n) {
    if (n < 4) {
        return 0;
    }
    int64_t total = 0;
    int64_t k = 4;
    while (k <= n) {
        int64_t v = S_val_i64(k);
        int64_t step = 1;
        int64_t hi = (k + step);
        if (hi > n) {
            hi = n;
        }
        int64_t v_hi = S_val_i64(hi);
        while ((v_hi == v && hi < n)) {
            step = (step * 2);
            hi = (k + step);
            if (hi > n) {
                hi = n;
            }
            v_hi = S_val_i64(hi);
        }
        if ((hi == n && v_hi == v)) {
            total = (total + (v * alt_sum_i64_i64(k, n)));
            break;
        }
        int64_t lo = (k + 1);
        int64_t r = hi;
        while (lo < r) {
            int64_t mid = FLOW_CHECKED_DIV(((lo + r)), (2));
            if (S_val_i64(mid) == v) {
                lo = (mid + 1);
            } else {
                r = mid;
            }
        }
        total = (total + (v * alt_sum_i64_i64(k, (lo - 1))));
        k = lo;
    }
    return total;
}

int32_t main(void) {
    printf("%lld\n", T_i64(N));
    return 0;
}

Generated MLIR

module {
  llvm.func @printf(!llvm.ptr, ...) -> i32
  llvm.mlir.global internal constant @str_0("%lld\n\00") {addr_space = 0 : i32} : !llvm.array<6 x i8>
  // Constant: N
  llvm.mlir.global internal constant @N(100000000000000000 : i64) : i64
  func.func @ipow128(%arg0: i64, %arg1: i64) -> i128 {
    %0 = arith.constant 1 : i32
    %1 = arith.extsi %0 : i32 to i128
    %2 = llvm.mlir.constant(1 : i64) : i64
    %3 = llvm.alloca %2 x i128 : (i64) -> !llvm.ptr
    llvm.store %1, %3 : i128, !llvm.ptr
    %4 = arith.extsi %arg0 : i64 to i128
    %5 = llvm.mlir.constant(1 : i64) : i64
    %6 = llvm.alloca %5 x i128 : (i64) -> !llvm.ptr
    llvm.store %4, %6 : i128, !llvm.ptr
    %7 = llvm.mlir.constant(1 : i64) : i64
    %8 = llvm.alloca %7 x i64 : (i64) -> !llvm.ptr
    llvm.store %arg1, %8 : i64, !llvm.ptr
    cf.br ^bb0
    ^bb0:
    %9 = llvm.load %8 : !llvm.ptr -> i64
    %10 = arith.constant 0 : i32
    %12 = arith.extsi %10 : i32 to i64
    %11 = arith.cmpi sgt, %9, %12 : i64
    cf.cond_br %11, ^bb1, ^bb2
    ^bb1:
      %13 = llvm.load %8 : !llvm.ptr -> i64
      %14 = arith.constant 1 : i32
      %16 = arith.extsi %14 : i32 to i64
      %15 = arith.andi %13, %16 : i64
      %17 = arith.constant 0 : i32
      %19 = arith.extsi %17 : i32 to i64
      %18 = arith.cmpi ne, %15, %19 : i64
      cf.cond_br %18, ^bb3, ^bb4
      ^bb3:
        %20 = llvm.load %3 : !llvm.ptr -> i128
        %21 = llvm.load %6 : !llvm.ptr -> i128
        %23 = arith.trunci %20 : i128 to i64
        %24 = arith.trunci %21 : i128 to i64
        %22 = arith.muli %23, %24 : i64
        %25 = arith.extsi %22 : i64 to i128
        llvm.store %25, %3 : i128, !llvm.ptr
        cf.br ^bb5
      ^bb4:
        cf.br ^bb5
      ^bb5:
      %26 = llvm.load %6 : !llvm.ptr -> i128
      %27 = llvm.load %6 : !llvm.ptr -> i128
      %29 = arith.trunci %26 : i128 to i64
      %30 = arith.trunci %27 : i128 to i64
      %28 = arith.muli %29, %30 : i64
      %31 = arith.extsi %28 : i64 to i128
      llvm.store %31, %6 : i128, !llvm.ptr
      %32 = llvm.load %8 : !llvm.ptr -> i64
      %33 = arith.constant 1 : i32
      %35 = arith.extsi %33 : i32 to i64
      %34 = arith.shrsi %32, %35 : i64
      llvm.store %34, %8 : i64, !llvm.ptr
      cf.br ^bb0
    ^bb2:
    %36 = llvm.load %3 : !llvm.ptr -> i128
    func.return %36 : i128
  }
  func.func @iroot(%arg0: i64, %arg1: i64) -> i64 {
    %37 = arith.constant 1 : i32
    %39 = arith.extsi %37 : i32 to i64
    %38 = arith.cmpi sle, %arg1, %39 : i64
    cf.cond_br %38, ^bb6, ^bb7
    ^bb6:
      func.return %arg0 : i64
    ^bb7:
      cf.br ^bb8
    ^bb8:
    %40 = arith.constant 0 : i32
    %42 = arith.extsi %40 : i32 to i64
    %41 = arith.cmpi sle, %arg0, %42 : i64
    cf.cond_br %41, ^bb9, ^bb10
    ^bb9:
      %43 = arith.constant 0 : i32
      %44 = arith.extsi %43 : i32 to i64
      func.return %44 : i64
    ^bb10:
      cf.br ^bb11
    ^bb11:
    %45 = arith.constant 1 : i32
    %47 = arith.extsi %45 : i32 to i64
    %46 = arith.cmpi eq, %arg0, %47 : i64
    cf.cond_br %46, ^bb12, ^bb13
    ^bb12:
      %48 = arith.constant 1 : i32
      %49 = arith.extsi %48 : i32 to i64
      func.return %49 : i64
    ^bb13:
      cf.br ^bb14
    ^bb14:
    %50 = arith.constant 1 : i32
    %51 = arith.extsi %50 : i32 to i64
    %52 = llvm.mlir.constant(1 : i64) : i64
    %53 = llvm.alloca %52 x i64 : (i64) -> !llvm.ptr
    llvm.store %51, %53 : i64, !llvm.ptr
    %54 = arith.constant 2 : i32
    %55 = arith.extsi %54 : i32 to i64
    %56 = llvm.mlir.constant(1 : i64) : i64
    %57 = llvm.alloca %56 x i64 : (i64) -> !llvm.ptr
    llvm.store %55, %57 : i64, !llvm.ptr
    cf.br ^bb15
    ^bb15:
    %59 = llvm.load %57 : !llvm.ptr -> i64
    %58 = func.call @ipow128(%59, %arg1) : (i64, i64) -> i128
    %60 = arith.extsi %arg0 : i64 to i128
    %62 = arith.trunci %58 : i128 to i64
    %63 = arith.trunci %60 : i128 to i64
    %61 = arith.cmpi sle, %62, %63 : i64
    cf.cond_br %61, ^bb16, ^bb17
    ^bb16:
      %64 = llvm.load %57 : !llvm.ptr -> i64
      %65 = arith.constant 2000000000 : i32
      %67 = arith.extsi %65 : i32 to i64
      %66 = arith.cmpi sgt, %64, %67 : i64
      cf.cond_br %66, ^bb18, ^bb19
      ^bb18:
        cf.br ^bb17
      ^bb19:
        cf.br ^bb20
      ^bb20:
      %68 = llvm.load %57 : !llvm.ptr -> i64
      %69 = arith.constant 2 : i32
      %71 = arith.extsi %69 : i32 to i64
      %70 = arith.muli %68, %71 : i64
      llvm.store %70, %57 : i64, !llvm.ptr
      cf.br ^bb15
    ^bb17:
    cf.br ^bb21
    ^bb21:
    %72 = llvm.load %53 : !llvm.ptr -> i64
    %73 = arith.constant 1 : i32
    %75 = arith.extsi %73 : i32 to i64
    %74 = arith.addi %72, %75 : i64
    %76 = llvm.load %57 : !llvm.ptr -> i64
    %77 = arith.cmpi slt, %74, %76 : i64
    cf.cond_br %77, ^bb22, ^bb23
    ^bb22:
      %78 = llvm.load %53 : !llvm.ptr -> i64
      %79 = llvm.load %57 : !llvm.ptr -> i64
      %80 = arith.addi %78, %79 : i64
      %81 = arith.constant 2 : i32
      %83 = arith.extsi %81 : i32 to i64
      %82 = arith.divsi %80, %83 : i64
      %84 = func.call @ipow128(%82, %arg1) : (i64, i64) -> i128
      %85 = arith.extsi %arg0 : i64 to i128
      %87 = arith.trunci %84 : i128 to i64
      %88 = arith.trunci %85 : i128 to i64
      %86 = arith.cmpi sle, %87, %88 : i64
      cf.cond_br %86, ^bb24, ^bb25
      ^bb24:
        llvm.store %82, %53 : i64, !llvm.ptr
        cf.br ^bb26
      ^bb25:
        llvm.store %82, %57 : i64, !llvm.ptr
        cf.br ^bb26
      ^bb26:
      cf.br ^bb21
    ^bb23:
    %89 = llvm.load %53 : !llvm.ptr -> i64
    func.return %89 : i64
  }
  func.func @ipow(%arg0: i64, %arg1: i64) -> i64 {
    %90 = arith.constant 1 : i32
    %91 = arith.extsi %90 : i32 to i128
    %92 = llvm.mlir.constant(1 : i64) : i64
    %93 = llvm.alloca %92 x i128 : (i64) -> !llvm.ptr
    llvm.store %91, %93 : i128, !llvm.ptr
    %94 = arith.extsi %arg0 : i64 to i128
    %95 = llvm.mlir.constant(1 : i64) : i64
    %96 = llvm.alloca %95 x i128 : (i64) -> !llvm.ptr
    llvm.store %94, %96 : i128, !llvm.ptr
    %97 = llvm.mlir.constant(1 : i64) : i64
    %98 = llvm.alloca %97 x i64 : (i64) -> !llvm.ptr
    llvm.store %arg1, %98 : i64, !llvm.ptr
    cf.br ^bb27
    ^bb27:
    %99 = llvm.load %98 : !llvm.ptr -> i64
    %100 = arith.constant 0 : i32
    %102 = arith.extsi %100 : i32 to i64
    %101 = arith.cmpi sgt, %99, %102 : i64
    cf.cond_br %101, ^bb28, ^bb29
    ^bb28:
      %103 = llvm.load %98 : !llvm.ptr -> i64
      %104 = arith.constant 1 : i32
      %106 = arith.extsi %104 : i32 to i64
      %105 = arith.andi %103, %106 : i64
      %107 = arith.constant 0 : i32
      %109 = arith.extsi %107 : i32 to i64
      %108 = arith.cmpi ne, %105, %109 : i64
      cf.cond_br %108, ^bb30, ^bb31
      ^bb30:
        %110 = llvm.load %93 : !llvm.ptr -> i128
        %111 = llvm.load %96 : !llvm.ptr -> i128
        %113 = arith.trunci %110 : i128 to i64
        %114 = arith.trunci %111 : i128 to i64
        %112 = arith.muli %113, %114 : i64
        %115 = arith.extsi %112 : i64 to i128
        llvm.store %115, %93 : i128, !llvm.ptr
        cf.br ^bb32
      ^bb31:
        cf.br ^bb32
      ^bb32:
      %116 = llvm.load %96 : !llvm.ptr -> i128
      %117 = llvm.load %96 : !llvm.ptr -> i128
      %119 = arith.trunci %116 : i128 to i64
      %120 = arith.trunci %117 : i128 to i64
      %118 = arith.muli %119, %120 : i64
      %121 = arith.extsi %118 : i64 to i128
      llvm.store %121, %96 : i128, !llvm.ptr
      %122 = llvm.load %98 : !llvm.ptr -> i64
      %123 = arith.constant 1 : i32
      %125 = arith.extsi %123 : i32 to i64
      %124 = arith.shrsi %122, %125 : i64
      llvm.store %124, %98 : i64, !llvm.ptr
      cf.br ^bb27
    ^bb29:
    %126 = llvm.load %93 : !llvm.ptr -> i128
    %127 = arith.trunci %126 : i128 to i64
    func.return %127 : i64
  }
  func.func @S_val_brute(%arg0: i64) -> i64 {
    %128 = arith.constant 4 : i32
    %130 = arith.extsi %128 : i32 to i64
    %129 = arith.cmpi slt, %arg0, %130 : i64
    cf.cond_br %129, ^bb33, ^bb34
    ^bb33:
      %131 = arith.constant 0 : i32
      %132 = arith.extsi %131 : i32 to i64
      func.return %132 : i64
    ^bb34:
      cf.br ^bb35
    ^bb35:
    %133 = arith.constant 0 : i32
    %134 = arith.extsi %133 : i32 to i64
    %135 = llvm.mlir.constant(1 : i64) : i64
    %136 = llvm.alloca %135 x i64 : (i64) -> !llvm.ptr
    llvm.store %134, %136 : i64, !llvm.ptr
    %137 = arith.constant 0 : i32
    %138 = arith.extsi %137 : i32 to i64
    %139 = llvm.mlir.constant(1 : i64) : i64
    %140 = llvm.alloca %139 x i64 : (i64) -> !llvm.ptr
    llvm.store %138, %140 : i64, !llvm.ptr
    %141 = llvm.mlir.constant(1 : i64) : i64
    %142 = llvm.alloca %141 x i64 : (i64) -> !llvm.ptr
    llvm.store %arg0, %142 : i64, !llvm.ptr
    cf.br ^bb36
    ^bb36:
    %143 = llvm.load %142 : !llvm.ptr -> i64
    %144 = arith.constant 1 : i32
    %146 = arith.extsi %144 : i32 to i64
    %145 = arith.cmpi sgt, %143, %146 : i64
    cf.cond_br %145, ^bb37, ^bb38
    ^bb37:
      %147 = llvm.load %140 : !llvm.ptr -> i64
      %148 = arith.constant 1 : i32
      %150 = arith.extsi %148 : i32 to i64
      %149 = arith.addi %147, %150 : i64
      llvm.store %149, %140 : i64, !llvm.ptr
      %151 = llvm.load %142 : !llvm.ptr -> i64
      %152 = arith.constant 1 : i32
      %154 = arith.extsi %152 : i32 to i64
      %153 = arith.shrsi %151, %154 : i64
      llvm.store %153, %142 : i64, !llvm.ptr
      cf.br ^bb36
    ^bb38:
    %155 = llvm.load %140 : !llvm.ptr -> i64
    %156 = llvm.mlir.constant(1 : i64) : i64
    %157 = llvm.alloca %156 x i64 : (i64) -> !llvm.ptr
    llvm.store %155, %157 : i64, !llvm.ptr
    cf.br ^bb39
    ^bb39:
    %158 = llvm.load %157 : !llvm.ptr -> i64
    %159 = arith.constant 2 : i32
    %161 = arith.extsi %159 : i32 to i64
    %160 = arith.cmpi sge, %158, %161 : i64
    cf.cond_br %160, ^bb40, ^bb41
    ^bb40:
      %163 = llvm.load %157 : !llvm.ptr -> i64
      %162 = func.call @iroot(%arg0, %163) : (i64, i64) -> i64
      %164 = arith.constant 2 : i32
      %166 = arith.extsi %164 : i32 to i64
      %165 = arith.cmpi slt, %162, %166 : i64
      cf.cond_br %165, ^bb42, ^bb43
      ^bb42:
        %167 = llvm.load %157 : !llvm.ptr -> i64
        %168 = arith.constant 1 : i32
        %170 = arith.extsi %168 : i32 to i64
        %169 = arith.subi %167, %170 : i64
        llvm.store %169, %157 : i64, !llvm.ptr
        cf.br ^bb39
      ^bb43:
        cf.br ^bb44
      ^bb44:
      %171 = arith.constant 2 : i32
      %172 = arith.extsi %171 : i32 to i64
      %173 = llvm.mlir.constant(1 : i64) : i64
      %174 = llvm.alloca %173 x i64 : (i64) -> !llvm.ptr
      llvm.store %172, %174 : i64, !llvm.ptr
      cf.br ^bb45
      ^bb45:
      %175 = llvm.load %174 : !llvm.ptr -> i64
      %176 = arith.cmpi sle, %175, %162 : i64
      cf.cond_br %176, ^bb46, ^bb47
      ^bb46:
        %178 = llvm.load %174 : !llvm.ptr -> i64
        %179 = llvm.load %157 : !llvm.ptr -> i64
        %177 = func.call @ipow(%178, %179) : (i64, i64) -> i64
        %180 = arith.divsi %arg0, %177 : i64
        %181 = arith.constant 0 : i32
        %183 = arith.extsi %181 : i32 to i64
        %182 = arith.cmpi eq, %180, %183 : i64
        cf.cond_br %182, ^bb48, ^bb49
        ^bb48:
          cf.br ^bb47
        ^bb49:
          cf.br ^bb50
        ^bb50:
        %185 = llvm.load %174 : !llvm.ptr -> i64
        %186 = llvm.load %157 : !llvm.ptr -> i64
        %187 = arith.constant 1 : i32
        %189 = arith.extsi %187 : i32 to i64
        %188 = arith.addi %186, %189 : i64
        %184 = func.call @ipow(%185, %188) : (i64, i64) -> i64
        %191 = llvm.load %174 : !llvm.ptr -> i64
        %192 = arith.constant 1 : i32
        %194 = arith.extsi %192 : i32 to i64
        %193 = arith.subi %191, %194 : i64
        %195 = llvm.load %157 : !llvm.ptr -> i64
        %196 = arith.constant 1 : i32
        %198 = arith.extsi %196 : i32 to i64
        %197 = arith.addi %195, %198 : i64
        %190 = func.call @ipow(%193, %197) : (i64, i64) -> i64
        %199 = arith.subi %184, %190 : i64
        %200 = arith.muli %180, %199 : i64
        %201 = llvm.load %136 : !llvm.ptr -> i64
        %202 = arith.cmpi sgt, %200, %201 : i64
        cf.cond_br %202, ^bb51, ^bb52
        ^bb51:
          llvm.store %200, %136 : i64, !llvm.ptr
          cf.br ^bb53
        ^bb52:
          cf.br ^bb53
        ^bb53:
        %203 = llvm.load %174 : !llvm.ptr -> i64
        %204 = arith.constant 1 : i32
        %206 = arith.extsi %204 : i32 to i64
        %205 = arith.addi %203, %206 : i64
        llvm.store %205, %174 : i64, !llvm.ptr
        cf.br ^bb45
      ^bb47:
      %207 = llvm.load %157 : !llvm.ptr -> i64
      %208 = arith.constant 1 : i32
      %210 = arith.extsi %208 : i32 to i64
      %209 = arith.subi %207, %210 : i64
      llvm.store %209, %157 : i64, !llvm.ptr
      cf.br ^bb39
    ^bb41:
    %211 = llvm.load %136 : !llvm.ptr -> i64
    func.return %211 : i64
  }
  func.func @S_val(%arg0: i64) -> i64 {
    %212 = arith.constant 4 : i32
    %214 = arith.extsi %212 : i32 to i64
    %213 = arith.cmpi slt, %arg0, %214 : i64
    cf.cond_br %213, ^bb54, ^bb55
    ^bb54:
      %215 = arith.constant 0 : i32
      %216 = arith.extsi %215 : i32 to i64
      func.return %216 : i64
    ^bb55:
      cf.br ^bb56
    ^bb56:
    %217 = arith.constant 1249 : i32
    %219 = arith.extsi %217 : i32 to i64
    %218 = arith.cmpi sle, %arg0, %219 : i64
    cf.cond_br %218, ^bb57, ^bb58
    ^bb57:
      %220 = func.call @S_val_brute(%arg0) : (i64) -> i64
      func.return %220 : i64
    ^bb58:
      cf.br ^bb59
    ^bb59:
    %221 = arith.constant 0 : i32
    %222 = arith.extsi %221 : i32 to i64
    %223 = llvm.mlir.constant(1 : i64) : i64
    %224 = llvm.alloca %223 x i64 : (i64) -> !llvm.ptr
    llvm.store %222, %224 : i64, !llvm.ptr
    %226 = arith.constant 3 : i32
    %227 = arith.extsi %226 : i32 to i64
    %225 = func.call @iroot(%arg0, %227) : (i64, i64) -> i64
    %228 = arith.constant 2 : i32
    %230 = arith.extsi %228 : i32 to i64
    %229 = arith.cmpi sge, %225, %230 : i64
    cf.cond_br %229, ^bb60, ^bb61
    ^bb60:
      %232 = arith.constant 4 : i32
      %233 = arith.extsi %232 : i32 to i64
      %231 = func.call @iroot(%arg0, %233) : (i64, i64) -> i64
      %234 = llvm.mlir.constant(1 : i64) : i64
      %235 = llvm.alloca %234 x i64 : (i64) -> !llvm.ptr
      llvm.store %231, %235 : i64, !llvm.ptr
      %236 = llvm.load %235 : !llvm.ptr -> i64
      %237 = arith.constant 2 : i32
      %239 = arith.extsi %237 : i32 to i64
      %238 = arith.cmpi slt, %236, %239 : i64
      cf.cond_br %238, ^bb63, ^bb64
      ^bb63:
        %240 = arith.constant 2 : i32
        %241 = arith.extsi %240 : i32 to i64
        llvm.store %241, %235 : i64, !llvm.ptr
        cf.br ^bb65
      ^bb64:
        cf.br ^bb65
      ^bb65:
      %242 = llvm.load %235 : !llvm.ptr -> i64
      %243 = arith.cmpi sgt, %242, %225 : i64
      cf.cond_br %243, ^bb66, ^bb67
      ^bb66:
        llvm.store %225, %235 : i64, !llvm.ptr
        cf.br ^bb68
      ^bb67:
        cf.br ^bb68
      ^bb68:
      %244 = arith.constant 2 : i32
      %245 = arith.extsi %244 : i32 to i64
      %246 = llvm.mlir.constant(1 : i64) : i64
      %247 = llvm.alloca %246 x i64 : (i64) -> !llvm.ptr
      llvm.store %245, %247 : i64, !llvm.ptr
      cf.br ^bb69
      ^bb69:
      %248 = llvm.load %247 : !llvm.ptr -> i64
      %249 = llvm.load %235 : !llvm.ptr -> i64
      %250 = arith.cmpi sle, %248, %249 : i64
      cf.cond_br %250, ^bb70, ^bb71
      ^bb70:
        %251 = llvm.load %247 : !llvm.ptr -> i64
        %252 = llvm.load %247 : !llvm.ptr -> i64
        %253 = arith.muli %251, %252 : i64
        %254 = llvm.load %247 : !llvm.ptr -> i64
        %255 = arith.muli %253, %254 : i64
        %256 = arith.divsi %arg0, %255 : i64
        %258 = llvm.load %247 : !llvm.ptr -> i64
        %259 = arith.constant 4 : i32
        %260 = arith.extsi %259 : i32 to i64
        %257 = func.call @ipow(%258, %260) : (i64, i64) -> i64
        %262 = llvm.load %247 : !llvm.ptr -> i64
        %263 = arith.constant 1 : i32
        %265 = arith.extsi %263 : i32 to i64
        %264 = arith.subi %262, %265 : i64
        %266 = arith.constant 4 : i32
        %267 = arith.extsi %266 : i32 to i64
        %261 = func.call @ipow(%264, %267) : (i64, i64) -> i64
        %268 = arith.subi %257, %261 : i64
        %269 = arith.muli %256, %268 : i64
        %270 = llvm.load %224 : !llvm.ptr -> i64
        %271 = arith.cmpi sgt, %269, %270 : i64
        cf.cond_br %271, ^bb72, ^bb73
        ^bb72:
          llvm.store %269, %224 : i64, !llvm.ptr
          cf.br ^bb74
        ^bb73:
          cf.br ^bb74
        ^bb74:
        %272 = llvm.load %247 : !llvm.ptr -> i64
        %273 = arith.constant 1 : i32
        %275 = arith.extsi %273 : i32 to i64
        %274 = arith.addi %272, %275 : i64
        llvm.store %274, %247 : i64, !llvm.ptr
        cf.br ^bb69
      ^bb71:
      %276 = llvm.load %235 : !llvm.ptr -> i64
      %277 = arith.constant 1 : i32
      %279 = arith.extsi %277 : i32 to i64
      %278 = arith.addi %276, %279 : i64
      %281 = arith.constant 3 : i32
      %282 = arith.extsi %281 : i32 to i64
      %280 = func.call @ipow(%278, %282) : (i64, i64) -> i64
      %283 = arith.divsi %arg0, %280 : i64
      %284 = arith.constant 1 : i32
      %285 = arith.extsi %284 : i32 to i64
      %286 = llvm.mlir.constant(1 : i64) : i64
      %287 = llvm.alloca %286 x i64 : (i64) -> !llvm.ptr
      llvm.store %285, %287 : i64, !llvm.ptr
      cf.br ^bb75
      ^bb75:
      %288 = llvm.load %287 : !llvm.ptr -> i64
      %289 = arith.cmpi sle, %288, %283 : i64
      cf.cond_br %289, ^bb76, ^bb77
      ^bb76:
        %291 = llvm.load %287 : !llvm.ptr -> i64
        %292 = arith.divsi %arg0, %291 : i64
        %293 = arith.constant 3 : i32
        %294 = arith.extsi %293 : i32 to i64
        %290 = func.call @iroot(%292, %294) : (i64, i64) -> i64
        %295 = arith.cmpi sge, %290, %278 : i64
        cf.cond_br %295, ^bb78, ^bb79
        ^bb78:
          %296 = llvm.mlir.constant(1 : i64) : i64
          %297 = llvm.alloca %296 x i64 : (i64) -> !llvm.ptr
          llvm.store %290, %297 : i64, !llvm.ptr
          %298 = llvm.load %297 : !llvm.ptr -> i64
          %299 = arith.cmpi sgt, %298, %225 : i64
          cf.cond_br %299, ^bb81, ^bb82
          ^bb81:
            llvm.store %225, %297 : i64, !llvm.ptr
            cf.br ^bb83
          ^bb82:
            cf.br ^bb83
          ^bb83:
          %301 = llvm.load %297 : !llvm.ptr -> i64
          %302 = arith.constant 4 : i32
          %303 = arith.extsi %302 : i32 to i64
          %300 = func.call @ipow(%301, %303) : (i64, i64) -> i64
          %305 = llvm.load %297 : !llvm.ptr -> i64
          %306 = arith.constant 1 : i32
          %308 = arith.extsi %306 : i32 to i64
          %307 = arith.subi %305, %308 : i64
          %309 = arith.constant 4 : i32
          %310 = arith.extsi %309 : i32 to i64
          %304 = func.call @ipow(%307, %310) : (i64, i64) -> i64
          %311 = arith.subi %300, %304 : i64
          %312 = llvm.load %287 : !llvm.ptr -> i64
          %313 = arith.muli %312, %311 : i64
          %314 = llvm.load %224 : !llvm.ptr -> i64
          %315 = arith.cmpi sgt, %313, %314 : i64
          cf.cond_br %315, ^bb84, ^bb85
          ^bb84:
            llvm.store %313, %224 : i64, !llvm.ptr
            cf.br ^bb86
          ^bb85:
            cf.br ^bb86
          ^bb86:
          cf.br ^bb80
        ^bb79:
          cf.br ^bb80
        ^bb80:
        %316 = llvm.load %287 : !llvm.ptr -> i64
        %317 = arith.constant 1 : i32
        %319 = arith.extsi %317 : i32 to i64
        %318 = arith.addi %316, %319 : i64
        llvm.store %318, %287 : i64, !llvm.ptr
        cf.br ^bb75
      ^bb77:
      cf.br ^bb62
    ^bb61:
      cf.br ^bb62
    ^bb62:
    %320 = arith.constant 0 : i32
    %321 = arith.extsi %320 : i32 to i64
    %322 = llvm.mlir.constant(1 : i64) : i64
    %323 = llvm.alloca %322 x i64 : (i64) -> !llvm.ptr
    llvm.store %321, %323 : i64, !llvm.ptr
    %324 = llvm.mlir.constant(1 : i64) : i64
    %325 = llvm.alloca %324 x i64 : (i64) -> !llvm.ptr
    llvm.store %arg0, %325 : i64, !llvm.ptr
    cf.br ^bb87
    ^bb87:
    %326 = llvm.load %325 : !llvm.ptr -> i64
    %327 = arith.constant 1 : i32
    %329 = arith.extsi %327 : i32 to i64
    %328 = arith.cmpi sgt, %326, %329 : i64
    cf.cond_br %328, ^bb88, ^bb89
    ^bb88:
      %330 = llvm.load %323 : !llvm.ptr -> i64
      %331 = arith.constant 1 : i32
      %333 = arith.extsi %331 : i32 to i64
      %332 = arith.addi %330, %333 : i64
      llvm.store %332, %323 : i64, !llvm.ptr
      %334 = llvm.load %325 : !llvm.ptr -> i64
      %335 = arith.constant 1 : i32
      %337 = arith.extsi %335 : i32 to i64
      %336 = arith.shrsi %334, %337 : i64
      llvm.store %336, %325 : i64, !llvm.ptr
      cf.br ^bb87
    ^bb89:
    %338 = arith.constant 4 : i32
    %339 = arith.extsi %338 : i32 to i64
    %340 = llvm.mlir.constant(1 : i64) : i64
    %341 = llvm.alloca %340 x i64 : (i64) -> !llvm.ptr
    llvm.store %339, %341 : i64, !llvm.ptr
    cf.br ^bb90
    ^bb90:
    %342 = llvm.load %341 : !llvm.ptr -> i64
    %343 = llvm.load %323 : !llvm.ptr -> i64
    %344 = arith.cmpi sle, %342, %343 : i64
    cf.cond_br %344, ^bb91, ^bb92
    ^bb91:
      %346 = llvm.load %341 : !llvm.ptr -> i64
      %345 = func.call @iroot(%arg0, %346) : (i64, i64) -> i64
      %347 = arith.constant 2 : i32
      %349 = arith.extsi %347 : i32 to i64
      %348 = arith.cmpi sge, %345, %349 : i64
      cf.cond_br %348, ^bb93, ^bb94
      ^bb93:
        %350 = arith.constant 2 : i32
        %351 = arith.extsi %350 : i32 to i64
        %352 = llvm.mlir.constant(1 : i64) : i64
        %353 = llvm.alloca %352 x i64 : (i64) -> !llvm.ptr
        llvm.store %351, %353 : i64, !llvm.ptr
        cf.br ^bb96
        ^bb96:
        %354 = llvm.load %353 : !llvm.ptr -> i64
        %355 = arith.cmpi sle, %354, %345 : i64
        cf.cond_br %355, ^bb97, ^bb98
        ^bb97:
          %357 = llvm.load %353 : !llvm.ptr -> i64
          %358 = llvm.load %341 : !llvm.ptr -> i64
          %356 = func.call @ipow(%357, %358) : (i64, i64) -> i64
          %359 = arith.divsi %arg0, %356 : i64
          %360 = arith.constant 0 : i32
          %362 = arith.extsi %360 : i32 to i64
          %361 = arith.cmpi eq, %359, %362 : i64
          cf.cond_br %361, ^bb99, ^bb100
          ^bb99:
            cf.br ^bb98
          ^bb100:
            cf.br ^bb101
          ^bb101:
          %364 = llvm.load %353 : !llvm.ptr -> i64
          %365 = llvm.load %341 : !llvm.ptr -> i64
          %366 = arith.constant 1 : i32
          %368 = arith.extsi %366 : i32 to i64
          %367 = arith.addi %365, %368 : i64
          %363 = func.call @ipow(%364, %367) : (i64, i64) -> i64
          %370 = llvm.load %353 : !llvm.ptr -> i64
          %371 = arith.constant 1 : i32
          %373 = arith.extsi %371 : i32 to i64
          %372 = arith.subi %370, %373 : i64
          %374 = llvm.load %341 : !llvm.ptr -> i64
          %375 = arith.constant 1 : i32
          %377 = arith.extsi %375 : i32 to i64
          %376 = arith.addi %374, %377 : i64
          %369 = func.call @ipow(%372, %376) : (i64, i64) -> i64
          %378 = arith.subi %363, %369 : i64
          %379 = arith.muli %359, %378 : i64
          %380 = llvm.load %224 : !llvm.ptr -> i64
          %381 = arith.cmpi sgt, %379, %380 : i64
          cf.cond_br %381, ^bb102, ^bb103
          ^bb102:
            llvm.store %379, %224 : i64, !llvm.ptr
            cf.br ^bb104
          ^bb103:
            cf.br ^bb104
          ^bb104:
          %382 = llvm.load %353 : !llvm.ptr -> i64
          %383 = arith.constant 1 : i32
          %385 = arith.extsi %383 : i32 to i64
          %384 = arith.addi %382, %385 : i64
          llvm.store %384, %353 : i64, !llvm.ptr
          cf.br ^bb96
        ^bb98:
        cf.br ^bb95
      ^bb94:
        cf.br ^bb95
      ^bb95:
      %386 = llvm.load %341 : !llvm.ptr -> i64
      %387 = arith.constant 1 : i32
      %389 = arith.extsi %387 : i32 to i64
      %388 = arith.addi %386, %389 : i64
      llvm.store %388, %341 : i64, !llvm.ptr
      cf.br ^bb90
    ^bb92:
    %390 = llvm.load %224 : !llvm.ptr -> i64
    func.return %390 : i64
  }
  func.func @alt_sum(%arg0: i64, %arg1: i64) -> i64 {
    %391 = arith.cmpi sgt, %arg0, %arg1 : i64
    cf.cond_br %391, ^bb105, ^bb106
    ^bb105:
      %392 = arith.constant 0 : i32
      %393 = arith.extsi %392 : i32 to i64
      func.return %393 : i64
    ^bb106:
      cf.br ^bb107
    ^bb107:
    %394 = arith.subi %arg1, %arg0 : i64
    %395 = arith.constant 1 : i32
    %397 = arith.extsi %395 : i32 to i64
    %396 = arith.addi %394, %397 : i64
    %398 = arith.constant 1 : i32
    %400 = arith.extsi %398 : i32 to i64
    %399 = arith.andi %396, %400 : i64
    %401 = arith.constant 0 : i32
    %403 = arith.extsi %401 : i32 to i64
    %402 = arith.cmpi eq, %399, %403 : i64
    cf.cond_br %402, ^bb108, ^bb109
    ^bb108:
      %404 = arith.constant 0 : i32
      %405 = arith.extsi %404 : i32 to i64
      func.return %405 : i64
    ^bb109:
      cf.br ^bb110
    ^bb110:
    %406 = arith.constant 1 : i32
    %408 = arith.extsi %406 : i32 to i64
    %407 = arith.andi %arg0, %408 : i64
    %409 = arith.constant 0 : i32
    %411 = arith.extsi %409 : i32 to i64
    %410 = arith.cmpi eq, %407, %411 : i64
    cf.cond_br %410, ^bb111, ^bb112
    ^bb111:
      %412 = arith.constant 1 : i32
      %413 = arith.extsi %412 : i32 to i64
      func.return %413 : i64
    ^bb112:
      cf.br ^bb113
    ^bb113:
    %414 = arith.constant 1 : i32
    %416 = arith.constant 0 : i32
    %415 = arith.subi %416, %414 : i32
    %417 = arith.extsi %415 : i32 to i64
    func.return %417 : i64
  }
  func.func @T(%arg0: i64) -> i64 {
    %418 = arith.constant 4 : i32
    %420 = arith.extsi %418 : i32 to i64
    %419 = arith.cmpi slt, %arg0, %420 : i64
    cf.cond_br %419, ^bb114, ^bb115
    ^bb114:
      %421 = arith.constant 0 : i32
      %422 = arith.extsi %421 : i32 to i64
      func.return %422 : i64
    ^bb115:
      cf.br ^bb116
    ^bb116:
    %423 = arith.constant 0 : i32
    %424 = arith.extsi %423 : i32 to i64
    %425 = llvm.mlir.constant(1 : i64) : i64
    %426 = llvm.alloca %425 x i64 : (i64) -> !llvm.ptr
    llvm.store %424, %426 : i64, !llvm.ptr
    %427 = arith.constant 4 : i32
    %428 = arith.extsi %427 : i32 to i64
    %429 = llvm.mlir.constant(1 : i64) : i64
    %430 = llvm.alloca %429 x i64 : (i64) -> !llvm.ptr
    llvm.store %428, %430 : i64, !llvm.ptr
    cf.br ^bb117
    ^bb117:
    %431 = llvm.load %430 : !llvm.ptr -> i64
    %432 = arith.cmpi sle, %431, %arg0 : i64
    cf.cond_br %432, ^bb118, ^bb119
    ^bb118:
      %434 = llvm.load %430 : !llvm.ptr -> i64
      %433 = func.call @S_val(%434) : (i64) -> i64
      %435 = arith.constant 1 : i32
      %436 = arith.extsi %435 : i32 to i64
      %437 = llvm.mlir.constant(1 : i64) : i64
      %438 = llvm.alloca %437 x i64 : (i64) -> !llvm.ptr
      llvm.store %436, %438 : i64, !llvm.ptr
      %439 = llvm.load %430 : !llvm.ptr -> i64
      %440 = llvm.load %438 : !llvm.ptr -> i64
      %441 = arith.addi %439, %440 : i64
      %442 = llvm.mlir.constant(1 : i64) : i64
      %443 = llvm.alloca %442 x i64 : (i64) -> !llvm.ptr
      llvm.store %441, %443 : i64, !llvm.ptr
      %444 = llvm.load %443 : !llvm.ptr -> i64
      %445 = arith.cmpi sgt, %444, %arg0 : i64
      cf.cond_br %445, ^bb120, ^bb121
      ^bb120:
        llvm.store %arg0, %443 : i64, !llvm.ptr
        cf.br ^bb122
      ^bb121:
        cf.br ^bb122
      ^bb122:
      %447 = llvm.load %443 : !llvm.ptr -> i64
      %446 = func.call @S_val(%447) : (i64) -> i64
      %448 = llvm.mlir.constant(1 : i64) : i64
      %449 = llvm.alloca %448 x i64 : (i64) -> !llvm.ptr
      llvm.store %446, %449 : i64, !llvm.ptr
      cf.br ^bb123
      ^bb123:
      %450 = llvm.load %449 : !llvm.ptr -> i64
      %451 = arith.cmpi eq, %450, %433 : i64
      %452 = scf.if %451 -> (i1) {
        %453 = llvm.load %443 : !llvm.ptr -> i64
        %454 = arith.cmpi slt, %453, %arg0 : i64
        scf.yield %454 : i1
      } else {
        %455 = arith.constant false
        scf.yield %455 : i1
      }
      cf.cond_br %452, ^bb124, ^bb125
      ^bb124:
        %456 = llvm.load %438 : !llvm.ptr -> i64
        %457 = arith.constant 2 : i32
        %459 = arith.extsi %457 : i32 to i64
        %458 = arith.muli %456, %459 : i64
        llvm.store %458, %438 : i64, !llvm.ptr
        %460 = llvm.load %430 : !llvm.ptr -> i64
        %461 = llvm.load %438 : !llvm.ptr -> i64
        %462 = arith.addi %460, %461 : i64
        llvm.store %462, %443 : i64, !llvm.ptr
        %463 = llvm.load %443 : !llvm.ptr -> i64
        %464 = arith.cmpi sgt, %463, %arg0 : i64
        cf.cond_br %464, ^bb126, ^bb127
        ^bb126:
          llvm.store %arg0, %443 : i64, !llvm.ptr
          cf.br ^bb128
        ^bb127:
          cf.br ^bb128
        ^bb128:
        %466 = llvm.load %443 : !llvm.ptr -> i64
        %465 = func.call @S_val(%466) : (i64) -> i64
        llvm.store %465, %449 : i64, !llvm.ptr
        cf.br ^bb123
      ^bb125:
      %467 = llvm.load %443 : !llvm.ptr -> i64
      %468 = arith.cmpi eq, %467, %arg0 : i64
      %469 = scf.if %468 -> (i1) {
        %470 = llvm.load %449 : !llvm.ptr -> i64
        %471 = arith.cmpi eq, %470, %433 : i64
        scf.yield %471 : i1
      } else {
        %472 = arith.constant false
        scf.yield %472 : i1
      }
      cf.cond_br %469, ^bb129, ^bb130
      ^bb129:
        %473 = llvm.load %426 : !llvm.ptr -> i64
        %475 = llvm.load %430 : !llvm.ptr -> i64
        %474 = func.call @alt_sum(%475, %arg0) : (i64, i64) -> i64
        %476 = arith.muli %433, %474 : i64
        %477 = arith.addi %473, %476 : i64
        llvm.store %477, %426 : i64, !llvm.ptr
        cf.br ^bb119
      ^bb130:
        cf.br ^bb131
      ^bb131:
      %478 = llvm.load %430 : !llvm.ptr -> i64
      %479 = arith.constant 1 : i32
      %481 = arith.extsi %479 : i32 to i64
      %480 = arith.addi %478, %481 : i64
      %482 = llvm.mlir.constant(1 : i64) : i64
      %483 = llvm.alloca %482 x i64 : (i64) -> !llvm.ptr
      llvm.store %480, %483 : i64, !llvm.ptr
      %484 = llvm.load %443 : !llvm.ptr -> i64
      %485 = llvm.mlir.constant(1 : i64) : i64
      %486 = llvm.alloca %485 x i64 : (i64) -> !llvm.ptr
      llvm.store %484, %486 : i64, !llvm.ptr
      cf.br ^bb132
      ^bb132:
      %487 = llvm.load %483 : !llvm.ptr -> i64
      %488 = llvm.load %486 : !llvm.ptr -> i64
      %489 = arith.cmpi slt, %487, %488 : i64
      cf.cond_br %489, ^bb133, ^bb134
      ^bb133:
        %490 = llvm.load %483 : !llvm.ptr -> i64
        %491 = llvm.load %486 : !llvm.ptr -> i64
        %492 = arith.addi %490, %491 : i64
        %493 = arith.constant 2 : i32
        %495 = arith.extsi %493 : i32 to i64
        %494 = arith.divsi %492, %495 : i64
        %496 = func.call @S_val(%494) : (i64) -> i64
        %497 = arith.cmpi eq, %496, %433 : i64
        cf.cond_br %497, ^bb135, ^bb136
        ^bb135:
          %498 = arith.constant 1 : i32
          %500 = arith.extsi %498 : i32 to i64
          %499 = arith.addi %494, %500 : i64
          llvm.store %499, %483 : i64, !llvm.ptr
          cf.br ^bb137
        ^bb136:
          llvm.store %494, %486 : i64, !llvm.ptr
          cf.br ^bb137
        ^bb137:
        cf.br ^bb132
      ^bb134:
      %501 = llvm.load %426 : !llvm.ptr -> i64
      %503 = llvm.load %430 : !llvm.ptr -> i64
      %504 = llvm.load %483 : !llvm.ptr -> i64
      %505 = arith.constant 1 : i32
      %507 = arith.extsi %505 : i32 to i64
      %506 = arith.subi %504, %507 : i64
      %502 = func.call @alt_sum(%503, %506) : (i64, i64) -> i64
      %508 = arith.muli %433, %502 : i64
      %509 = arith.addi %501, %508 : i64
      llvm.store %509, %426 : i64, !llvm.ptr
      %510 = llvm.load %483 : !llvm.ptr -> i64
      llvm.store %510, %430 : i64, !llvm.ptr
      cf.br ^bb117
    ^bb119:
    %511 = llvm.load %426 : !llvm.ptr -> i64
    func.return %511 : i64
  }
  func.func @main() -> i32 {
    %512 = llvm.mlir.addressof @str_0 : !llvm.ptr
    %514 = llvm.mlir.addressof @N : !llvm.ptr
    %515 = llvm.load %514 : !llvm.ptr -> i64
    %513 = func.call @T(%515) : (i64) -> i64
    %516 = llvm.call @printf(%512, %513) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
    %517 = arith.constant 0 : i32
    func.return %517 : i32
  }
}