MathBlog

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

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

Problem 10127 at UVa Online Judge, Ones, is a neat little problem. We are given an integer and are asked to find its smallest multiple that consists only of ones.

We start off by coming up with a simple brute-force solution which, unfortunately, doesn’t even work. With some clever observations and some thinking in reverse-mode, we manage create a good solution that works. We also see the interesting results of an attempt I made to make an even faster solution, which unfortunately turned out to be slower.

I was all excited when I first saw the headline of Problem 96 of Project Euler  since I love solving SuDoku puzzles. And I wasn’t disappointed when I saw the problem description which reads

By solving all fifty puzzles find the sum of the 3-digit numbers found in the top left corner of each solution grid; for example, 483 is the 3-digit number found in the top left corner of the solution grid above.

Ok, I have cheated a bit since I dabbled into making a solver for Sudoku puzzles a while ago, so I decided to reuse it for this solution. I have implemented a brute force solver as well as implemented logic limit the number of solutions.

In problem 10229 at UVa Online Judge, Modular Fibonacci, our task is to calculate huge Fibonacci numbers, modulo some given integer.

We analyse different methods of computing Fibonacci numbers, but they are either too slow or aren’t applicable in our situation.
We end up developing a fast solution that makes use of Fibonacci numbers in matrix form and exponentiation by squaring.

We have added a new section to the site with many more programming challenges and upcoming competitions and events. Sites with programming challenges First of all we have a list of sites which offers programming and math challenges for you to try out. It can be found in the top menu under programming challenges. So [...]

Even though we are still below 5000 people who have solved Problem 95 of Project Euler this problem it proved to be a relatively easy problem to solve. The main challenge was to find a method to get the speed of the solution to reasonable level. The problem reads

Find the smallest member of the longest amicable chain with no element exceeding one million.

I managed to make two solutions which differs in the way they calculate the sum of factors. Otherwise they are the same. The first solution relies on a function to return the sum of factors when needed. This method I will cover first.

As you (of course) must have noticed, not all of the posts are written by me anymore. I have gotten a new guy on board in order to serve you even more goodies than I my self was able to. So I would like to formally welcome Bjarki on board on the blog and hope that [...]

UVa Online Judge is a website hosted by the University of Valladolid, Spain.

It has two main roles. First, it’s a problem archive with over 3500 programming problems. Second, you can upload your solution to one of the problems in the archive, and the online judge will determine whether it’s correct or not.

We cover the basic steps on how to submit your first solution and list a couple of tools to help you solve problems.

I can realy feel that the problems become harder and harder. Problem 94 of Project Euler took me a good while to figure out. The problem is easy to understand and reads

We shall define an almost equilateral triangle to be a triangle for which two sides are equal and the third differs by no more than one unit.

Find the sum of the perimeters of all almost equilateral triangles with integral side lengths and area and whose perimeters do not exceed one billion (1,000,000,000).

We are dealing with a triangle with two sides of length a and one side of length b = a-1 or b = a+1. I will treat these as two different cases for the next paragraf or two.

In UVa 294, Divisors, we are asked to find the number with the maximum number of divisors in a given range. Counting number of divisors is a classic problem, and there exists a fast and simple way to do it. We start off with a straight-forward, but slow, implementation and progressively optimize it until it’s fast enough. We don’t stop there, though, but we end with a much faster implementation by noticing that divisor count is related to prime factorization.