I’m migrating my servers from Ubuntu 10.04 LTS (Lucid Lynx) to Ubuntu 12.04 LTS (Precise Pangolin), and both servers have multiple users and a complex network of user groups that I’d like to maintain. This is a bit more complicated than simply copying files, as many system processes have their own user IDs/groups and I don’t to mess with how the system defines those processes in the new install.

### Source Machine: Make a Backup Directory

We just need somewhere to save our information before we do the transfer. I’ll be performing all of these operations as root. (Super user access is required to read the files we need.)

### Source Machine: Saving Group Info

The group info is saved in /etc/group, and using the same idea as above we issue the command:

### Save The Data

Use a command such as scp to transfer the data to another machine, or save somewhere reliable. Once the new machine is set up, create a directory at /user_backup/ (or somewhere reasonable) and transfer the files created above to that directory.

### Transferring Users

Change directory to where the files are and become the root user. Then, issue the command:

### Transferring Users’ Data

$cp home.backup.tar.gz /home$ cd /home
$gunzip home.backup.tar.gz$ tar -xvf home.backup.tar

That _should_ do it.

Problem: The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143?

Solutions: I’ll give a Sage, Python, Cython and C solution.

### Sage Solution

There is a single-line solution in Sage.

sage: max(ZZ(600851475143).prime_factors())
6857

Let’s time this with 100,000 iterations in Sage.

import time

start = time.time()
for i in range(100000):
a = max(ZZ(600851475143).prime_factors())
elapsed = (time.time() - start)

print "result %s returned after %s seconds (100,000 iterations)." % (a, elapsed)

We get the following result.

result 6857 returned after 4.41913223267 seconds (100,000 iterations).

So, the calculation in Sage averages somewhere around 4.42e-05 seconds. That’s relatively quick. Let’s now write our own Python code.

### Python Solution

We’ll start factoring an input number by removing multiples of 2. Then, we’ll look at odd integers in increasing value until the number is completely factored. This is far from the most efficient factorization algorithm, but it will work. And, since we’re only interested in the largest factor, we don’t need to store much in memory.

import time

def largest_prime_factor(n):

largest_factor = 1

# remove any factors of 2 first
while n % 2 == 0:
largest_factor = 2
n = n/2

# now look at odd factors
p = 3
while n != 1:
while n % p == 0:
largest_factor = p
n = n/p
p += 2

return largest_factor

start = time.time()
for i in range(100000): a = largest_prime_factor(600851475143)
elapsed = (time.time() - start)

print "result %s returned after %s seconds (100,000 iterations)." % (a, elapsed)

We get the following result.

result 6857 returned after 93.1715428829 seconds (100,000 iterations).

This means that each iteration takes roughly 0.0009317 seconds, or about 21 times the time of the Sage code above. This makes sense here as the Sage code is using a much more efficient factorization algorithm. What happens when we code our Python into Cython?

### Cython Solution

We’ll modify our Python code to Cython and see how fast it runs.

%cython

import time

cdef largest_prime_factor(unsigned long n):

cdef unsigned long    largest_factor = 1
cdef unsigned long    p = 3

# remove any factors of 2 first
while n % 2 == 0:
largest_factor = 2
n = n/2

# now look at odd factors
while n != 1:
while n % p == 0:
largest_factor = p
n = n/p
p += 2

return largest_factor

start = time.time()
for i in range(100000): a = largest_prime_factor(600851475143)
elapsed = (time.time() - start)

print "result %s returned after %s seconds (100,000 iterations)." % (a, elapsed)

This returns the following result when executed.

result 6857 returned after 5.63884592056 seconds (100,000 iterations).

The Cython code is roughly 16.523 times faster than the Python code. The Cython code still takes roughly 27% longer than the Sage code, which is fine since Sage is using the PARI C library for factorizations, and our code was relatively cheap. For how much effort was put in to writing the Cython code, it performs very well. We can make this faster by writing the same code in C.

### C Solution

The C code here has the same basic structure as the Python and Cython code.

#include <stdio.h>
#include <stdlib.h>

unsigned long largest_prime_factor(unsigned long n) {
unsigned long   largest_factor = 1;
unsigned long   p = 3;
unsigned long   div = n;

/* remove any factors of 2 first */
while (div % 2 == 0) {
largest_factor = 2;
div = div/2;
}

/* now look at odd factors */
while (div != 1) {
while (div % p == 0) {
largest_factor = p;
div = div/p;
}
p = p + 2;
}

return largest_factor;
}

