Recursion

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

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

Problem 118 have a very short problem description which in all it’s glory reads

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

Continue reading →

Posted by Kristian in Project Euler, 5 comments
Project Euler 117: Investigating the number of ways of tiling a row using different-sized tiles.

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

Problem 117 of Project Euler is a continuation of the problems given in Problem 114 to 116. The problem reads

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

Continue reading →

Posted by Kristian in Project Euler, 1 comment
Project Euler 116: Investigating the number of ways of replacing square tiles with one of three coloured tiles.

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

Problem 116 of Project Euler reads

A row of five 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).

If red tiles are chosen there are exactly seven ways this can be done.

 

If green tiles are chosen there are three ways.

 

And if blue tiles are chosen there are two ways.

Assuming that colours cannot be mixed there are 7 + 3 + 2 = 12 ways of replacing the black tiles in a row measuring five units in length.

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?

Continue reading →

Posted by Kristian in Project Euler, 8 comments
Project Euler 115: Finding a generalisation for the number of ways to fill a row with separated blocks.

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

Problem 115 of Project Euler is a continuation of Problem 114. The problem reads

NOTE: This is a more difficult version of problem 114.

A row measuring n units in length has red blocks with a minimum length of m 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.

Let the fill-count function, F(mn), represent the number of ways that a row can be filled.

For example, F(3, 29) = 673135 and F(3, 30) = 1089155.

That is, for m = 3, it can be seen that n = 30 is the smallest value for which the fill-count function first exceeds one million.

In the same way, for m = 10, it can be verified that F(10, 56) = 880711 and F(10, 57) = 1148904, so n = 57 is the least value for which the fill-count function first exceeds one million.

For m = 50, find the least value of n for which the fill-count function first exceeds one million.

Continue reading →

Posted by Kristian in Project Euler, 0 comments
Project Euler 114: Investigating the number of ways to fill a row with separated blocks that are at least three units long.

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

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 reads

A 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?
NOTE: Although the example above does not lend itself to the possibility, in general it is permitted to mix block sizes. For example, on a row measuring eight units in length you could use red (3), black (1), and red (4).

Continue reading →

Posted by Kristian in Project Euler, 5 comments