# Shobute☘

## Project Euler / 461

Let $$f_n(k) = e^{k/n} - 1$$, for all non-negative integers $$k$$.

Let $$g(n) = a^2 + b^2 + c^2 + d^2$$ for $$a, b, c, d$$ that minimize: $$| f_n(a) + f_n(b) + f_n(c) + f_n(d) - \pi |$$.

Find $$g(10000)$$.

I solved this using C:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define SIZE (15000/2 * (15000 + 1))
#define PI 3.14159265358979323846

int cmp (const void *a, const void *b) {
const double *da = (const double *) a;
const double *db = (const double *) b;

return (da > db) - (da < db);
}

int main (void) {
double *sums, f[15000], bestError;
int a, b, c, d, bestI, bestMid;

for (int i = 0; i < 15000; i++) {
f[i] = exp((double)i/10000) - 1;
}

sums = malloc(SIZE * sizeof(double));
for (int i = 0, k = 0; i < 15000; i++) {
for (int j = i; j < 15000; j++) {
sums[k++] = f[i] + f[j];
}
}

qsort(sums, SIZE, sizeof(double), cmp);

bestError = 1;
for (int i = 0; i < SIZE; i++) {
int min = 0;
int max = SIZE;
int mid;
while (max >= min) {
mid = (min + max) / 2;
if (sums[i] + sums[mid] <= PI) min = mid + 1;
else max = mid -1;
}
double error = fabs(sums[i] + sums[mid] - PI);
if (error < bestError) {
bestError = error;
bestI = i;
bestMid = mid;
}
}

for (int i = 0; i < 15000; i++) {
for (int j = i; j < 15000; j++) {
if (sums[bestI] == f[i] + f[j]) {
a = i;
b = j;
}
if (sums[bestMid] == f[i] + f[j]) {
c = i;
d = j;
}
}
}

printf("%d² + %d² + %d² + %d² = %d\n", a, b, c, d, a*a + b*b + c*c + d*d);

return 0;
}


It runs in 23 seconds (on a 3.5 GHz CPU).

Last updated on .