# Combinatorics

## Project Euler 92: Investigating a square digits number chain with a surprising property.

Problem 92 of Project Euler is one of the more solve puzzles in this range, so based on that parameter this should be a pretty easy thing to chew through. The problem text reads

A number chain is created by continuously adding the square of the digits in a number to form a new number until it has been seen before.

For example,

44 → 32 → 13 → 10 → 1 → 1
85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89

Therefore any chain that arrives at 1 or 89 will become stuck in an endless loop. What is most amazing is that EVERY starting number will eventually arrive at 1 or 89.

How many starting numbers below ten million will arrive at 89?

I have found two methods to solve this. One where we  go through all 10.000.000 numbers to check what their cycle will be with a bit of help from some caching. And then a method where we exploit the fact that the order of the digits doesn’t matter and that significantly reduces the cases we need to check. Continue reading →

Posted by Kristian in Project Euler, 12 comments

## Project Euler 90: An unexpected way of using two cubes to make a square.

In the ninetieth problem of Project Euler  we are back in combinatorics with a problem description that reads

Each of the six faces on a cube has a different digit (0 to 9) written on it; the same is done to a second cube. By placing the two cubes side-by-side in different positions we can form a variety of 2-digit numbers.

For example, the square number 64 could be formed:

In fact, by carefully choosing the digits on both cubes it is possible to display all of the square numbers below one-hundred: 01, 04, 09, 16, 25, 36, 49, 64, and 81.

For example, one way this can be achieved is by placing {0, 5, 6, 7, 8, 9} on one cube and {1, 2, 3, 4, 8, 9} on the other cube.

However, for this problem we shall allow the 6 or 9 to be turned upside-down so that an arrangement like {0, 5, 6, 7, 8, 9} and {1, 2, 3, 4, 6, 7} allows for all nine square numbers to be displayed; otherwise it would be impossible to obtain 09.

In determining a distinct arrangement we are interested in the digits on each cube, not the order.

{1, 2, 3, 4, 5, 6} is equivalent to {3, 6, 4, 1, 2, 5}
{1, 2, 3, 4, 5, 6} is distinct from {1, 2, 3, 4, 5, 9}

But because we are allowing 6 and 9 to be reversed, the two distinct sets in the last example both represent the extended set {1, 2, 3, 4, 5, 6, 9} for the purpose of forming 2-digit numbers.

How many distinct arrangements of the two cubes allow for all of the square numbers to be displayed?

Posted by Kristian in Project Euler, 10 comments

## Project Euler 85: Investigating the number of rectangles in a rectangular grid

And now for something completely different.. or maybe as we will see later Problem 85 of Project Euler offers us a new problem where we can use the same ideas as for the solution to a previous problem. To lets start out with the problem text:

By counting carefully it can be seen that a rectangular grid measuring 3 by 2 contains eighteen rectangles:

Although there exists no rectangular grid that contains exactly two million rectangles, find the area of the grid with the nearest solution.

A nice and short problem text. I have found two possible solutions for the problem, one using brute force and the other applying some combinatorics to find an analytical solution to the number of rectangles that we have for a given size. Continue reading →

Posted by Kristian in Project Euler, 17 comments

## Project Euler 77: What is the first value which can be written as the sum of primes in over five thousand different ways?

In problem 77 of Project Euler we are asked the following question

It is possible to write ten as the sum of primes in exactly five different ways:

7 + 3
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2

What is the first value which can be written as the sum of primes in over five thousand different ways?

Posted by Kristian in Project Euler, 6 comments

## Project Euler 53: How many values of C(n,r), for 1 ≤ n ≤ 100, exceed one-million?

I have found Problem 53 of Project Euler to be a really interesting problem to work with, because there is a brute force solution and then there is a much more elegant solution if you dive into the mathematics behind the question.  The problem reads

There are exactly ten ways of selecting three from five, 12345:

123, 124, 125, 134, 135, 145, 234, 235, 245, and 345

In combinatorics, we use the notation, 5C3 = 10.

In general, $^nC_r = \frac{n!}{r!(n-r)!}$

where $r \leq n$, $n! = n\cdot (n-1)\cdot \dots \cdot 3 \cdot 2\cdot 1$ and $0! = 1$

It is not until n = 23, that a value exceeds one-million: 23C10 = 1144066.

How many, not necessarily distinct, values of  nCr, for 1 n 100, are greater than one-million?

I will present 2 different solution strategies each with 2 different solutions, so lets jump right into it. Continue reading →

Posted by Kristian in Project Euler, 17 comments

## Project Euler 51: Find the smallest prime which, by changing the same part of the number, can form eight different primes

When I worked on this problem I realised that I value two things about code – speed and simplicity. I always try to obtain both but in this case I had to sacrifice the simplicity in order to gain speed as we shall see. But before we dive into the code lets look at Problem 51 which is the problem description for the first problem on the second page of Project Euler. It reads

By replacing the 1st digit of *3, it turns out that six of the nine possible values: 13, 23, 43, 53, 73, and 83, are all prime.

By replacing the 3rd and 4th digits of 56**3 with the same digit, this 5-digit number is the first example having seven primes among the ten generated numbers, yielding the family: 56003, 56113, 56333, 56443, 56663, 56773, and 56993. Consequently 56003, being the first member of this family, is the smallest prime with this property.

Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime value family.

This problem can be solved in multiple ways.  You could run your way through all primes and check if each one is part of a family or you could do a bit of analysis on the problem to narrow down the problem you have to solve by code. I have chosen the latter. Continue reading →

Posted by Kristian in Project Euler, 21 comments

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

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 reads

The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.

Let d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, we note the following:

• d2d3d4=406 is divisible by 2
• d3d4d5=063 is divisible by 3
• d4d5d6=635 is divisible by 5
• d5d6d7=357 is divisible by 7
• d6d7d8=572 is divisible by 11
• d7d8d9=728 is divisible by 13
• d8d9d10=289 is divisible by 17

Find the sum of all 0 to 9 pandigital numbers with this property.

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

Posted by Kristian in Project Euler, 18 comments

## Project Euler 12 – Revisited

A while ago I treated Problem 12 of Project Euler and came up with several solutions as seen here.

Lets just repeat the problem here

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …

Let us list the factors of the first seven triangle numbers:

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

Posted by Kristian in Project Euler, 4 comments

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

Problem 24 of Project Euler is about permutations, which is in the field of combinatorics. The posed question is as follows

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

012 021 102 120 201 210

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 →

Posted by Kristian in Project Euler, 38 comments

## Project Euler 15: Routes through a 20×20 grid

The problem description in Problem 15 of Project Euler contains a figure, which I wont copy, so go ahead an read the full description at the Project Euler site. The problem can be understood without it though. The problem reads

Starting in the top left corner of a 2×2 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 20×20 grid?

My first question for many of the problems has been – Can it be brute forced? And my best answer to that is “probably”, but I cannot figure out how to generate all the routes. So instead I will give you two other approaches, which are both efficient. One is inspired by dynamic programming and the other gives an analytic solution using combinatorics. Continue reading →

Posted by Kristian in Project Euler, 38 comments