Posts Tagged with "Permutations"

uva102-header

UVa 102: Ecological Bin Packing

Wednesday, January 2, 2013

1 Comment

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

Project Euler 93: Using four distinct digits and the rules of arithmetic, find the longest sequence of target numbers.

Saturday, April 21, 2012

24 Comments

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...
Project Euler 68: What is the maximum 16-digit string for a "magic" 5-gon ring?

Project Euler 68: What is the maximum 16-digit string for a “magic” 5-gon ring?

Saturday, October 29, 2011

12 Comments

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?

Continue reading...
Project Euler 62: Find the smallest cube for which exactly five permutations of its digits are cube

Project Euler 62: Find the smallest cube for which exactly five permutations of its digits are cube

Saturday, September 24, 2011

6 Comments

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...
Project Euler 52: Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits in some order

Project Euler 52: Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits in some order

Saturday, July 16, 2011

6 Comments

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

Project Euler 49: Find arithmetic sequences, made of prime terms, whose four digits are permutations of each other

Saturday, June 25, 2011

22 Comments

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

Project Euler 43: Find the sum of all pandigital numbers with an unusual sub-string divisibility property

Tuesday, May 17, 2011

16 Comments

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

Project Euler 24: What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

Saturday, January 22, 2011

28 Comments

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