## Almost-magic squares of squares

2016-07-18 § Leave a comment

In the last post we saw that every 3×3 almost-magic square is a rearrangement of three three-term arithmetic progressions that have the same common difference. In other words, if we pick any three numbers *x*, *y* and *z*, and any common difference *d*, then the nine numbers

x–d, |
x, |
x+d |

y–d, |
y, |
y+d |

z–d, |
z, |
z+d |

can be rearranged to make an almost-magic square

x | z+d | y-d |

z-d | y | x+d |

y+d | x-d | z |

where all the rows and columns, and the leading diagonal, add up to *x*+*y*+*z*.

We’re interested in finding almost-magic squares where all the entries are square numbers, so that means we’re particularly interested in three-term arithmetic progressions of *squares*. Fortunately there is a well-developed theory of these things, which are closely related to Pythagorean triples.

« Read the rest of this entry »

## Magic squares of squares: Part I

2016-07-13 § 1 Comment

A recent Numberphile video discussed an intriguing unsolved problem in number theory: is there a 3×3 magic square whose entries are all square numbers? (Matt Parker proposed a solution which doesn’t *quite* work: see the video for more. The “Parker square” even has its own Twitter account.)

It turns out that this question leads to some interesting mathematics, which I’m going to have a go at explaining. At the very least I hope to give some insight into why it’s a hard problem.

To reduce the risk that I’ll run out of time and energy before pressing Publish, I’m going to split this post into two or possibly three parts, which I’ll post separately. The first part, which you’re reading **right now**, gives some background on 3×3 magic squares. The second will explain how to find *almost-magic* squares of squares using a bit of number theory and computer algebra. By *almost-magic* I mean that the rows and the columns and *one* of the two diagonals have the same sum.

The third, if I write it, will be more speculative and look at some possible approaches to either finding the mythical square of squares or proving that it doesn’t exist.

« Read the rest of this entry »

## Counting coins

2015-04-26 § 14 Comments

This afternoon, Matt Locke tweeted the following problem from his nine-year-old daughter’s maths homework:

## Tackling the Minimal Superpermutation Problem

2014-08-22 § 5 Comments

What’s the shortest string that contains every possible permutation of ABCD somewhere inside it? As it happens, it’s 33 letters long: ABCDABCADBCABDCABACDBACBDACBADCBA. A string like this is called a *minimal superpermutation*.

So what’s the shortest string that contains every possible permutation of ABCDE? It was recently shown that 153 letters is the shortest possible, and that there are eight different superpermutations of this length.

Okay, what about ABCDEF? The answer is that **nobody knows**. Until this week the shortest known superpermutation of ABCDEF was 873 letters long:

ABCDEFABCDEAFBCDEABFCDEABCFDEABCDFEABCDAEFBCDAEBFCDAEBCFDAEBCDFAEB CDAFEBCDABEFCDABECFDABECDFABECDAFBECDABFECDABCEFDABCEDFABCEDAFBCED ABFCEDABCFEDABCADEFBCADEBFCADEBCFADEBCAFDEBCADFEBCADBEFCADBECFADBE CAFDBECADFBECADBFECADBCEFADBCEAFDBCEADFBCEADBFCEADBCFEADBCAEFDBCAE DFBCAEDBFCAEDBCFAEDBCAFEDBCABDEFCABDECFABDECAFBDECABFDECABDFECABDC EFABDCEAFBDCEABFDCEABDFCEABDCFEABDCAEFBDCAEBFDCAEBDFCAEBDCFAEBDCAF EBDCABEFDCABEDFCABEDCFABEDCAFBEDCABFEDCABACDEFBACDEBFACDEBAFCDEBAC FDEBACDFEBACDBEFACDBEAFCDBEACFDBEACDFBEACDBFEACDBAEFCDBAECFDBAECDF BAECDBFAECDBAFECDBACEFDBACEDFBACEDBFACEDBAFCEDBACFEDBACBDEFACBDEAF CBDEACFBDEACBFDEACBDFEACBDAEFCBDAECFBDAECBFDAECBDFAECBDAFECBDACEFB DACEBFDACEBDFACEBDAFCEBDACFEBDACBEFDACBEDFACBEDAFCBEDACFBEDACBFEDA CBADEFCBADECFBADECBFADECBAFDECBADFECBADCEFBADCEBFADCEBAFDCEBADFCEB ADCFEBADCBEFADCBEAFDCBEADFCBEADCFBEADCBFEADCBAEFDCBAEDFCBAEDCFBAED CBFAEDCBAFEDCBA

