Problem 138 of Project Euler readsFind ∑ L for the twelve smallest isosceles triangles for which h = b ± 1 and b, L are positive integers.The key to solving this problem is definitively to only consider the rightangled part of the triangle, such that you get a triangle consisting of one of the sides with length L, h and half the base (which I will denote x).I started out by figuring out that solutions would be primitive pythagorean triplets which we have worked with in Problem 9 among other places. So I tried to build a solution where I check to see if the triplets fulfill the condition that 2x ± 1 = h. However, I quickly ran into the fact that the solution would take forever to complete. So I had to take a step back and try another approach.

Continue reading...23 February 2013

I think that Problem 137 of Project Euler is a really fantastic problem since it has so many facets of how it can be solved. I will go through a one of them, and then link to a few other. The problem readsConsider the infinite polynomial series AF(x) = xF1 + x2F2 + x3F3 + ..., where Fk is the kth term in the Fibonacci sequenceWe shall call AF(x) a golden nugget if x is rational. Find the 15th golden nugget.I honestly don't know a whole lot about infinite series, and I am always quite intimidated by them. However, I know enough about them to know that there is something called a generating function which should be the keyword here.

Continue reading...16 February 2013

Problem 136 of Project Euler can be solved in a very easy way, and a very fast way. So lets look at the problem and dive right into the problem which readsThe positive integers, x, y, and z, are consecutive terms of an arithmetic progression. Given that n is a positive integer, the equation,x2 - y2 - z2 = n, has exactly one solution when n = 20:How many values of n less than fifty million have exactly one solution?So this sounds a bit like Problem 135? Well it is a lot like that, and this is where we will get out easy solution from.

Continue reading...9 February 2013

In Problem 135 of Project Euler we have another nice number theory problem. The problem readsGiven the positive integers, x, y, and z, are consecutive terms of an arithmetic progression, the least value of the positive integer, n, for which the equation, x2 - y2 - z2 = n, has exactly two solutions is n = 27.How many values of n less than one million have exactly ten distinct solutions?The first key insight which I missed for a while, is to notice that x,y and z is an arithmetic progression which means that we have that y = z + d and x = z + 2d.

Continue reading...2 February 2013

With a little help from Wikipedia I found Problem 134 of Project Euler rather easy to solve. Well it was easy after solving some issues I had with integer overflows and several other bugs. But anyway, the problem readsIn fact, with the exception of p1 = 3 and p2 = 5, for every pair of consecutive primes, p2 > p1, there exist values of n for which the last digits are formed by p1 and n is divisible by p2. Let S be the smallest of these values of n.Find ΣS for every pair of consecutive primes with 5 ≤ p1 ≤ 1000000.Based on the problem description it is rather easy to formulate this as linear congruence and then all we need to do, is to figure out how to solve that.

Continue reading...26 January 2013

Problem 133 of Project Euler is a continuation of Problem 132 and Problem 129 in which we are supposed to find the some prime numbers which are not factors of R(10n) for any n. In fact the problem readsFind the sum of all the primes below one-hundred thousand that will never be a factor of R(10n).I have found two methods for solving this. Both build upon the same principle which I will present first...

Continue reading...19 January 2013

In problem 132 of Project Euler we are going back to working with repunits in a problem that readsFind the sum of the first forty prime factors of the repuint R(109).This is a pretty large number, and having to actually do trial division would be a pain and take quite a while, even though we have BigInteger class which is certainly a help here.

Continue reading...12 January 2013

I am pretty sure the Problem 131 of Project Euler can be brute forced. However, if you start digging you will see that there is a really beautiful solution to the problem that readsThere are some prime values, p, for which there exists a positive integer, n, such that the expression n3 + n2p is a perfect cube.How many primes below one million have this remarkable property?

Continue reading...5 January 2013

Problem 130 of Project Euler is a continuation of problem 129, so if you have already solved that this one should be pretty easy. It readsFind the sum of the first twenty-five composite values of n for which GCD(n, 10) = 1 and n - 1 is divisible by A(n).If you have already solved Problem 129 as we have, this one can be solved pretty easily. We already have a function that will give us A(n), so we can just brute force our way through the problem calculating check if n-1 is divisible by A(n) and n is not a prime.

Continue reading...2 January 2013

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...This site uses cookies.

2 March 2013

9 Comments