Factorial

UVa 530: Binomial Showdown

UVa 530: Binomial Showdown

Problem 530 at the UVa Online Judge, also known as Binomial Showdown, asks us to compute the number of ways one can choose elements out of elements, not taking order into account. The problem is a classical one ( choose , 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 →

Posted by Bjarki Ágúst in UVa Online Judge, 3 comments
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.

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

The number 145 is well known for the property that the sum of the factorial of its digits is equal to 145:

1! + 4! + 5! = 1 + 24 + 120 = 145

Perhaps less well known is 169, in that it produces the longest chain of numbers that link back to 169; it turns out that there are only three such loops that exist:

169 → 363601 → 1454 → 169
871 → 45361 → 871
872 → 45362 → 872

It is not difficult to prove that EVERY starting number will eventually get stuck in a loop. For example,

69 → 363600 → 1454 → 169 → 363601 (→ 1454)
78 → 45360 → 871 → 45361 (→ 871)
540 → 145 (→ 145)

Starting with 69 produces a chain of five non-repeating terms, but the longest non-repeating chain with a starting number below one million is sixty terms.

How many chains, with a starting number below one million, contain exactly sixty non-repeating terms?

Continue reading →

Posted by Kristian in Project Euler, 3 comments
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?

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 reads

There are exactly ten ways of selecting three from five, 12345:

123, 124, 125, 134, 135, 145, 234, 235, 245, and 345

In combinatorics, we use the notation, 5C3 = 10.

In general,

where , and

It is not until n = 23, that a value exceeds one-million: 23C10 = 1144066.

How 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 →

Posted by Kristian in Project Euler, 17 comments

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

The headline of Problem 34 of Project Euler triggered something in me and I found it oddly familiar. I didn’t quite know what it was until a few minutes later where it dawned on me that it was very similar to Problem 30. The problem description is short and reads:

145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.

Find the sum of all numbers which are equal to the sum of the factorial of their digits.

Note: as 1! = 1 and 2! = 2 are not sums they are not included.

Where the solution to Problem 30 is about the sum of the fifth power of the digits, this is about the sum of factorials of the digits.

I could copy paste the text from the solution to problem 30, but let me change the focus a bit. We can establish an upper bound of the problem by figuring out that 9!7 = 2540160 which is the upper limit. There is no possible higher value since 9!8 also results in a 7 digit number. First I will make a solution almost similar to the aforementioned solution, and later on I will speed it up, by pre-calculating the factorial. Continue reading →

Posted by Kristian in Project Euler, 24 comments