Posts Tagged with "Recursion"

Project Euler 118: Exploring the number of ways in which sets containing prime elements can be made.

Saturday, October 13, 2012


Problem 118 have a very short problem description which in all it's glory readsUsing all of the digits 1 through 9 and concatenating them freely to form decimal integers, different sets can be formed. Interestingly with the set {2,5,47,89,631}, all of the elements belonging to it are prime.How many distinct sets containing each of the digits one through nine exactly once contain only prime elements?I see two approaches to this problem of which I have taken one of them. The first solution approach which I have taken is to generate all permutations of the digits 1-9 and then check if you can split them in to ordered sets of primes.

Continue reading...

Project Euler 117: Investigating the number of ways of tiling a row using different-sized tiles.

Saturday, October 6, 2012

1 Comment

Problem 117 of Project Euler is a continuation of the problems given in Problem 114 to 116. The problem readsUsing a combination of black square tiles and oblong tiles chosen from: red tiles measuring two units, green tiles measuring three units, and blue tiles measuring four units, it is possible to tile a row measuring five units in length in exactly fifteen different ways.How many ways can a row measuring fifty units in length be tiled?This problem is actually more similar to Problem 114 than to Problem 116. The only difference between this and Problem 114 is that we have an uppper limit on the size of block, which we didn't in Problem 114. So we will just add that upper limit and remove the need for spaces between blocks to the recursive function and we are good to go.

Continue reading...

Project Euler 116: Investigating the number of ways of replacing square tiles with one of three coloured tiles.

Saturday, September 29, 2012


Problem 116 of Project Euler readsA row of black square tiles is to have a number of its tiles replaced with coloured oblong tiles chosen from red (length two), green (length three), or blue (length four).How many different ways can the black tiles in a row measuring fifty units in length be replaced if colours cannot be mixed and at least one coloured tile must be used?Apart from the added color this is not very different from problem 114. So we probably still want to solve it with a recursive function. However, we can't directly reuse the one we have. So lets look into the differences.

Continue reading...

Project Euler 115: Finding a generalisation for the number of ways to fill a row with separated blocks.

Saturday, September 22, 2012


Problem 115 of Project Euler is a continuation of Problem 114. The problem readsFor m = 50, find the least value of n for which the fill-count function first exceeds one million.With the very efficient solution from Problem 114 I couldn't help just trying to wrap it in a while loop until I found the solution.

Continue reading...

Project Euler 114: Investigating the number of ways to fill a row with separated blocks that are at least three units long.

Saturday, September 15, 2012


I wont brag that I have ever been good at spotting a problem which should be solved by using recursion. But problem 114 of Project Euler is so obvious a case that even I can see it. It readsA row measuring seven units in length has red blocks with a minimum length of three units placed on it, such that any two red blocks (which are allowed to be different lengths) are separated by at least one black square. There are exactly seventeen ways of doing this.How many ways can a row measuring fifty units in length be filled?

Continue reading...
This site uses cookies.