Author Archives: jnwood

Project Euler Problem 2: Even Fibonacci numbers

Project Euler Problem 2 instructs:

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, …

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

They’ve already given you the definition of the Fibonacci sequence (except it is usually written as starting with 0,1 or 1,1). So the first thing to figure out is how do we find the sequence of even-valued terms.

Luckily, there is a pretty easy pattern here. Let’s start by writing the Fibonacci sequence as a formula:

F_n=F_{n-1} + F_{n-2}

where F_1=F_2=1

So starting by substituting n=3 we get F_3=F_2+F_1. Since both F_1 and F_2 are odd valued, we’ll replace them with F_{odd}. So now we have:

F_3=F_{odd} + F_{odd}

Two odd numbers always add to an even number, so let’s replace F_3 with F_{even}. Resulting in:

F_{even}=F_{odd} + F_{odd}

So this is the start of our pattern. Now, let’s find the next equation in the pattern.

F_4=F_3 + F_2

Substitute F_3 and F_2:

F_4=F_{even} + F_{odd}

An even and and odd number will always add to an odd number. So we have:

F_{odd}=F_{even} + F_{odd}

Repeat for F_5 and we have:

F_{odd}=F_{odd} + F_{even}

Once more for F_6 results in:

F_{even}=F_{odd} + F_{odd}

Which is where we started with F_3. Since each Fibonacci number only depends on the previous 2 numbers, this sequence of even and odd numbers will repeat forever.

\begin{aligned}&F_1&=&1&=&odd&\\&F_2&=&1&=&odd&\\&F_3&=&2&=&even&\\&F_4&=&3&=&odd&\\&F_5&=&5&=&odd&\\&F_6&=&8&=&even&\\&F_7&=&13&=&odd&\\&F_8&=&21&=&odd&\\&F_9&=&34&=&even&\end{aligned}

Every third term is an even number starting with F_3.

Solution A: The Straightforward Approach

The most straight-forward way to implement this in C# would be to calculate each Fibonacci number and add up every third number until we reach our limit:

public static long SolveA()
{
	long n1 = 1;
	long n2 = 2;
	long total = 0;

	while (n2 <= 4000000)
	{
		total += n2;

		long n3 = n1 + n2;
		long n4 = n2 + n3;
		long n5 = n3 + n4;

		n1 = n4;
		n2 = n5;
	}

	return total;
}

Solution B: Skipping Odd Values

Now we’re going to discuss the first optimizaiton. Since we only need to add up every third Fibonacci number, we don’t actually need the other two in the sequence.

Once again, let’s start with our Fibonacci sequence formula:

F_n=F_{n-1} + F_{n-2}

Instead of being based on the previous two numbers, which we don’t care about, let’s see if we can rewrite it in terms of the numbers we do care about. That would be the other even numbers, which occur in every third place. So we’d like to express F_n in terms of F_{n-3} and F_{n-6}.

Let’s start by substituting F_{n-1}

F_n=F_{n-2}+F_{n-3} + F_{n-2}

Simplify:

F_n=2*F_{n-2}+F_{n-3}

F_{n-3} is useful, but we still need to break down F_{n-2}:

F_n=2*(F_{n-3}+F_{n-4})+F_{n-3}

Simplify:

F_n=3*F_{n-3}+2*F_{n-4}

This part gets a bit tricky. We’re going to substitute only one F_{n-4} and leave the other one to use later:

F_n=3*F_{n-3}+F_{n-4}+F_{n-5}+F_{n-6}

Now we substitute F_{n-3} back in place of F_{n-4}+F_{n-5} to get:

F_n=3*F_{n-3}+F_{n-3}+F_{n-6}

Simplify:

F_n=4*F_{n-3}+F_{n-6}

There you have it. We now have our Fibonacci sequence, except that it only spits out the even terms.

Here is the C# code:

public static long SolveB()
{
	long n1 = 2;
	long n2 = 8;
	long n3 = 34;
	long total = 10;

	while (n3 <= 4000000)
	{
		total += n3;
		n1 = n2;
		n2 = n3;
		n3 = (n2 << 2) + n1;
	}

	return total;
}

Note: the n2 << 2 is just a more efficient way to multiply by 4.

Solution C: No Running Total Needed

Ok, so there's actually a way to do this without even keeping a running total. We still have to calculate the Fibonacci sequence, but we don't have to explicitly add up the even terms. We'll do this with a trick similar to the one in Project Euler Problem 1.

What we're trying to solve is the total that we'll call S_n:

