Problem 530 at the UVa Online Judge, also known as Binomial Showdown, asks us to compute the number of ways one can choose k elements out of n elements, not taking order into account. The problem is a classical one (n choose k, anyone?), but with a twist. The input numbers are big, and we need to be really careful not to overflow integers in our intermediate computations. We discover a formula that has smaller intermediate values than the direct formula, and with one more small observation, we're done.

Continue reading...Saturday, December 10, 2011

And now for something completely different. Problem 74 of Project Euler has as far as I know nothing to do with proper fractions nor Farey sequences. So let's have a look at the problem description**How many chains, with a starting number below one million, contain exactly sixty non-repeating terms?**I have made 3 different solutions for this problem. All the solutions I have found here use some sort of brute force. With those words of wisdom, I believe we are ready to look at the first solution. The first one stores the current solution in a list and is just pure brute force. The second solution implies a caching strategy to avoid calculating things twice. The third uses almost no memory as the stopping criteria are changed such that we can avoid using a list to store the current sequence in. I think we are ready to look at the first solution now.

Saturday, July 23, 2011

I have found Problem 53 of Project Euler to be a really interesting problem to work with, because there is a brute force solution and then there is a much more elegant solution if you dive into the mathematics behind the question. The problem readsHow many, not necessarily distinct, values of nCr, for 1 ≤ n ≤ 100, are greater than one-million?I will present 2 different solution strategies each with 2 different solutions, so lets jump right into it.

Continue reading...Saturday, April 2, 2011

The headline of Problem 34 of Project Euler triggered something familiar in me. I didn't quite know what it was untill a few minutes later where it dawned on me that it was very similar to Problem 30. The problem reads Find the sum of all numbers which are equal to the sum of the factorial of their digits. I could copy paste the text from the solution to problem 30, but let me change the focus a bit.

Continue reading...
Wednesday, June 6, 2012

3 Comments