BigInteger

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

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

Problem 119 of Project Euler reads

The number 512 is interesting because it is equal to the sum of its digits raised to some power: 5 + 1 + 2 = 8, and 83 = 512. Another example of a number with this property is 614656 = 284.

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

You are given that a2 = 512 and a10 = 614656.

Find a30.

Continue reading →

Posted by Kristian in Project Euler, 15 comments
Project Euler 110: Find an efficient algorithm to analyse the number of solutions of the equation 1/x + 1/y = 1/n.

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

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 reads

In the following equation xy, and n are positive integers.

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?

NOTE: This problem is a much more difficult version of problem 108 and as it is well beyond the limitations of a brute force approach it requires a clever implementation.

Continue reading →

Posted by Kristian in Project Euler, 3 comments
Project Euler 97: Find the last ten digits of the non-Mersenne prime: 28433 × 2^7830457 + 1

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

I am almost embarrassed to make a post about problem 97 of Project Euler which reads

The first known prime found to exceed one million digits was discovered in 1999, and is a Mersenne prime of the form 26972593−1; it contains exactly 2,098,960 digits. Subsequently other Mersenne primes, of the form 2p−1, have been found which contain more digits.

However, in 2004 there was found a massive non-Mersenne prime which contains 2,357,207 digits: 28433×27830457+1.

Find the last ten digits of this prime number.

Continue reading →

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

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 reads

A googol (10100) is a massive number: one followed by one-hundred zeros; 100100 is almost unimaginably large: one followed by two-hundred zeros. Despite their size, the sum of the digits in each number is only 1.

Considering natural numbers of the form, ab, where a, b < 100, what is the maximum digital sum?

Continue reading →

Posted by Kristian in Project Euler, 9 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 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

Problem 48 of Project Euler has the nice and simple description

The series, 11 + 22 + 33 + … + 1010 = 10405071317.

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

Posted by Kristian in Project Euler, 14 comments

Project Euler 12 – Revisited

A while ago I treated Problem 12 of Project Euler and came up with several solutions as seen here.

Lets just repeat the problem here

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …

Let us list the factors of the first seven triangle numbers:

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

Continue reading →

Posted by Kristian in Project Euler, 4 comments

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

Back to the big numbers again in Problem 25 of Project Euler. The problem reads

The Fibonacci sequence is defined by the recurrence relation:

Fn = Fn-1 + Fn-2, where F1 = 1 and F2 = 1.
Hence the first 12 terms will be:
F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144
The 12th term, F12 is the first term to contain three digits.

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 →

Posted by Kristian in Project Euler, 20 comments

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

Just like the solution to problem 13 the answer to problem 16 of Project Euler has become trivial with .NET 4.0. And since I am lazy I intend to exploit the tools I am given. The problem description reads

215 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.
What is the sum of the digits of the number 21000?

If there didn’t exist a BigInteger class in .NET, then we would have needed to implement a way of storing the large result, which would need 1000 bits of storage, or around the size of 32 integers. Continue reading →

Posted by Kristian in Project Euler, 20 comments