S_n=\displaystyle\sum_{k=1}^{n/3}F_{3*k}

Let's start by taking the end of Solution B:

F_n=4*F_{n-3}+F_{n-6}

This will be much easier to work with if we add 6 to the indices and get:

F_{n+6}=4*F_{n+3}+F_n

And then solve for F_n:

F_n=F_{n+6}-4*F_{n+3}

Now let's expand the values of F_n that we want to sum for our solution:

\begin{aligned}&F_n&=&F_{n+6}&-&4*&F_{n+3}\\&F_{n-3}&=&&&&F_{n+3}&-&4*&F_n&\\&F_{n-6}&=&&&&&&&F_{n}&-&4*&F_{n-3}&\\\dots\\&F_6&=&&&&&&&&&&&F_{12}&-&4*&F_9&\\&F_3&=&&&&&&&&&&&&&&F_9&-&4*&F_6&\\&F_0&=&&&&&&&&&&&&&&&&&F_6&-&4*&F_3&\end{aligned}

Note: I know that F_0 is equal to zero, but having it here it will make things easier later.

First, you can see that the left side of these equations add up to the total we are looking for. They're the list of all the even Fibonacci numbers. And we can also see a pattern on the right side. The terms in the middle partially cancel each other out leaving negative three of each term. So it ends up looking like this:

S_n=F_{n+6}-3*F_{n+3}-3*F_n-3*F_{n-3}-...-3*F_{12}-3*F_9-3*F_6-4*F_3

We can simplify this with a summation expression as:

S_n=F_{n+6}-3*F_{n+3}-3*\displaystyle\sum_{k=1}^{n/3}F_{3*k}-F_3

Substitute the summation for S_n:

S_n=F_{n+6}-3*F_{n+3}-3*S_n-F_3

And solve for S_n:

S_n=\dfrac{F_{n+6}-3*F_{n+3}-F_3}4

We now have the sum of our Fibonacci sequence in terms of the sequence itself.

In code form:

public static long SolveC()
{
	long n1 = 2;
	long n2 = 8;
	long n3 = 34;

	while (n3 <= 4000000)
	{
		n1 = n2;
		n2 = n3;
		n3 = (n2 << 2) + n1;
	}

	n1 = (n3 << 2) + n2;

	long total = (n1 - 3 * n3 - 2) >> 2;

	return total;
}

Solutions D & E: Logarithmic Time Algorithms

The solutions we've developed so far have all had a linear time complexity with respect to the maximum sequence value (4000000 in our case). However, it is possible to do better than that. I'm not going to go into a lot of detail, because this is probably beyond the skill level expected just for problem 2 on Project Euler.

Matrix Multiplication

It is actually possible to find the nth Fibonacci number with the following matrix formula:

