Archive for the ‘Uncategorised’ Category

Yet Another one on Fibonacci serie - Knuth multiplication

Java Fibonacci serie - Knuth multiplication

Leonardo Fibonacci,the Italian mathematician (from Pisa, 1170, one of the most important mathematician of all time) invented the famous serie defined recursively as follows:


We all know that as programmers once in life (at least) we will write some piece of code to compute the element of the serie. Recursive implementation is straightforward but inefficient, due to the exponential number of recursive calls, that make "hard" to compute numbers bigger that 40. It is very easy to come up with some iterative or memoised implementation, that lowers the complexity to and allows to efficently compute "any" number of the serie.
In this post we will derive an implementation (JAVA) that have complexity 1)using results from Knuth, Fibonacci multiplication,1988. Read On…

References   [ + ]

1. using results from Knuth, Fibonacci multiplication,1988

Project Euler - Problem 24

In this article we want to briefly discuss a possible solution to the project euler problem 24 which asks:

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

012 021 102 120 201 210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

One possible approach could obviously be to brute force all the lexicographical permutations and then take the millionth element out of the previously sorted collection of permutation (interpreted as number). The drawback of this solution is that unfortunately the number of permutations is more than exponential, is .

We want to show here a more mathematical/combinatorial approach. First of all start considering that how the permutations looks like.
First permutations are (thanks to Stefano Germano for typo correction) .
A deeper look at the permutations reveals that are all the sequences starting with 0 and concatenated with a permutation of the ramaining 9 elements . How many of them? .
It means that the permutation we are looking for  has to be greater than the th permutation: .
From this we can deduce that we can also skip all the sequences starting by 1 because they produces (again) permutations and

. Moreover our millioth permutation is in the sequences starting with 2 because (hence is not in the permutations starting with 3). Read On…