Problem 102 at the UVa online judge deals with a special kind of bin packing problem, where we are asked to recycle glass in the most efficient way possible.We solve the problem by simple brute force. It may though be harder to implement than might seem at first sight. In any case, this is yet another easy problem from the UVa online judge.

Continue reading...Saturday, April 21, 2012

I really start feeling that the problems become more and more difficult. Problem 93 of Project Euler was not trivial at all. And as we shall see the only solution I found was a brute force solution. The problem readsFind the set of four distinct digits, a < b < c < d, for which the longest set of consecutive positive integers, 1 to n, can be obtained, giving your answer as a string: abcd. As I mentioned in the beginning, I have only been able to solve this using brute force. That being said there are several interesting aspects on how to cover the whole search space for the best solution.

Continue reading...Saturday, October 29, 2011

We have now been dealing with continued fractions for a good while, except for the last problem which was solved a good while ago. Problem 68 of Project Euler is completely different. It reads **Using the numbers 1 to 10, and depending on arrangements, it is possible to form 16- and 17-digit strings. What is the maximum 16-digit string for a "magic" 5-gon ring?**

Saturday, September 24, 2011

Problem 62 of Project Euler goesFind the smallest cube for which exactly five permutations of its digits are cube.I figured the problem could be attacked from two sidesWe generate numbers and check how many cubes exists of the number and its permutations We generate cubes until we find 5 that gives the same permutationI couldn't wrap my head around the first approach, and I think it would take an awful lot time since we would be dealing with a whole lot of numbers which are not cubes. Besides it is more expensive to calculate the cube root of a number than it is to go the other way.

Continue reading...Saturday, July 16, 2011

Problem 52 of Project Euler readsFind the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits.Between solving this problem and writing this text I did a bit of research on other peoples solutions. It seems that some people already knew the answer from an old high school exercise with fractions or from the book The man who counted by Malba Tahan. The book cover of that book is used for this posts headline image. I must admit that I didn't know that.

Continue reading...Saturday, June 25, 2011

Problem 49 of Project Euler asks us to find three numbers with the following propertiesThe arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another. There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.Avid readers of the blog knows how fond of prime number lists by now, so I took that approach instead. I took the following approach.Generate a list of primes below between 1000 and 10000. Take two primes i and j with i < jand calculate k = j + (j-i). Check if k< 10000 and check if k is a prime, if not go to 2. Check if i and j are permutations of each other and check if i and k are permutations of each other. If not go to 2. Found the triple, so exit.

Continue reading...Tuesday, May 17, 2011

When I first saw pandigital numbers I thought it was just a curious thing that we would visit once. I was wrong as Problem 42 of Project Euler is also about a special group of pandigital numbers. The problem readsFind the sum of all pandigital numbers with an unusual sub-string divisibility propertyWe will take two different approaches to this. First We will explore the brute force of generating all permutations and after that we will use the divisibility requirements to limit the number of permutations we have to explore.

Continue reading...Saturday, January 22, 2011

Problem 24 of Project Euler is about permutations, which is in the field of combinatorics. The posed question is as follows What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?There is a clever way to solve it, and a brute force solution. Since the brute force algorithm still requires some thought on how to generate permutation, I will cover both methods in this post.

Continue reading...
Wednesday, January 2, 2013

1 Comment