ISourceCode

Make the frequent cases fast and the rare case correct

Monthly Archives: February 2011

Fibonacci Numbers – [Recursion , Iterative using Dynamic Programming , Matrix Property]

In mathematics, the Fibonacci numbers are the numbers in the following integer sequence:

the sequence Fn of Fibonacci numbers is defined by the recurrence relation

with seed values

Closed form solution:
Binet’s formula, even though it was already known by Abraham de Moivre

where

is golden ratio

Matrix form:

A 2-dimensional system of linear difference equations that describes the Fibonacci sequence is

direct formula for the nth element in the fibonacci series:

Python using Matrix property:

>>> import numpy
>>> fib = numpy.matrix([[1,1],[1,0]])
>>> result = fib*fib
>>> result
matrix([[2, 1],
        [1, 1]])
>>> result = fib*fib*fib
>>> result
matrix([[3, 2],
        [2, 1]])
>>> result = fib*fib*fib*fib*fib
>>> result
matrix([[8, 5],
        [5, 3]])

In this Post you can find implementation for finding nth fibonacci number using

1 . Recursion – exponential
2 . Iterative method using Dynamic Programming – O(n)
3 . Matrix Property – O(log n)

For the Run time of the three algorithms please refer to this article from cs.wisc here

Implementation:

import time
def fib_matrix(n):
	i = h = 1
	j = k = 0
	while (n > 0) :
		if (n%2 == 1) : # when n is odd
			t = j*h
			j = i*h + j*k + t
			i = i*k + t
		t = h*h
		h = 2*k*h + t
		k = k*k + t
		n = int(n/2)
	return j
start1 = time.strftime('%s')
value1 = fib_matrix(500000)
#print value1
end1 = time.strftime('%s')
time1 = int(end1) - int(start1)
print "Time to execute the algorithm using matrix property=", time1 ,"Second(s)"

def fib_dp(n):
	a = b = 1
	for i in range(2,n) :
		c = a+b
		a = b
		b = c
	return c
start2 = time.strftime('%s')
value2 = fib_dp(500000)
#print value2
end2 = time.strftime('%s')
time2 = int(end2) - int(start2)
print "Time to execute the algorithm using dynamic programming =", time2 ,"Second(s)"

def fib_rec(n) :
	if (n==1 or n==2) :
		return 1
	return fib_rec(n-1) + fib_rec(n-2)
start3 = time.strftime('%s')
value3 = fib_rec(35)
#print value3
end3 = time.strftime('%s')
time3 = int(end3) - int(start3)
print "Time to execute the algorithm using recursion without dynamic programming =", time3 ,"Second(s)"

OUTPUT:

labuser@ubuntu:~$ python fib.py
Time to execute the algorithm using matrix property= 2 Second(s)
Time to execute the algorithm using dynamic programming = 38 Second(s)
Time to execute the algorithm using recursion without dynamic programming = 19 Second(s)

Note : I had to use input 35 for recursion to capture a run time as its a exponential time algorithm

The matrix method is more efficient than the simple iterative algorithm for larger numbers. For smaller numbers, the simplicity of the iterative algorithm is preferable.

Thanks to Wikipedia for the Theory !

Dyck Words – Project Euler problem 15 (Variant) – use of Catalan Numbers

Cn is the number of Dyck words of length 2n. A Dyck word is a string consisting of n X’s and n Y’s such that no initial segment of the string has more Y’s than X’s (Dyck language). For example, the following are the Dyck words of length 6: – Wikipedia

XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY.

Re-interpreting the symbol X as an open parenthesis and Y as a close parenthesis, Cn counts the number of expressions containing n pairs of parentheses which are correctly matched:

((())) ()(()) ()()() (())() (()()) – check this article for some code.

Problem 15 – Project Euler

Starting in the top left corner of a 2×2 grid, there are 6 routes (without backtracking) to the bottom right corner.

If we modify this question to find paths which do not pass above the diagonal or paths which do not pass below the diagonal.

Then solution is a Catalan Number

