Project Euler Problem #2 (R)

Here is a solution for Project Euler’s Problem #2 in R, which is stated as:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

Firstly ,we will define a function to calculate the Fibonacci numbers below N, where N in this case is 4*10^6:

fib < - function(n) { 
	x <- c(length=10)
	x[1] <- 1; x[2] <- 2
	for (i in 3:n) { 
		y <- x[i-1]+x[i-2]; 
		if (y > n){ break } 
		else { x[i] < - y }
	}
	x
}

Next, we just calculate the sum of the even-valued problems, in a similar manner to the way we solved problem #1:

f < - fib(4E6)
sum(f[f %% 2 ==0])

Memory Usage Statistics via Bash

I was just experimenting with a couple of useful commands (one is basically from the ps man page), and I want to record them here before I forget them.

Firstly,

ps -o pid,pmem,user --sort pmem --user [myuser]

Will show the currently running processes for [myuser], and for each process, the percentage of RSS (resident set size) of that process with respect to the total amount of physical memory on the machine. Very useful. If you want to see the entire process virtual size, add the vsize field to the field list above.

Secondly:

echo `cat /proc/meminfo | /bin/awk '/MemTotal/ {tot=$2} /MemFree/ {print $2/tot}'`

I’m sure there is a much nicer way to do this in awk, but I am an awk newbie. This returns the amount of free memory expressed as a percentage of total physical memory.

Awk doesn’t seem to have a round() function, so a version with more readable output would be:

echo `cat /proc/meminfo | /bin/awk '/MemTotal/ {tot=$2} /MemFree/ {print int($2/tot*10
0) "% memory free"}'`

Project Euler Problem #1 (R)

Here is a solution for Project Euler’s problem #1 in R. The problem is expressed as:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

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

As usual with Project Euler questions, there is an obvious way, and a less obvious, but much more efficient way. In this case, the obvious way is:

x < - seq(1,999)
sum(x[x %% 3 ==0 | x %% 5 == 0])

Which very concisely returns the correct answer, 233168. However, if we use the following intuition:

\[S_N = S_3 + S_5 - (S_{3,5})\]

i.e. the sum of all numbers divisible by 3 or 5 is the sum of all numbers divisible by 3, plus the sum of all numbers divisible by 5, minus the sum of all numbers divisible by 3 and 5 (as we have double counted them), then we get the correct answer.

Since \[S_n = \frac{n(a_1 + a_n)}{2}\], where \(n = \lfloor \frac{N}{n} \rfloor\), and \(a_n = a_1n\), the last piece of the puzzle is what to use for \(S_{3,5}\). This is straightforward, we just use the lowest common multiple of 3 and 5, which in this case is 15. Hence, the R representation of this is:

sum(333*((3+333*3)/2),199*((5+199*5)/2)-66*((15+66*15)/2))

MathTran

MathTran is a very popular (and useful) web service which performs a similar function to Google Charts – hit it with a valid TeX formula and it will return an image representation of the formula. Jonathan Fine has written a JavaScript wrapper which enables you to mark up img tags with alt values like “tex:[formula]” and these are automagically converted to images.

For example, the tag

<img alt="tex:\frac{1}{\sqrt{2\pi}\sigma}\int_{-\infty}^{x}{e^{-\frac{(x-\mu)^2}{2\sigma^2}}}dx">

will be converted to:

tex:\frac{1}{\sqrt{2\pi}\sigma}\int_{-\infty}^{x}{e^{-\frac{(x-\mu)^2}{2\sigma^2}}}dx

I have taken the MathTran source script and modified it slightly – MathTran allows you to specify a size parameter, between 1 and 9. This is not available via the default script, but I added the ability to have the img tag take a “size” parameter. This can be used like so:

<alt="tex:\sum_{0}^{\infty}x_i = \frac{1}{(1-x)}" size="2">

An example below:

tex:\sum_{i=0}^{\infty}x^i = \frac{1}{(1-x)}
tex:\sum_{i=0}^{\infty}x^i = \frac{1}{(1-x)}
tex:\sum_{i=0}^{\infty}x^i = \frac{1}{(1-x)}
tex:\sum_{i=0}^{\infty}x^i = \frac{1}{(1-x)}
tex:\sum_{i=0}^{\infty}x^i = \frac{1}{(1-x)}
tex:\sum_{i=0}^{\infty}x^i = \frac{1}{(1-x)}
tex:\sum_{i=0}^{\infty}x^i = \frac{1}{(1-x)}
tex:\sum_{i=0}^{\infty}x^i = \frac{1}{(1-x)}
tex:\sum_{i=0}^{\infty}x^i = \frac{1}{(1-x)}

UPDATE: I made a slight modification to add the raw TeX source to the title attribute of the img tag, so if you hover on a generated MathTran image, you should see the original formula.

UPDATE (2012) – this doesnt work anymore – now using the lovely MathJAX!

If you want to get the (modified) MathTran script, it is here: http://www.theresearchkitchen.com/blog/wp-includes/js/mathtran.js

Recursive Parameter Substitution Routine

I was recently looking at implementing a parameter substitution routine, along the lines of what Ant does for ${}-style properties. I initially picked up Spring’s PropertyPlaceholderConfigurer implementation, and created a modified version of the parseStringValue() routine, which is a recursive routine that unwraps delimited properties and resolves them. This did mostly what I want, but there were a few issues with it, mainly that it doesn’t handle truly recursive properties. For instance, if I want to do a Bash-style eval of a property ${FOO${BAR}}, where $BAR is mapped to "def", then I want the ultimate evaluation of this property to be ${FOOdef}.

This seems pretty simple to do in theory, as it would lend itself well to a recursive method, or an iterative method, possibly using a stack to store nested property names as we extract them from the string.

What I came up with was (if PREFIX is a property start delimiter, e.g. '{', and SUFFIX is a property end delimiter, e.g. '}'):

void recurse(StringBuilder str, int index) {
        if (str.indexOf(PREFIX, index) != -1)
            recurse(str, str.indexOf(PREFIX, index)+1);

            if (str.indexOf(PREFIX) == -1)
                return;

            String resolved = (str.substring(index, str.indexOf(SUFFIX, index)));
            str.replace(index-PREFIX.length(),
                    str.indexOf(SUFFIX, index)+SUFFIX.length(),
                    lookup(resolved));
    }

    private String lookup(String key) {
        System.out.println("looking up [" + key+  "] => [" + map.get(key) + "]");
        return map.get(key);
    }

Which does the job, although it could still be more elegant (not to mention efficient). The explicit check to str.indexOf(PREFIX) in order to exit the routine bugs me a little bit – I’m sure its possible to rearrange this to be more concise and skip the explicit check like that. Still this routine can now parse strings like TEXT{FOO}MORETEXT{BAR{GOO}} and resolve nested properties. I’m trrying to find a nicer recursive representation for this. maybe I should ask on #haskell.