Posts Tagged with "BigInteger"

problem119

Project Euler 119: Investigating the numbers which are equal to sum of their digits raised to some power

Saturday, October 20, 2012

9 Comments

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

Project Euler 110: Find an efficient algorithm to analyse the number of solutions of the equation 1/x + 1/y = 1/n.

Saturday, August 18, 2012

1 Comment

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

Project Euler 97: Find the last ten digits of the non-Mersenne prime: 28433 × 2^7830457 + 1

Saturday, May 19, 2012

1 Comment

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...
Project Euler 56: Considering natural numbers of the form, a^b, finding the maximum digital sum.

Project Euler 56: Considering natural numbers of the form, a^b, finding the maximum digital sum.

Saturday, August 13, 2011

7 Comments

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

15 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 48: Find the last ten digits of 1^1 + 2^2 + ... + 1000^1000

Project Euler 48: Find the last ten digits of 1^1 + 2^2 + … + 1000^1000

Saturday, June 18, 2011

12 Comments

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

Project Euler 12 – Revisited

Saturday, May 14, 2011

4 Comments

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

Project Euler 25: What is the first term in the Fibonacci sequence to contain 1000 digits?

Sunday, January 30, 2011

18 Comments

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

Project Euler 20: Sum of Digits in 100!

Wednesday, January 5, 2011

11 Comments

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

Project Euler 16: The sum of digits in 2^1000

Saturday, December 18, 2010

14 Comments

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