\begin{bmatrix}1&1\\1&0\end{bmatrix}^n=\begin{bmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{bmatrix}

And there are tricks to do the matrix exponent in logarithmic time, which I won't get into yet. But that's not the whole problem. Our problem statement doesn't actually want us to get the nth Fibonacci number. It wants us to sum up to the number whose value does not exceed a limit. So you'd have to use this matrix exponentiation to do a binary search to find which value of n does not exceed the limit where n + 3 does. You could then use this in our Solution C.

Inspiration for this solution came from this link.

Binet's Formula

Another improvement on the previous solution can find the nth Fibonacci number in constant time. It's called Binet's formula. In fact, any constant-recursive sequence can be solved this way. However, the binary search from the matrix solution would still be needed to find the index in the Fibonacci sequence that doesn't exceed the limit.

Here is the formula:

f_n=\dfrac{\bigg(\dfrac{1+\sqrt5}2\bigg)^n-\bigg(\dfrac{1-\sqrt5}2\bigg)^n}{\sqrt5}

This could also be used in Solution C to find the desired sum.

GitHub

You can find the code on GitHub (complete with unit tests) at https://github.com/josiahwood/ProjectEuler/tree/master/Problem2.

Project Euler Problem 1: Multiples of 3 and 5

Project Euler Problem 1 instructs:

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.

This ends up being a basic math problem, so no code is needed yet.

I think the easiest way to think of this is as a variation on triangular numbers. Triangular numbers are the sums of the first n natural numbers. Which is a very similar description to our problem statement. The initial formula for triangular numbers is:

T_n=\displaystyle\sum_{k=1}^nk

Expanded, this looks like:

T_n=1+2+3+...+(n-2)+(n-1)+n

If we do a little trick here, then we can simplify this expression considerably. Take the above expansion, reverse it, and add it to the original expansion term by term.

\begin{aligned}&T_n&=&1&+&2&+&3&+&...&+&(n-2)&+&(n-1)&+&n\\+&T_n&=&n&+&(n-1)&+&(n-2)&+&...&+&3&+&2&+&1\\=&2T_n&=&(n+1)&+&(n+1)&+&(n+1)&+&...&+&(n+1)&+&(n+1)&+&(n+1)\end{aligned}

If we simplify the repeated terms we get:

2T_n=n(n+1)

And then solve for T_n:

T_n=\dfrac{n(n+1)}2

Great! Now we really have something that we can use in our solution. Since the problem asked for the sum of natural numbers below 1000 let us subtract 1 to get 999. Then divide that by i (which will represent the increment being summed, either 3 or 5 in this problem). Last, scale by i so that we are adding up multiples of the increment instead of just sequential natural numbers. So if L represents the upper limit provided (1000), then we get this equation:

S(L,i)=iT_{{\lfloor}\frac{L-1}i{\rfloor}}

Now substitute the final equation for T_n:

S(L,i)=\dfrac{i}2{\lfloor}\dfrac{L-1}i{\rfloor}({\lfloor}\dfrac{L-1}i{\rfloor}+1)

However, we need the sum of numbers that are either multiples of 3 or 5. So we have to add both of those results and then subtract the intersection that would otherwise be counted twice.

S(1000,3) + S(1000,5) - S(1000,15)

166833 + 99500 - 33165 = 233168

It would have arguably been simpler to just write a quick program that loops through all natural numbers less than 1000 and total any value that is a multiple of 3 or 5. However, thinking about this problem mathematically is good practice for what is up ahead. In future problems you will not have the luxury of using an algorithm that takes linear time instead of constant time.

However, if you’d really like to see this in code, then here is my C# example:

using System;

namespace Problem1
{
	public class Program
	{
		static void Main(string[] args)
		{
			int result = Solve(1000);
			Console.WriteLine(result);
		}

		public static int Solve(int limit)
		{
			return Sum(limit, 3) + Sum(limit, 5) - Sum(limit, 15);
		}

		static int Sum(int limit, int increment)
		{
			int n = (limit - 1) / increment;
			return increment * n * (n + 1) / 2;
		}
	}
}

You can find the code on GitHub (complete with a unit test) at https://github.com/josiahwood/ProjectEuler/tree/master/Problem1.

Twelve Men on an Island Logic Puzzle

One of my favorite shows right now is Brooklyn Nine-Nine. During season 2 episode 18, titled “Captain Peralta”, Captain Holt presents this riddle to the team:

There are twelve men on an island. Eleven weigh exactly the same amount, but one of them is slightly lighter or heavier. You must figure out which. The island has no scales, but there is a seesaw. You can only use it three times.

This isn’t exactly a programming post, but it does demonstrate the same kind of problem solving that is often found in devising efficient algorithms.

I decided to represent each islander with a letter from A to L. This makes it easy to unambiguously and concisely represent combinations of islanders. I show each trial with the seesaw as a column. The “Test” column shows what islanders are put on the seesaw as left vs. right. The “Result” column shows “=” if both sides were equal, “<” if the left side weighed less than the right, or “>” if the left side weighed more than the right. Then the “Possibilities” column shows what possible solutions remain given the result of the trial. As we move from the 1st trial towards the 3rd we can see the remaining possibilities reduce as more results eliminate solutions.

When solving this puzzle we know right away that we cannot rely on the seesaw always tilting to the left or right. This seems to be people’s initial attempt at solving this problem. Just put six on one side and six on the other and work your way down. However, 3 trials and only 2 possible results would only give us up to 8 solutions because 2 x 2 x 2 = 8. So we know that we have to rely some trials being balanced to find all the solutions. Therefore, it is probably not a good idea to put six vs. six because there is no way that seesaw could be balanced since the different islander would always be on the seesaw giving only two possible results which doesn’t tell us which side the different islander is on.

The first trial that gives the most information is to do four vs. four (ABCD vs. EFGH). No matter what the result we have reduced the possible solutions from 24 to 8.

Possibilities Test Result Possibilities
A lighter
A heavier
B lighter
B heavier
C lighter
C heavier
D lighter
D heavier
E lighter
E heavier
F lighter
F heavier
G lighter
G heavier
H lighter
H heavier
I lighter
I heavier
J lighter
J heavier
K lighter
K heavier
L lighter
L heavier
ABCD vs. EFGH = I lighter
I heavier
J lighter
J heavier
K lighter
K heavier
L lighter
L heavier
< A lighter
B lighter
C lighter
D lighter
E heavier
F heavier
G heavier
H heavier
> A heavier
B heavier
C heavier
D heavier
E lighter
F lighter
G lighter
H lighter
  • If the seesaw is equal then we know those eight islanders (ABCDEFGH) can be eliminated from being either lighter or heavier. The remaining four islanders (IJKL) could then be either lighter or heavier.
  • If the seesaw is unbalanced then we know the four untested islanders (IJKL) can be eliminated. We also know that all the islanders on the heavier side cannot be lighter. And all the islanders on the lighter side cannot be heavier.

What we do for the second trial depends on the type of result for the first trial because the pattern of remaining possibilities is different.

  • If the first trial was balanced then we have four remaining islanders (IJKL) that could be either lighter or heavier. We can work out the remaining possibilities by comparing three remaining islanders (IJK) with three normal islanders (ABC).

    Possibilities Test Result Possibilities
    I lighter
    I heavier
    J lighter
    J heavier
    K lighter
    K heavier
    L lighter
    L heavier
    IJK vs. ABC = L lighter
    L heavier
    < I lighter
    J lighter
    K lighter
    > I heavier
    J heavier
    K heavier
    • If the second trial was balanced, then you know that that last remaining islander (L) is the different islander. Compare him with any other islander. That will tell you if he is lighter or heavier than the other islanders. This third trial cannot be balanced since we know that this last islander (L) is different from all the other islanders.
    • If the second trial was unbalanced, then you now know if the different islander is either lighter or heavier. You also know that the last untested islander (L) is normal. You can weigh two of the remaining islanders against each other to determine which of the remaining three islanders is different. I will show the case where the three islanders (IJK) are lighter.

      Possibilities Test Result Possibilities
      I lighter
      J lighter
      K lighter
      I vs. J = K lighter
      < I lighter
      > J lighter
  • If the first trial was unbalanced, then this gets much less intuitive. For simplicity, we will only consider the result where the left side is lighter than the right side (ABCD < EFGH). The last case where the left side is heavier than the right side is just the inverse. The key to this trial is to find a test that will make the best use of the three possible seesaw results. Specifically, we don't want to use a test that only has two possible outcomes (like ABC vs. EFG). So I chose to take two potentially lighter islanders with one potentially heavier islander for each side (ABE vs. CDF). This has all three possible outcomes and leaves us with either two or three remaining possibilities.
    Possibilities Test Result Possibilities
    A lighter
    B lighter
    C lighter
    D lighter
    E heavier
    F heavier
    G heavier
    H heavier
    ABE vs. CDF = G heavier
    H heavier
    < A lighter
    B lighter
    F heavier
    > C lighter
    D lighter
    E heavier
    • If the second trial is balanced, then you only have two potentially heavier islanders left. Just weigh them against each other and whoever is heavier is the different islander. It is not possible for this last trial to be balanced since you know one of them is the heavier islander.
    • If the second trail is unbalanced, then weigh the remaining potentially lighter islanders against each other. If the third trial is balanced then the last potentially heavier islander is the different islander. If the third trial is unbalanced, then the islander on the lighter side is the different islander.

Here is the full solution:

1st Trial 2nd Trial 3rd Trial
Test Result Possibilities Test Result Possibilities Test Result Possibilities
ABCD vs. EFGH = I lighter
I heavier
J lighter
J heavier
K lighter
K heavier
L lighter
L heavier
IJK vs. ABC = L lighter
L heavier
L vs. A = Impossible
< L lighter
> L heavier
< I lighter
J lighter
K lighter
I vs. J = K lighter
< I lighter
> J lighter
> I heavier
J heavier
K heavier
I vs. J = K heavier
< J heavier
> I heavier
< A lighter
B lighter
C lighter
D lighter
E heavier
F heavier
G heavier
H heavier
ABE vs. CDF = G heavier
H heavier
G vs. H = Impossible
< H heavier
> G heavier
< A lighter
B lighter
F heavier
A vs. B = F heavier
< A lighter
> B lighter
> C lighter
D lighter
E heavier
C vs. D = E heavier
< C lighter
> D lighter
> A heavier
B heavier
C heavier
D heavier
E lighter
F lighter
G lighter
H lighter
ABE vs. CDF = G lighter
H lighter
G vs. H = Impossible
< G lighter
> H lighter
< C heavier
D heavier
E lighter
C vs. D = E lighter
< D heavier
> C heavier
> A heavier
B heavier
F lighter
A vs. B = F lighter
< B heavier
> A heavier

Ethereum Truffle and Testrpc with Cloud9

Here are the steps I’ve performed to get ConsenSys’s Ethereum Truffle working on Cloud9.  Note that I am new to a lot of the things being used here, so if you see something that I’m doing wrong or “the hard way” then let me know!  I hope this post helps someone else, but I also hope that I get some good feedback.

Installation Script

After creating your Cloud9 workspace run this script (we’ll break it down afterward):

#!/bin/bash

# pyethereum
cd ~
git clone https://github.com/ethereum/pyethereum/
cd pyethereum
sudo python setup.py install

# eth-testrpc
sudo pip install eth-testrpc

# nodejs v5.0.0
. ~/.nvm/nvm.sh
nvm use v5.0.0
nvm alias default 5.0.0

# truffle
sudo npm install -g truffle

You can find the latest version of this script in my Futarchy project at https://github.com/josiahwood/futarchy/blob/master/cloud9setup.sh.

Ethereum

# pyethereum
cd ~
git clone https://github.com/ethereum/pyethereum/
cd pyethereum
sudo python setup.py install

Lines 5-7 are just copy/pasted from the installation section of https://github.com/ethereum/pyethereum/. It works perfectly as advertised. This is required for testrpc to work in the next section.

Testrpc

# eth-testrpc
sudo pip install eth-testrpc

Line 10 is all you need to install testrpc according to https://github.com/ConsenSys/eth-testrpc. I’ve found Testrpc to be the quickest way to get up and going with writing contracts.

Update Nodejs

# nodejs v5.0.0
. ~/.nvm/nvm.sh
nvm use v5.0.0
nvm alias default 5.0.0

Since Truffle uses npm you’ll want to put Nodejs at your desired version first. I found version 5.0.0 worked very well with truffle. Lines 13-15 were the most consistent way I found to update Nodejs and make the new version the default. Line 15 is important to make sure all new Cloud9 terminals are using the correct version of Nodejs by default. This also affects what happens to Cloud9 terminals if you’ve been logged off for a while. Cloud9 advertises that your environment will be exactly the way you left it, but the terminals do reset after some timeout.

Truffle

# truffle
sudo npm install -g truffle

At this point line 18 works exactly as documented in the installation section of Truffle at https://github.com/ConsenSys/truffle.

Cloud9 Environment

Ok, this part took me a while to get working on Cloud9. I had no problems running on a local Ubuntu virtual machine, but I wasn’t so lucky on Cloud9. You can see how I worked out the problem on StackOverflow at Ethereum Test RPC working in Cloud9 with Truffle.  Credit for the final answer goes to XMLHttpRequest cannot load cloud 9 io.

In order to make it possible for testrpc to bind to the public IP address of your Cloud9 environment you’ll need to click on the “Share” button in the upper right-hand corner of the Cloud9 IDE and then make the Application link public. The StackOverflow answer indicated that this was due to a recent bug in Cloud9, so this may not be necessary in the future.

Truffle Project Environment/Configuration

Once you have some code/contracts you want to try out you’ll need to start testrpc first. Do this by executing testrpc -p 8081 -d 0.0.0.0 in a new Cloud9 terminal. The -p 8081 argument tells testrpc to run on port 8081. Cloud9 only opens a few ports for public access according to https://docs.c9.io/docs/multiple-ports so we can’t use the testrpc default of 8545. Port 8080 will be used later by the truffle serve command, so 8081 is the next open port. The -d 0.0.0.0 argument tells testrpc to bind to all available IP addresses, including the public one.

Now that you have testrpc up and running, you’ll need to configure your Truffle project properly. You can do this a few ways but the key is to get this part in your config file:

"rpc": {
    "host": "project-user.c9users.io",
    "port": 8081
}

Replace project-user.c9users.io with the Application URL you made public in the “Cloud9 Environment” section above.

You can either update this in your config/app.json file (to make it the default for all environments), one of the existing config/[environment]/config.json files, or make a new environment just for Cloud9.

After deploying your contracts with truffle deploy you can now run truffle serve and your HTML/JavaScript will be visible on port 8080 of your Application URL. Since this is conveniently the default port for Cloud9 it automatically gets redirected from port 80. This allows you to see your project directly at your Application URL like “http://project-user.c9users.io”.

Conclusion

Thanks for reading! Get coding!