Cn is the number of monotonic paths along the edges of a grid with n × n square cells, which do not pass above the diagonal. A monotonic path is one which starts in the lower left corner, finishes in the upper right corner, and consists entirely of edges pointing rightwards or upwards. Counting such paths is equivalent to counting Dyck words: X stands for “move right” and Y stands for “move up”. The following diagrams show the case n = 4: – Wikipedia

Catalan Numbers – Combinatorial Problem – Print all valid properly opened and closed combination of n-pairs of parentheses

In combinatorial mathematics, the Catalan numbers form a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects. They are named after the Belgian mathematician Eugène Charles Catalan (1814–1894). – Wikipedia

The nth Catalan number is given directly in terms of binomial coefficients by

The first Catalan numbers (sequence A000108 in OEIS) for n = 0, 1, 2, 3, … are

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, …

How many ways are there to build a balanced formula from n sets of left and right parentheses? For example, there are five ways to do it for n = 3: ((())), ()(()), (())(), (()()), and ()()(). The leftmost parenthesis l matches some right parenthesis r, which must partition the formula into two balanced pieces, the part between l and r, and the part to the right of r. If the left part contains k pairs, the right part must contain n − k − 1 pairs, since l,r represent one pair.

Both of these sub formulas must be well formed, which leads to the recurrence given above – Programming challenges

Implementation:

import java.util.Scanner;

public class Parentheses{

        static void ParCheck(int left,int right,String str)
        {
                if (left == 0 && right == 0)
                {
                        System.out.println(str);
                }

                if (left > 0)
                {
                        ParCheck(left-1, right+1 , str + "(");
                }
                if (right > 0)
                {
                        ParCheck(left, right-1, str + ")");
                }

        }
        public static void main(String[] args)
        {
                Scanner input=new Scanner(System.in);
                System.out.println("Enter the  number");
                int num=input.nextInt();

                String str="";
                ParCheck(num,0,str);
        }
} 

OUTPUT:

labuser@ubuntu:~$ java Parentheses
Enter the number
3
((()))
(()())
(())()
()(())
()()()
labuser@ubuntu:~$ java Parentheses
Enter the number
4
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()

Collatz Conjecture – Problem 14 – Project Euler – ACM’s 3n+1 problem

The Collatz conjecture is an unsolved conjecture in mathematics named after Lothar Collatz, who first proposed it in 1937. The conjecture is also known as the 3n + 1 conjecture, the Ulam conjecture (after Stanisław Ulam), Kakutani’s problem (after Shizuo Kakutani), the Thwaites conjecture (after Sir Bryan Thwaites), Hasse’s algorithm (after Helmut Hasse), or the Syracuse problem the sequence of numbers involved is referred to as the hailstone sequence or hailstone numbers or as wondrous numbers

Take any natural number n. If n is even, divide it by 2 to get n / 2, if n is odd multiply it by 3 and add 1 to obtain 3n + 1. Repeat the process (which has been called “Half Or Triple Plus One”, or HOTPO) indefinitely. The conjecture is that no matter what number you start with, you will always eventually reach 1. The property has also been called oneness

Paul Erdős said about the Collatz conjecture: “Mathematics is not yet ready for such problems.” He offered $500 for its solution. – Grateful to Wikipedia for this wonderful introduction.

Consider the following operation on an arbitrary positive integer:

* If the number is even, divide it by two.
* If the number is odd, triple it and add one.
In modular arithmetic notation, define the function f as follows:

Now, form a sequence by performing this operation repeatedly, beginning with any positive integer, and taking the result at each step as the input at the next.

The Collatz conjecture is: This process will eventually reach the number 1, regardless of which positive integer is chosen initially.

For instance, starting with n = 6, one gets the sequence 6, 3, 10, 5, 16, 8, 4, 2, 1.
n = 11, for example, takes longer to reach 1: 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.

The sequence for n = 27, listed and graphed below, takes 111 steps, climbing to 9232 before descending to 1.

Pseudo code:

    function collatz(n)

        while n > 1

            show n
            if n is odd then

                set n = 3n + 1

            else

                set n = n / 2

            endif

        endwhile

    show n 

Cool Application or Visual Property