int main(int argc, char **argv) {
unsigned long   factor;
unsigned long   max = 100000;
unsigned long   i = 1;

while (i <= max) {
factor = largest_prime_factor(600851475143);
i++;
}
printf("%ld\n", factor);

return 0;
}

We compile (with GCC) and then run the executable (which includes 100000 iterations of the required function) to find that it takes 2.576 seconds, which is about 58% the runtime of the original Sage code.

Problem: 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, and 89. By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Solution: Notice that every third term is even. We can use this to our advantage. I’ll give three solutions: Sage, Python, and Cython.

### Sage Solution

This can be done with a single line in Sage.

sage: sum([i for i in fibonacci_xrange(4000000) if is_even(i)])
4613732

But, how fast is it? Let’s try it one million times and time it in Sage.

import time

start = time.time()
for j in range(1000000):
a = sum([i for i in fibonacci_xrange(4000000) if is_even(i)])
elapsed = (time.time() - start)

print "result %s returned after %s seconds (1 million iterations)." % (a, elapsed)

When we execute this, we wait and wait and wait. While I’m waiting for the result, I’ll explain what is taking so long. The function fibonacci_xrange() in Sage is not computing the Fibonacci numbers recursively, but calculating each one from scratch. That’s bad… really bad. I think I’ll go make some coffee while I wait for this to finish, and perhaps submit a bug patch. It finally finishes, roughly 15 minutes later.

result 4613732 returned after 887.411308289 seconds (1 million iterations).

### Python Solution

Instead of using the PARI C library to compute the Fibonacci sequence non-recursively, we now construct the sequence explicitly in Python, and we can use the fact that every third number will be even to construct our sum. First, I’ll use a bit of slightly more elegant code.

import time

def fib_sum(n):
fib = [1,2]
n1,n2 = 1,2
while n1+n2 &lt; n:
fib.append(n1+n2)
n1,n2 = n2,n1+n2
return sum(fib[1::3])

start = time.time()
for i in range(1000000): fibsum = fib_sum(4000000)
elapsed = (time.time() - start)

print "result %s returned after %s seconds (1 million iterations)." % (fibsum, elapsed)

This runs much more quickly than the Sage code.

result 4613732 returned after 16.3734951019 seconds (1 million iterations).

But, we can do better by avoiding the Python list slicing.

import time

def fibonacci_even_sum(n):
if n == 0: return 0
if n == 1: return 0
if n == 2: return 2

# n is greater than 2 (no error checking done)

# set the initial sum to zero
sum = 2

# set the initial fibonacci values
fib0 = 0
fib1 = 1
fib2 = 2

# set an iterator variable to only sum every third entry
iter = 0

while( fib2 <= n ):
if( iter == 3 ):
sum = sum + fib2

# print fib2
iter = 0
fib0 = fib1
fib1 = fib2
fib2 = fib0 + fib1
iter = iter + 1

return sum

start = time.time()
for i in range(1000000): fibsum = fibonacci_even_sum(4000000)
elapsed = (time.time() - start)

print "result %s returned after %s seconds (1 million iterations)." % (fibsum, elapsed)

And when we run this, we get the following output.

result 4613732 returned after 11.8605749607 seconds (1 million iterations).

This is roughly 74.82 times faster than the Sage implementation.

### Cython Solution

We modify our Python code slightly to produce Cython.

%cython

import time

cdef fibonacci_even_sum(unsigned long long int n):
cdef unsigned long long int sum = 2
cdef unsigned int iter = 0
cdef unsigned long long int fib0 = 0
cdef unsigned long long int fib1 = 1
cdef unsigned long long int fib2 = 2
if n == 0: return 0
if n == 1: return 0
if n == 2: return 2

while( fib2 <= n ):
if( iter == 3 ):
sum = sum + fib2

# print fib2
iter = 0
fib0 = fib1
fib1 = fib2
fib2 = fib0 + fib1
iter = iter + 1

return sum

start = time.time()
for i in range(1000000): fibsum = fibonacci_even_sum(4000000)
elapsed = (time.time() - start)
print "result %s returned after %s seconds (1 million iterations)." % (fibsum, elapsed)

When executed, we get the following.

result 4613732 returned after 0.363753080368 seconds (1 million iterations).

This is roughly 32.61 times faster than our fastest Python code, and about 2439.60 times faster than our Sage code.

This post solves Project Euler problem 1 in Python and Clojure.

### Problem:

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.

### Python Solution

As a first Python solution, we simple sum over a list constructed out of integers having the desired property: they are either divisible by 3 or 5.

#!/usr/bin/python

import time

start = time.time()

s = sum([i for i in range(1000) if (i % 3 == 0 or i % 5 == 0)])

