Shobute 🍻

Project-Euler / 461

Problem 461 asks:

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).