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

Last updated on .


Favourite Quotations

I will update this posts with quotes I like when I come across them. In no particular order:

Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away.

I do my thing and you do your thing.
I am not in this world to live up to your expectations,
And you are not in this world to live up to mine.
You are you, and I am I, and if by chance we find each other, it's beautiful.
If not, it can't be helped.

Once the game is over, the king and the pawn go back in the same box.

For instance, on the planet Earth, man had always assumed that he was more intelligent than dolphins because he had achieved so much -- the wheel, New York, wars and so on -- whilst all the dolphins had ever done was muck about in the water having a good time. But conversely, the dolphins had always believed that they were far more intelligent than man -- for precisely the same reasons.

Last updated on .


Update Files In Vim Without Changing Modification Date

The backend of is very simple, all the blog posts are HTML files stored in the directory posts/, the modification time of each file is used to tell when they were last updated.

Occasionally I want to make a very small change to a file without updating its modification time, I wrote the following Vim function to do that:

function! WriteSmall()
    let mtime = system("date -d @`stat -c %Y ".shellescape(expand('%:p')) . "`")
    write
    call system("touch --date='".mtime."' ".shellescape(expand('%:p')))
endfunction
map <F4> :call WriteSmall()<CR>

I’m sure there are other uses for it. You can put it in your Vim configuration and then press F4 (or map it to another key) every time you want to write the file without updating the modification time. It assumes you have date, stat and touch from the GNU userland.

Last updated on .


Project Euler 9

Problem 9 asks:

There exists exactly one Pythagorean triplet for which \(a + b + c = 1000\). Find the product \(abc\).

I solved this with pen and paper.

I already know a Pythagorean triplet \((a, b, c)\) can be written as \(k(2mn, m^2-n^2, m^2+n^2)\) where \(k, m, n \in \mathbb{N} \cdot m > n\) by Euclid’s formula, so using that fact:$$a + b + c = 1000$$ can be writen as, $$\begin{align}&2mn + m^2 - n^2 + m^2 + n^2 = 1000\\ \implies &m(m + n) = 500\\ \implies &m = 20, n = 5\end{align}$$ therefore, $$\begin{align}a &= 2\times20\times5 = 200\\ b &= 20^2 - 5^2 = 375\\ c &= 20^2 + 5^2 = 425\\ abc &= 200\times375\times425 = 31875000\end{align}$$

Last updated on .


Project Euler 8

Problem 8 asks:

Find the greatest product of five consecutive digits in the 1000-digit number.

7316717653133062491922511[…]3600823257530420752963450

I did a simple bruteforce in Java:

import java.nio.file.*;
import java.io.IOException;

public class Problem8 {
    public static void main(String[] args) {
        Path path = Paths.get("problem8.txt");
        try {
            byte[] bigNum = Files.readAllBytes(path);
            int result = 0;
            for (int i=0; i<bigNum.length-5; i++) {
                int product = 1;
                for (int j=i; j<i+5; j++) product *= bigNum[j] - '0';
                if (product > result) result = product;
            }
            System.out.println(result);
        } catch (IOException ex) {
            ex.printStackTrace();
        }
    }
}

No optimizations and runs in under 0.14 seconds (on a 2.26GHz CPU).

Last updated on .


Project Euler 7

Problem 7 asks:

What is the 10 001st prime number?

Here’s my solution in Java:

import static java.lang.Math.sqrt;

public class Problem7 {
    public static void main(String[] args) {
        int count = 0;
        int div = 1;
        int result = 1;
        while (count < 10_001) {
            result++;
            for (div=(int)sqrt(result); div>0; div--)
                if (result % div == 0) break;
            if (div == 1) count++;
        }
        System.out.println(result);
    }
}

The only thing to note is I’m dividing from \(\lfloor\sqrt n\rfloor\) (and down to 1) to check if \(n\) is prime. The reason I don’t need to check more than that is if \(d\) is a divisor of \(n\) then \(\tfrac{n}{d}\) is also a divisor of \(n\). This substantially speeds up the program.

Last updated on .


Project Euler 6

Problem 6 asks:

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

This has been the simplest problem so far, here’s my straight forward solution in Java:

public class Problem6 {
    public static void main(String[] args) {
        int sumOfSqs = 0;
        int sqOfSum = 0;
        for (int i=1; i<=100; i++) {
            sumOfSqs += i * i;
            sqOfSum += i;
        }
        sqOfSum *= sqOfSum;
        System.out.println(sqOfSum - sumOfSqs);
    }
}

I decided to try and find the general case. I know from school that the sum of the natural numbers 1 to n is \(\tfrac{1}{2}n(n+1)\), so the square of the sum is \(\tfrac{1}{4}n^2(n+1)^2\). I didn’t know how to go about making a general formula for the sum of squares, so I cheated and looked on Wikipedia, I found Faulhaber’s formula which gives me the sum of squares being \(\tfrac{1}{6}n(n+1)(2n+1)\). Which implies $$\begin{align}s - t &= (\tfrac{1}{2}n(n+1))^2 - \tfrac{1}{6}n(n+1)(2n+1)\\ &= \tfrac{1}{12}n(n+1)(3n+2)(n-1)\end{align}$$ Where \(s\) is the square of the sum, and \(t\) is the sum of squares.

Now with that groundwork done it’s simple to solve this problem for very big n in a very fast time.

Last updated on .


Project Euler 5

Problem 5 asks:

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

I did another brute-force solution in Java, not the most elegant way to solve it, but it runs in a third of a second on my computer:

public class Problem5 {
    public static void main(String[] args) {
        int div = 3;
        for (int result=20; div<20; result+=20) {
            for (div=3; result%div==0; div++) {
                if (div == 19) System.out.println(result);
            }
        }
    }
}

One thing to note is the outer loop increments by 20 because you know 20 will have to be a factor, so it saves a lot of time checking unnecessary numbers (and division can start from 3 because if it’s divisible by 20 it’s divisible by 2).

Last updated on .