Project Euler 140: Modified Fibonacci golden nuggets

Project Euler 140: Modified Fibonacci golden nuggets

Problem 140 of Project Euler is very much a continuation of the Problem 137, as we can see from the problem description

Consider the infinite polynomial series AG(x) = xG1 + x2G2 + x3G3 + …, where Gk is the kth term of the second order recurrence relation Gk = Gk-1 + Gk-2, G1 = 1 and G2 = 4; that is, 1, 4, 5, 9, 14, 23, … .

We shall call AG(x) a golden nugget if x is rational. Find the sum of the first thirty golden nuggets.

In Problem 137 I mentioned in the end that the problem could be solved using a Diophantine equation. This is exactly the way I will go for this problem.

Read this article…
Project Euler 139: Pythagorean tiles

Project Euler 139: Pythagorean tiles

In Project Euler There are loads of problems that end up with a number theoretic solution. Problem 139 is no exception to that. The problem reads

Let (a, b, c) represent the three sides of a right angle triangle with integral length sides. It is possible to place four such triangles together to form a square with length c.

For example, (3, 4, 5) triangles can be placed together to form a 5 by 5 square with a 1 by 1 hole in the middle and it can be seen that the 5 by 5 square can be tiled with twenty-five 1 by 1 squares.

Given that the perimeter of the right triangle is less than one-hundred million, how many Pythagorean triangles would allow such a tiling to take place?

I will give you two different approaches to solving it.

Read this article…
Project Euler 138: Special isosceles triangles

Project Euler 138: Special isosceles triangles

Problem 138 of Project Euler reads

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

Read this article…
Project Euler 137: Fibonacci golden nuggets

Project Euler 137: Fibonacci golden nuggets

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 reads

Consider the infinite polynomial series AF(x) = xF1 + x2F2 + x3F3 + …, where Fk is the kth term in the Fibonacci sequence

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

Read this article…
Project Euler 136: Singleton difference

Project Euler 136: Singleton difference

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 reads

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

Read this article…
Project Euler 135: Same differences

Project Euler 135: Same differences

In Problem 135 of Project Euler we have another nice number theory problem. The problem reads

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

Read this article…
Project Euler 134: Prime pair connection

Project Euler 134: Prime pair connection

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 reads

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

Read this article…
Project Euler 133: Repunit nonfactors

Project Euler 133: Repunit nonfactors

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 reads

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

Read this article…
Project Euler 132: Large repunit factors

Project Euler 132: Large repunit factors

In problem 132 of Project Euler we are going back to working with repunits in a problem that reads

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

Read this article…
Project Euler 131: Determining primes, p, for which n^3 + n^2p is a perfect cube.

Project Euler 131: Determining primes, p, for which n^3 + n^2p is a perfect cube.

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 reads

There 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?

Read this article…
This site uses cookies.