Iterating a optimized collatz map in the complex plane produces the Collatz fractal.

Collatz iterations on the Ulam Spiral can be seen in this video

An online collatz chain length calculator can be found here

Programming:

ACM question. : 3n+1 problem [you can find Java and C++ implementation in the link]

Consider the following algorithm to generate a sequence of numbers. Start with an
integer n. If n is even, divide by 2. If n is odd, multiply by 3 and add 1. Repeat this
process with the new value of n, terminating when n = 1. For example, the following
sequence of numbers will be generated for n = 22:
22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
It is conjectured (but not yet proven) that this algorithm will terminate at n = 1 for
every integer n. Still, the conjecture holds for all integers up to at least 1, 000, 000.
For an input n, the cycle-length of n is the number of numbers generated up to and
including the 1. In the example above, the cycle length of 22 is 16. Given any two
numbers i and j, you are to determine the maximum cycle length over all numbers
between i and j, including both endpoints.
Input
The input will consist of a series of pairs of integers i and j, one pair of integers per
line. All integers will be less than 1,000,000 and greater than 0.
Output
For each pair of input integers i and j, output i, j in the same order in which they
appeared in the input and then the maximum cycle length for integers between and
including i and j. These three numbers should be separated by one space, with all three
numbers on one line and with one line of output for each line of input.
Sample Input
1 10
100 200
201 210
900 1000

Sample Output
1 10 20
100 200 125
201 210 89
900 1000 174

Problem 14 – Project Euler

The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even)
n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

import time

ulam = { 1: 1 }
def collatz(n):
    if not n in ulam:
        ulam[n] = collatz(3*n+1 if n%2 else n/2) + 1
    return ulam[n]

max = (0,0)
limit = raw_input("Enter the Max limit: ")
limit = int(limit)
index = raw_input("Enter the starting Number: ")
index = int(index)
#limit = 200
start = time.strftime('%s')
if index % 2 == 0:
        for i in range(index+3,limit,2):
                length = collatz(i)
                if length > max[1]: max = (i,length)
if index % 2 != 0:
        for i in range(index,limit,2):
                length = collatz(i)
                if length > max[1]: max = (i,length)

end = time.strftime('%s')
time = int(end) - int(start)
print "(Number, Chain Length) =", max
print "Time to execute the algorithm =", time ,"Second(s)"

OUTPUT:

labuser@ubuntu:~$ python collatz.py
Enter the Max limit: 1000000
Enter the starting Number: 0
(Number, Chain Length) = (837799, 525)
Time to execute the algorithm = 10 Second(s)

labuser@ubuntu:~$
labuser@ubuntu:~$ python collatz.py
Enter the Max limit: 10
Enter the starting Number: 1
(Number, Chain Length) = (9, 20)
Time to execute the algorithm = 0 Second(s)

labuser@ubuntu:~$
labuser@ubuntu:~$ python collatz.py
Enter the Max limit: 200
Enter the starting Number: 100
(Number, Chain Length) = (171, 125)
Time to execute the algorithm = 0 Second(s)

labuser@ubuntu:~$ python collatz.py
Enter the Max limit: 210
Enter the starting Number: 201
(Number, Chain Length) = (207, 89)
Time to execute the algorithm = 0 Second(s)

labuser@ubuntu:~$
labuser@ubuntu:~$ python collatz.py
Enter the Max limit: 1000
Enter the starting Number: 900
(Number, Chain Length) = (937, 174)
Time to execute the algorithm = 0 Second(s)

Problem 76 – Project Euler – How many different ways can one hundred be written as a sum of at least two positive integers?

How many different ways can one hundred be written as a sum of at least two positive integers? – Project Euler

It is possible to write five as a sum in exactly six different ways:

4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

How many different ways can one hundred be written as a sum of at least two positive integers?

I am guilty of writing this article as i have already written an article addressing this problem. But i made this seperate as these are problem listed on project Euler

Please Read my article on Integer Partition and Ferrers diagram

It should be noted that in Ferrers diagram the number itself is considered as one partition. But this specific problem asks for atleast 2 partitions.

Follow

Get every new post delivered to your Inbox.