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

Problem 16 asks:

What is the sum of the digits of the number 2^{1000}?

Very easy in Java thanks to `BigInteger`

:

import java.math.BigInteger;
public class Problem16 {
public static void main(String[] args) {
BigInteger number = new BigInteger("2").pow(1000);
int sum = 0;
while (number.compareTo(BigInteger.ZERO) > 0) {
sum += number.remainder(BigInteger.TEN).intValue();
number = number.divide(BigInteger.TEN);
}
System.out.println(sum);
}
}

Problem 15 asks:

Starting in the top left corner of a 2×2 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 20×20 grid?

If you know anything about combinations in mathematics this problem is easy to solve without a line of code. You just use the binomial coefficient: $$\binom{40}{20} = \frac{40!}{20!^2}$$

Problem 14 asks:

The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even)

n → 3n + 1 (n is odd)

Which starting number, under one million, produces the longest chain?

Here’s my solution in Java:

public class Problem14 {
public static void main(String[] args) {
final int MAX = 1_000_000;
int longestChain = 0;
int result = -1;
int cache[] = new int[MAX];
for (int n = 2; n < MAX; n++) {
int terms = 1;
long m = n;
while (m >= n) {
m = (m % 2 == 0) ? m / 2 : 3 * m + 1;
terms++;
}
terms += cache[(int)m]; // safe to cast because m < n
cache[n] = terms;
if (terms > longestChain) {
longestChain = terms;
result = n;
}
}
System.out.println(result);
}
}

It stores the results it finds as it goes, so it doesn’t have to repeat the same computations.

Problem 13 asks:

Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.

Here’s my solution in Java, I left out a lot of the numbers for clarity’s sake:

public class Problem13 {
private static double[] NUMS = {
37107287.533902102798797998220837590246510135740250,
46376937.677490009712648124896970078050417018260538,
/* 96 other numbers go here... */
20849603.980134001723930671666823555245252804609722,
53503534.226472524250874054075591789781264330331690
};
public static void main(String[] args) {
double sum = 0;
for (double num : NUMS) sum += num;
System.out.println((long)sum);
}
}

It almost feels like cheating by storing the numbers as doubles but it works well because precision is not important and by putting the decimal point after 8 digits I end up with 10 digits after adding together 10^{2} of them.

Problem 12 asks:

What is the value of the first triangle number to have over five hundred divisors?

Here’s my solution in Java:

public class Problem12 {
public static void main(String[] args) {
int triangle = 0;
for (int n = 1, numFactors = 0; numFactors <= 500; n++) {
triangle = n * (n + 1) / 2;
numFactors = 2;
for (int div = 2; div * div <= triangle; div++) {
if (triangle % div == 0) numFactors += 2;
}
}
System.out.println(triangle);
}
}

Problem 11 asks:

What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 20×20 grid?

I was going to solve this in Java but ended up just using my eyes (with a little help from Vim).

Problem 10 asks:

Find the sum of all the primes below two million.

Here’s my solution in Java:

public class Problem10 {
public static void main(String[] args) {
int max = 2_000_000;
boolean[] isComposite = new boolean[max + 1];
for (int i = 2; i * i <= max; i++) {
if (!isComposite[i]) {
for (int j = i; i * j <= max; j++) isComposite[i*j] = true;
}
}
long sum = 0;
for (int i = 2; i <= max; i++) if (!isComposite[i]) sum += i;
System.out.println(sum);
}
}

It uses the sieve of Eratosthenes algorithm. It could be optimized by using the sieve of Atkin, and/or using a bit vector instead of a boolean array, but as is it runs in a very fast time.

Problem 1 asks:

Find the sum of all the multiples of 3 or 5 below 1000.

Very simple, just go through every number between 0 and 1000, and if it’s a multiple of 3 or 5 add it to the running total.

Here’s my initial solution in Java:

public class Problem1 {
public static void main(String[] args) {
int sum = 0;
for (int i = 0; i < 1000; i++) {
if (i % 3 == 0 || i % 5 == 0) sum += i;
}
System.out.println(sum);
}
}

This is fine if you only want to find the multiples below 1000, but for big ranges we can do *far* better.

We can solve this problem in constant time by making use of the fact that: $$\sum_{i=1}^ni = \frac{n(n+1)}2$$

The sum of all multiples of 3 and 5 below n can be calculated as: $$3\sum_{i=1}^{\lfloor\tfrac{1}{3}n-1\rfloor}i + 5\sum_{i=1}^{\lfloor\tfrac{1}{5}n-1\rfloor}i - 15\sum_{i=1}^{\lfloor\tfrac{1}{15}n-1\rfloor}i$$

Multiples of 15 have to be subtracted to remove duplicates which were multiples of both 5 and 3. One needs to be subtracted from each range because the questions says *below* 1000.

Using the earlier formula, this expands to: $$\frac{3\lfloor\tfrac{1}{3}m\rfloor(\lfloor\tfrac{1}{3}m\rfloor+1) + 5\lfloor\tfrac{1}{5}m\rfloor(\lfloor\tfrac{1}{5}m\rfloor+1) - 15\lfloor\tfrac{1}{15}m\rfloor(\lfloor\tfrac{1}{15}m\rfloor+1)}2$$ where \(m = n -1\).

Translating into Java we get:

public class Problem1 {
public static void main(String[] args) {
final long RANGE = 1000;
long m = RANGE - 1;
long sum = (3 * (m / 3) * (m / 3 + 1) + 5 * (m / 5) * (m / 5 + 1) -
15 * (m / 15) * (m / 15 + 1)) / 2;
System.out.println(sum);
}
}

Xterm is bloated and archaic terminal emulator, but it ships with OpenBSD and gets the job done, so I'm happily using it.

Browsing through the 6206 line long manual I found an excellent snippet which I thought others might find useful.

Not everyone finds the three-button mouse bindings easy to use. In a wheel mouse, the middle button might be the wheel. As an alternative, you could add a binding shifted keys:

*VT100*translations: #override \n\
Shift Home: copy-selection(SELECT) \n\
Shift Insert: copy-selection(SELECT) \n\
Ctrl Shift C: copy-selection(SELECT) \n\
Ctrl Shift V: insert-selection(SELECT)

You would still use the left- and right-mouse buttons (typically 1 and 3) for beginning and extending selections.

Switching this up slightly to use the `CLIPBOARD`

buffer gives us:

xterm*VT100.Translations: #override \n\
Ctrl Shift C: copy-selection(CLIPBOARD) \n\
Ctrl Shift V: insert-selection(CLIPBOARD)

Add this to your `~/.Xdefaults`

and reload the configuration with `xrdb -merge ~/.Xdefaults`

.

Now you can copy and paste from xterm using Ctrl-Shift-C and Ctrl-Shift-V respectively!