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!

The backend of Shobute 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.