(Previously, previously)

To not bury the lede, we finally have our first new value for the OEIS sequence A000769:And its corollary A000755.

a(19) = 32577

This was calculated in 255 GPU-hours using eight RTX 4090s rented from Runpod.

Not only that! With help from Thomas Prellberg and the GPU cluster at Queen Mary University of London, we’ve been able to find some solutions with record-breaking sizes. The largest at the time I’m writing this is 64×64, shown below, with hopefully more on the way.

For the last month I’ve been completely addicted to the logic puzzle game Tametsi. Put briefly, it’s ordinary Minesweeper but with a set of 160 hand-crafted puzzles rather than a randomly generated starting board. Beyond the Minesweeper rules that we’re all familiar with, there are only a couple of additions: non-square/irregular grids for many of the puzzles, and “global” constraints, such as a fixed number of mines in cells of a particular colour or along a specified line.

I finally finished all the available puzzles and so Tametsi has released its grip on me. I’ve been trying to figure out what made it so compelling, and here’s the best I could come up with.

In the Game of Life, which still lifes can be produced by crashing gliders together? We’ve known for a few years that the answer cannot be “all of them”, because in 2022 Ilkka Törmä and Ville Salo found a patch of still life that, if it exists in the universe, must have existed since the beginning of time. And so, there is no way we could have produced it out of empty space through glider collisions. Similar such patches have been found since, with the goal of optimising size or population, and at the time of writing the record holder is an unsynthesizable still life with population 154 produced by forum user “400spartans”.

Finding syntheses for small still lifes is easy, but at some unknown point below 154 it becomes impossible. Today, we completed our collaborative project to notch the lower bound up from 22 to 23, by giving explicit syntheses for all 1,646,147 (strict)A still life is strict when all its islands are necessary to maintain the stability of the pattern. still lifes with population 23.

The code in the previous post is fairly quick, but of course we’d always prefer it to be quicker. I’ll keep a record here of things I’ve tried and whether they worked.

The No-three-in-line problem asks how many points can be placed on a n \times n grid so that no three points are on the same line, where the lines considered are of any slope and not just orthogonal and diagonal. Each row/column can contain at most 2 points, so clearly the answer is at most 2n. The real question is, can we actually achieve 2n for every grid size? It’s conjectured that the answer is “no” for grids large enough, but we don’t know where the crossover point is and there’s no indication that the number of 2n-point solutions is falling away from exponential growth, at least up to 18 \times 18!

To my eye, the configurations that work can be quite balanced and attractive. Here are some symmetrical ones for 14 \times 14 (though in general the solutions are not necessarily symmetric in this way):

The most extensive searches for configurations so far have been done by Achim Flammenkamp and later by Ben Chaffin. I’ve written some CUDA codeBy the way, the existing cuda-mode for Emacs is a bit messed up, I have a fork with some bugfixes here. of my own with the goal of pushing things a little further, and I’ll explain it in the rest of this post.