Posts Tagged with "Factorial"

nchoosek

UVa 530: Binomial Showdown

Wednesday, June 6, 2012

2 Comments

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...
Project Euler 74: Determine the number of factorial chains that contain exactly sixty non-repeating terms.

Project Euler 74: Determine the number of factorial chains that contain exactly sixty non-repeating terms.

Saturday, December 10, 2011

0 Comments

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 descriptionHow 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.

Continue reading...
Project Euler 53: How many values of C(n,r), for 1 ≤ n ≤ 100, exceed one-million?

Project Euler 53: How many values of C(n,r), for 1 ≤ n ≤ 100, exceed one-million?

Saturday, July 23, 2011

14 Comments

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...

Project Euler 34: Find the sum of all numbers which are equal to the sum of the factorial of their digits

Saturday, April 2, 2011

11 Comments

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...