Problem 119 of Project Euler readsWe shall define an to be the nth term of this sequence and insist that a number must contain at least two digits to have a sum.To be honest I have a bit of a bad feeling about the solution for this as it is based a whole lot on heuristics and guess when choosing the parameters. But lets give it a spin and see where we end up.

Continue reading...Saturday, August 18, 2012

Problem 110 of Project Euler is a continuation of Problem 108 except that we need a solution approach which is much more efficient. The problem readsIn the following equation x, y, and n are positive integers.1/x + 1/y = 1/n It can be verified that when n = 1260 there are 113 distinct solutions and this is the least value of n for which the total number of distinct solutions exceeds one hundred.What is the least value of n for which the number of distinct solutions exceeds four million?So what happens if we just run the same code as in problem 108? Well first of all we would get in problems with the capacity of the variables, but we could just change it to BigInteger and then run it. I tried, and gave up after a while. So I changed the solution approach...

Continue reading...Saturday, May 19, 2012

I am almost embarrassed to make a post about problem 97 of Project Euler which readsHowever, in 2004 there was found a massive non-Mersenne prime which contains 2,357,207 digits: 2843327830457+1. Find the last ten digits of this prime number.I decided to use the BigInteger class for solving this, so I didn't have to care about numerical issues. The only other insight that was needed was to use the ModPow method which takes the modulo along with the power instead of doing those seperatly.

Continue reading...Saturday, August 13, 2011

Problem 56 of Project Euler is one of those problems where I really haven't found a nice method for solving it. The problem description readsConsidering natural numbers of the form, ab, where a, b < 100, what is the maximum digital sum?I have only found a brute force solution with a bit of pruning, so lets jump right into that. The first thing we need is a method to calculate the digit sum of a number. Since some of the numbers are pretty big I have chosen to keep everything in BigInteger, so the fastest C# method I can conjure up for calculating the digit sum is

Continue reading...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, June 18, 2011

Problem 48 of Project Euler has the nice and simple descriptionFind the last ten digits of the series, 11 + 22 + 33 + ... + 10001000.When I first saw the problem, I thought I knew it would be trivial to solve with BigInteger. However, it turns out that the solution lacks performance, so I have derived another solution as well based on the properties of the modulo operator.

Continue reading...Saturday, May 14, 2011

A while ago I treated Problem 12 of Project Euler and came up with several solutions as seen here.In relation to that post Nazia asked me if the code would scale, and that made me realise that the current implementation of the function for calculating the number of divisors is dependent on the prime array that I used to be large enough. If this isn't the case the calculated number of divisors may very well be wrong. Besides that, using integers limits the solution to numbers less than approximately 2.7 billion.

Continue reading...Sunday, January 30, 2011

Back to the big numbers again in Problem 25 of Project Euler. The problem reads What is the first term in the Fibonacci sequence to contain 1000 digits?With the BigInteger class this is rather easy to brute force. So a brute force solution is one of the two solutions I will show you. The other solution is one you can use with a calculator, or if you are good at mental arithmetic, you can do it with pen and paper.

Continue reading...Wednesday, January 5, 2011

Given problem 20 of Project Euler which reads Find the sum of the digits in the number 100!I exploit the BigInteger class in .NET 4.0 which makes it easy to operate on large integers, and thereby makes it a matter of slicing up the big number.

Continue reading...Saturday, December 18, 2010

Given problem 16 of Project Euler which reads What is the sum of the digits of the number 21000?I exploit the BigInteger class in .NET 4.0 which makes it easy to operate on large integers, and thereby makes it a matter of slicing up the big number.

Continue reading...
Saturday, October 20, 2012

9 Comments