Project Euler / 16

Problem 16 asks:

What is the sum of the digits of the number 21000?

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);
    }
}

Last updated on .


Project Euler / 15

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

Last updated on .


Project Euler / 14

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.

Last updated on .


Project Euler / 13

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 102 of them.

Last updated on .


Project Euler / 12

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);
    }
}

Last updated on .


Project Euler / 11

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

Searching [98]\d in Vim with 'hlsearch' set on.

Last updated on .


Project Euler / 10

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.

Last updated on .


Project Euler / 1

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);
    }
}

Last updated on .


OpenBSD / Copy And Paste In Xterm

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!

Last updated on .


Misc / 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 .