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}$$

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

Problem 7 asks:

What is the 10 001^{st} 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.

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.

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

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

Problem 4 asks:

Find the largest palindrome made from the product of two 3-digit numbers.

I solved this with a simple brute force solution in Java:

public class Problem4 {
public static void main(String[] args) {
int product, rProduct, temp;
int result = 0;
for (int a = 100; a < 1000; a++) {
// start from `a' to avoid duplicates
for (int b = a; b < 1000; b++) {
product = a * b;
temp = product;
rProduct = 0;
while (temp > 0) {
rProduct = rProduct * 10 + temp % 10;
temp = temp / 10;
}
if (product == rProduct && product > result) {
result = product;
}
}
}
System.out.println(result);
}
}

I would try to come up with a more efficient solution if the numbers were bigger, but as is it runs in under a tenth of a second.

Problem 3 asks:

What is the largest prime factor of the number 600 851 475 143?

Here’s what I did in Java:

public class Problem3 {
public static void main(String[] args) {
long number = 600851475143L;
int result = 0;
for (int factor = 2; factor <= number; factor++) {
if (number % factor == 0) {
result = factor;
number /= factor;
factor = 2;
}
}
System.out.println(result);
}
}

This required a little more thought to write efficiently, but my solution turned out very simple so it’s easy to follow.

Problem 2 asks:

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Another straight forward problem, here's my solution:

public class Problem2 {
public static void main(String[] args) {
int n = 1, m = 2;
int sum = 0;
int temp;
while (m <= 4_000_000) {
if (m % 2 == 0) sum += m;
temp = n;
n = m;
m += temp;
}
System.out.println(sum);
}
}

With n and m being the n^{th} and (n+1)^{th} term in the sequence respectively.

Problem 17 asks:

If all the numbers from 1 to 1 000 (one thousand) inclusive were written out in words, how many letters would be used?

This problem can be solved by hand. I essentially used Python as a calculator to solve it:

len("onethousand" + 900*"hundred" + 190*"onetwothreefourfivesixseveneightnine" +
100*"twentythirtyfortyfiftysixtyseventyeightyninety" + 891*"and" +
10*"teneleventwelvethirteenfourteenfifteensixteenseventeeneighteennineteen")