A European adult with a computer can be as smart as a Vietnamese Eight year old

I’m quite liking the puzzles coming out of Alex Bellos’s Adventures in Numberland. This week’s challenge: Can you do the maths puzzle for Vietnamese eight-year-olds that has stumped parents and teachers?

You have a simple arithmetic equation and you have to place the digits from one to 9 in the grid so that the result is 66. And I thought that sounded pretty easy – there are only 362880 possible combinations, I just need a trial and error method to work through the combinations until I find the right one.

Thank you Python.

Firstly, a function to yield all the possible permutations in a list

def yield_permutations(the_list):
    """ Yields all permutations for a list """
    length = len(the_list)
    if length <= 1:
        yield the_list
        for i in range(0, length):
            for j in yield_permutations(the_list[:i] + the_list[i+1:]):
                yield [the_list[i]] + j

And then I just need to plug the values into the formula

digits = []
for i in range(1, 10): 

for x in yield_permutations(digits):
    result = x[0] + 13 * x[1] / x[2] + x[3] + 12 * x[4] - x[5] - 11 + x[6] * x[7] / x[8] - 10
    print(x, result)
    if result == 66:

I’m sure there is a more elegant way of doing this, but after checking my result by hand, I can confirm that this approach also works.

Towel was a silly name for a repository

I mentioned about a week ago that I was starting to consolidate some of the short scripts that I have knocked together and pushed to GitHub over the years. This is still in progress but I have decided to consolidate these into two repositories: utilities and silliness. Because A lot of what I do is quite silly.

Going forward, anything short I throw together will end up in one or the other of these repositories. Now I just need to tidy up my current mess of folders.

Exponential Origami

Raju Varghese (via Sploid) claims that if you fold a piece of paper 103 times, the thickness of your paper will be larger than the diameter of the observable universe: 93 billion light years. The explanation is simple enough – every time you fold a piece of paper you double its thickness and when you start doubling things they get very large very quickly – but I couldn’t leave this without checking the numbers for myself.

Of course, I couldn’t resist checking this for myself and pulled out a calculator. I soon found that the mental juggling needed to get from fractions of millimetres to kilometres was too much for my little brain and converting between millimetres and light years was going to be impossible.

So I wrote a script. The code is pretty simple, as you can see below, although I did have a four fold discrepancy when I first ran it (I came up with 107 folds needed, rather than 103). It turned out that my initial thickness of the paper was out by a factor of 10. Once I fixed this, everything matched.

#!/usr/bin/env python
""" Foldpaper
    Calculates the thickness of a piece of paper after n folds """

thickness = 0.1
folds = 0
meter = 1000
kilometer = 1000000
lightyear = 1000000 * 9000000000000
size_of_universe_in_mm = 93000000000 * lightyear

while thickness  1:
        print(folds, int(thickness/lightyear), 'light years')
    elif int(thickness / kilometer) > 1:
        print(folds, int(thickness/kilometer), 'kilometers')
    elif int(thickness / meter) > 1:
        print(folds, int(thickness/meter), 'meters')
        print(folds, thickness, 'mm')

And then, with a slight edit, I dumped the results into a table so that I could add a few comparative distances.

Folds Height Notes
15 3 metres Taller than the average human
22 419 metres Taller than The Shard in London
27 13 kilometres We’re now standing higher than Mount Everest
42 439804 kilometres Now we’ve just passed the Moon
51 225179981 kilometres And the Sun
56 7205759403 kilometres And finally we reach Pluto
69 6 light years With a single fold, we have shot past Alpha Centuri
83 107460 light years And now the thickness of our piece of paper is larger than the Milky Way
88 3438722 light years And in a few short folds, we pass Andromeda
103 112680053353 light years And with that final fold, we have exceeded the size of the Universe

Exponentiation is awesome.

Prime pair sets

I started playing around with Project Euler way back in November 2011, not least as an opportunity to hone my still nascent Python skills. And I’m still learning.

Problem 60 states:

The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property.

Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.

This took a bit of thinking about but the approach I eventually came up with was to create a set of concetanatable primes for each prime (up to an arbitarily chosen value of 10000). Then all I would need to do is search each set for intersecting elements until I found five intersecting sets. Since the primes are generated in order, from lowest to highest, the first set of five intersecting sets will give me the answer.

Then for the implementation…

I already have a function that returns a list of primes, so that was easy, and using a dictionary keyed by prime was a no-brainer, but looking for set intersections was a bit of a struggle. Until I discovered that Python will do it for me. Using the set class it becomes remarkably easy to build a dictionary of sets and then work through them, checking intersections, until I find five sets that intersect.

My actual code is neither nice nor fast, and it isn’t going to scale at all – but I am quite pleased to have gained a handle on yet another iterable type.

Dice combinations

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):

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

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

Fifty solutions in sixteen months

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.

Yielding pandigitals

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

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.

Desperately seeking Pythagoras

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)

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


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.

Desperately seeking pandigitals

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.