elapsed = time.time() - start

print "result %s returned in %s seconds" % (s,elapsed)

This finds the result relatively quickly.

result 233168 returned in 0.000147819519043 seconds

There are some downsides to that solution though. Namely, every integer between 0 and 999 is being checked to see if it is divisible by 3 or 5. We can improve on this by explicitly constructing a few lists. First, we’ll look at all multiples of 3 in the given range. Then, we’ll consider all multiples of 5 which are not multiples of 3. (If we considered all multiples of 5, we’d be counting twice those numbers which happen to be divisible by 5 and divisible by 3 – as they’ve already been counted.)

#!/usr/bin/python

import time

start = time.time()

s = 0

# add in all multiples of 3
for i in range(3,1000,3): s += i

# Add in multiples of 5 that are no also multiples of 3.
# This includes numbers of the form 5+15n and 10+15n between 0 and 1000.
for i in range(5,1000,15): s += i
for i in range(10,1000,15): s += i

elapsed = time.time() - start

print "result %s returned in %s seconds" % (s,elapsed)

This does indeed speed up the process a bit, as shown here:

result 233168 returned in 4.79221343994e-05 seconds

In fact, that’s roughly 3 times as fast as the original. There are some other tricks that we can throw at this. One option is to use Python sets instead of lists.

#!/usr/bin/python

import time

start = time.time()

s1 = set(range(0,1000,3))
s2 = set(range(0,1000,5))
ss = s1.union(s2)
s = sum(ss)

elapsed = time.time() - start

print "result %s returned in %s seconds" % (s,elapsed)

In this example, we’re using the union of two sets (those integers divisble by 3 and those divisible by 5) to get around the problem of integers that are divisible by both 3 and 5 being counted twice. Let’s see how fast that runs.

result 233168 returned in 3.31401824951e-05 seconds

That’s slightly faster than our best list method yet.

There’s a much better way to tackle this problem though. Another approach is to realize that the sum of all numbers between 1 and 1000 being divisible by 3 is

$\sum_{j=1}^{333}3j = 3\sum_{j=1}^{333}j=3\times\frac{333(333+1)}{2}=3\times 55611=166833$

and the sum of all numbers in the same range divisible by 5 is
$\sum_{j=1}^{199}5j=5\sum_{j=1}^{199}j=5\times\frac{199(199+1)}{2}=5\times 19900=99500.$

The integers that would be counted twice by doing the above sums are numbers that are both multiples of 3 and 5. If we take the two sums and then subtract every number that is both a multiple of 3 and 5, we will obtain the result.

$15+30+45+\cdots+990=(3\cdot 5)\times(1+2+\cdots+66)$

In closed form, that’s

$15\sum_{j=1}^{66}j=15\times\frac{66(66+1)}{2}=15\times 2211=33165.$

Encoded in Python, we have the following, which should find our result nice and quickly.

#!/usr/bin/python

import time

# The sum of all numbers from 1 to n is (n*(n+1))/2. Using this formula, we can
# find the answer in the following way.

# Notice that all of the multiples of 3 look like this:
#   3 + 6 + 9 + ... + 996 + 999 = 3 * (1 + 2 + ... + 333) = 3 * (333*334)/2

# Similarly, the sum of all multiples of 5 looks like this:
#   5 + 10 + 15 + ... + 995 = 5 * (1 + 2 + ... + 199) = 5 * (199*200)/2

# If we were to add these two integers together, we would be counting multiples
# of 15 twice (once as multiples of 3 and once as multiples of 5). So, we take
# the two numbers above and subtract an instance of all multiples of 15:
#   15 + 30 + ... + 990 = 15 * (1 + 2 + ... + 66) = 15 * (66*67)/2

start = time.time()

s = ((3*333*334)/2) + ((5*199*200)/2) - ((15*66*67)/2)

elapsed = time.time() - start

print "result %s found in %s seconds" % (s, elapsed)

We execute this and find the result about 35 times as fast as our fastest method yet.

result 233168 found in 9.53674316406e-07 seconds

### Clojure Solution

The idea is to create a sequence of numbers from 1 to 1000, use a map with a function that filters out the numbers that aren’t divisible by 3 or 5, and use a reduce with a sum on the remaining sequence.

(ns project-euler-001.core
(:gen-class))

(defn f
"Takes an input x. If 3 or 5 divides x, returns x. Otherwise, returns 0."
[x]
(if (or (= (mod x 3) 0) (= (mod x 5) 0)) x 0))

(defn -main
"Project Euler Problem 1 - Clojure Solution"
[& args]
(println (time (reduce + (map f (range 1 1000))))))