I’m always a little uncertain as to how far I can rasonably talk about Project Euler problems. The site is a superb resource that challenges you to develop programs to solve mathematical problems. For myself, it has helped both to improve my Python programming skills and to broaden my appreciation of just how diverse and fascinating a field Mathematics is.

However, the site does ask you not to share solutions and I can see the reason for this, If you can just copy and past the answer to a problem, then it all becomes a little pointless.

On the other hand, I do sometimes come up with solution for which I feel (I think) justifiably proud. In the case of Problem 250, the solution I was pleased with is not the solution to the problem, so I feel reasonably justified in talking about it.

So here goes…

Peter has nine four-sided (pyramidal) dice, each with faces numbered 1, 2, 3, 4.
Colin has six six-sided (cubic) dice, each with faces numbered 1, 2, 3, 4, 5, 6.

Peter and Colin roll their dice and compare totals: the highest total wins. The result is a draw if the totals are equal.

What is the probability that Pyramidal Pete beats Cubic Colin? Give your answer rounded to seven decimal places in the form 0.abcdefg

This looked to me like a simple question question of number crunching. If I know all of the combinations and frequencies that six six-sided dice can produce, and all the combinations and frequencies for nine four-sided dice, then I can simply work through every possible dice roll and see who wins.

The fun began when I decided I wanted a generic function that would give me, for any number of a dice, the frequency of every possible combination. It’s taken a while, but the final result turned out to be a lot simpler than I expected.

from itertools import product

def list_dice_combinations(number, dice):
    die = []
    for i in range(1, dice + 1):
        die.append(i)

    combinations = {}
    for roll in product(die, repeat = number):
        total = sum(roll)
        if total in combinations:
            combinations[total] += 1
        else:
            combinations[total] = 1
    return(combinations)

How you use this function is, of course, completely up to you.

Observant readers (both of you) will notice a graphic has just popped up in the sidebar of this blog. This should update automatically to reflect my Project Euler progress.

And, yes, after 16 months I have finally solved the first 50 problems.

I have to admit that some of my solutions are a little slower than they should be, but I am quite pleased to have made it this far and it is quite nice to be able to see the extent to which my Python is improving.

An n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital. This is a thing that I first encountered while solving Project Euler problems and it keeps on turning up – most recently (for me) in problem 43.

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 d₁ be the 1^st digit, d₂ be the 2^nd digit, and so on. In this way, we note the following:

d₂d₃d₄=406 is divisible by 2
d₃d₄d₅=063 is divisible by 3
d₄d₅d₆=635 is divisible by 5
d₅d₆d₇=357 is divisible by 7
d₆d₇d₈=572 is divisible by 11
d₇d₈d₉=728 is divisible by 13
d₈d₉d₁₀=289 is divisible by 17

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

My eventual approach was (mainly) to brute-force my way through all of the possible pandigitals and testing each against the divisible criteria listed. This, however, raised its own problem: How do I quickly generate a list of all nine digit pandigitals?

The answer turned out to be a rather elegant application of the itertools module.

#!/usr/bin/env python

import itertools

def yield_pandigitals(length):
    """ Yields all 0 to length pandigitals 
        length is an integer between 1 and 9 """ 
    for pandigital in list(itertools.permutations(range(length + 1))):
        yield int(''.join(map(str, pandigital)))

Well, I was rather pleased with it.

Also known as Project Euler problem 39:

If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.

{20,48,52}, {24,45,51}, {30,40,50}

For which value of p ≤ 1000, is the number of solutions maximised?

My first thought here was to generate an iterable collection of right angled triangles and accumulate a count of triangles by perimeter size. Don’t try this – it is far too slow an approach.

So my second thought was to try and iterate over the perimeter sizes and calculate the number of right angle triangles for each. It’s a long time since I had to think about Pythagoras but, for a triangle with sides a, b and c and a perimeter of p, I can make the following two statements:

a + b + c = p
a^2 + b^2 = c^2

Based on the second statement, above, I can also assert:
c = sqrt(a^2 + b^2)

Also:
c = p - a - b

Which means:
a^2 + b^2 = (p - a - b)^2

This can be expanded and simplified to state:
0 = pp - 2pb - 2ap + 2ab

or:

b = p(p - 2a) / 2(p - a)

Using this formula, we can say that for any values of p and a where p > a, if b is an integer then we have a right angle triangle.

One further optimisation: Intuitively, a can’t be greater than p/3.

Implementing this can then be done with two very simple for loops. The outer one iterates over all values of p and the inner one iterates over the range (2, int(p / 3)) and counts the number of integer values of b.

Also known as Project Euler Problem 38:

Take the number 192 and multiply it by each of 1, 2, and 3:

192 × 1 = 192
192 × 2 = 384
192 × 3 = 576

By concatenating each product we get the 1 to 9 pandigital, 192384576. We will call 192384576 the concatenated product of 192 and (1,2,3)

The same can be achieved by starting with 9 and multiplying by 1, 2, 3, 4, and 5, giving the pandigital, 918273645, which is the concatenated product of 9 and (1,2,3,4,5).

What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, … , n) where n > 1?

This is a problem for which finding a practical approach took a lot longer than the implementation of said approach. It’s also a problem that forced me to think about the actual maths of the problem. I already have an is_pandigital function, which I wrote to help solve problem 32, so the main challenge here is to constrain the search enough that I can avoid endless looping.

So, a bit of analysis…

For n = 2,
9 * (1, 2) = 918
98 * (1, 2) = 98196
987 * (1, 2) = 9871974
9876 * (1, 2) = 987619752 <- That's 9 digits

Since the problem mentions the pandigital, 918273645, I plugged this into the calculator as well,
9182 * (1, 2) = 918218365 <- That's 9 digits again

For n = 3,
9 * (1, 2, 3) = 91827
98 * (1, 2, 3) = 98196294 <- 8 digits is not enough
987 * (1, 2, 3) = 98719742961 <- 11 digits is too many

So I now know that the number I am looking for is n * (1, 2) where n is between 9876 and 9182.

The implementation, therefore, is a very simple loop that checks is_pandigital(int(str(n) + str(n * 2))) for values of n from 9876 to 9182.

The result is almost instantaneous.