and it was thought that might be the shortest possible.

But we now know it isn’t, because I found a shorter one:

ABCDEFABCDEAFBCDEABFCDEABCFDEACBFDEACFBDEACFDBEACFDEBACFDEABCDFEAB CDAEFBCDAEBFCDAEBCFDAEBCDFAEBCDAFEBCDABEFCDABECFDABECDFABECDAFBECD ABFECDABCEFDABCEDFABCEDAFBCEDABFCEDABCFEDACBFEDCABFDECAFBDCEAFBDCA EFBDCAFEBDCAFBEDCAFBDECAFDBECADFBECADBFECADBEFCADBECFADBECAFDEBCAD FEBCADEFBCADEBFCADEBCFADEBCAFDECBAFDECABFDCEABFDCAEBFDCABEFDCBAEFD BCAEDFBCAEDBFCAEDBCFAEDBCAFEDBCAEFDBACEFDBAECFBDAECFBADECFBAEDCFBA ECDFBACEDFBACDEFBACDFEBACDFBEACDFBAECFDBAEFCDBAFECDBAFCEDBAFCDEBAF CDBEAFCDBAEFDCBEAFDCBEFADCBEFDACBEFDCABFEDCBAFEDCBFAECDBFACEDBFACD EBFACDBEFACDBFEACDBFAECBDFEACBDFECABDFCEABDFCAEBDFCABEDFCBAEDFCBEA DFCBEDAFCBEDFACBEDFCABDEFCBADEFCBDAEFCBDEAFCBDEFACBDEFCABDFECBADFE CBDAFECBDFAECBFDAECBFADECBFAEDCBFEADCFBEADCFEBADCEFBADCEBFADCEBAFD CEBADFCEBADCFEABDCFAEBDCFABEDCFABDECFABDCEFABDCFEADBCEFADBCEAFDBCE ADFBCEADBFCEADBCFEADCBFEDACFBEDACFEBDACEFBDACEBFDACEBDFACEBDAFCEBD ACFEDBACFEDABC

I’ve uploaded a short note about it to the arxiv.

## Revisiting “On editing text”

2014-06-19 § 1 Comment

*This document is an incomplete draft.*

About two years ago I wrote about a category-theoretic treatment of collaborative text editing. That post is unique in the history of Bosker Blog in having been cited – twice so far that I know of – in the academic literature; so it’s a little embarrassing for me to have to explain that it is almost entirely wrong. The good news is that the core idea can be rescued, and the corrected story is quite interesting. Other writers on this subject seem to have made at least some of the same mistakes I did, so I hope this will be useful to at least a few other people too. « Read the rest of this entry »

## Decoding the mysterious symmetry of the bicycle lock numbers

2014-02-25 § Leave a comment

Suppose you have a lock of this sort that has *n* dials and *k* numbers on each dial. Let *m*(*n*, *k*) be the minimum number of turns that always suffice to open the lock from any starting position, where a turn consists of rotating **any number of adjacent rings** by one place.

In the previous post, we found an algorithm for computing these *bicycle lock numbers*, revealing a mysterious symmetry, « Read the rest of this entry »

## The bicycle lock problem

2014-02-18 § 4 Comments

Don’t lock your bicycle with a combination lock. Someone will steal it: I learnt this the hard way. It’s quite easy to open a combination lock by feel, without knowing the combination. Try it: with a bit of practice, you can open the lock with your eyes shut. (It’s easier to do this with an old wobbly lock than a tight-fitting new one.)

« Read the rest of this entry »