## My Favorite Sequences: A289523

This the second post in what will be a recurring series, My Favorite OEIS Sequences. Click here for the first post.

(If you like this sort of thing, check out the Integer Sequence Review from The Aperiodical!)

## A289523: Packing Circles of Increasing Area

In July 2017, I added a mathematically-silly-but-visually-fun sequence, A289523. The sequence works like this: place a circle of area $$\pi$$ centered at $$(1,1)$$, then place a circle of area $$2\pi$$ centered at $$(2,a(2))$$ where $$a(2) = 4$$, the least positive integer such that the circle does not overlap with the first circle. Next, place a circle of area $$3\pi$$ centered at $$(3,a(3))$$ where $$a(3) = 7$$ is the least positive integer such that the circle does not overlap with the first two circle. Continue this pattern ad infinitum, creating the earliest infinite sequence of positive integers such that no two circles overlap with any others, and a circle centered at $$(k, a(k))$$ has area $$k\pi$$.

I haven’t done much mathematical analysis on this problem, but it would be interesting to see if it’s possible to compute (or put some bounds on) the packing density of the convex hull of the circles. Also, a glance at a plot of the points suggests that the sequence is bounded above by a linear function—is this the case?

The sequence begins 1, 4, 7, 1, 11, 16, 5, 21, 27, 34, 10, 1, 41, 17, 49, 25, 57, 6, 33, 66, 43, 14, ....

### Finding an upper bound

The scatter plot of A289523 suggests that the centers of the circles have a linear upper bound. This is to be expected! The areas of the circles increase linearly, and the packing density is (presumably) nonzero.

What is the slope of the upper bound? And what is the packing density of these circles in the limit?

## Related Construction

At the end of March, I posted a related puzzle, “Placing Circles Along a Square Spiral”, on Code Golf Stack Exchange. For the post, I made a few animated GIFs that explain the construction and tweeted about them.

Impressively, Code Golf Stack Exchange users tsh, Arnauld, and A username each wrote (deliberately terse) Javascript code that computes the placement of these circles.

In fact, they compute something strictly harder! In the challenge, after laying down all of these circles (in blue), the challenge instructed them to go back to the start and greedily fill the gaps with (red) circles of increasing area. Next, they laid down a third (yellow) generation in the same fashion, and fourth (cyan) generation, and so on.

#### Related questions

• What is the packing density of the first (blue) generation?
• What is the packing density of the $$k$$-th generation?
• How many “steps” away from the origin is the smallest circle in the $$k$$-th generation?
• Do an infinite number of blue circles touch? Do an infinite number of any circles touch? Which ones?
• How far can a circle be from its neighbors? Which circles are maximally far from their neighbors?
• How does this work if the path the circles follow is not the spiral? Can different paths have significantly different packing densities?

If you have thoughts or ideas about any of this—or if you just want to make animated GIFs together—leave a comment or let me know on Twitter, @PeterKagey!

## My Favorite Sequences: A261865

This is the first installment in a new series, “My Favorite Sequences”. In this series, I will write about sequences from the On-Line Encyclopedia of Integer Sequences that I’ve authored or spent a lot of time thinking about.

I’ve been contributing to the On-Line Encyclopedia of Integer Sequences since I was an undergraduate. In December 2013, I submitted sequence A233421 based on problem A2 from the 2013 Putnam Exam—which is itself based on “Ron Graham’s Sequence” (A006255)—a surprising bijection from the natural numbers to the non-primes. As of today, I’ve authored over 475 sequences based on puzzles that I’ve heard about and problems that I’ve dreamed up.

## A261865: Multiples of square roots

(This problem is closely related to Problem 13 in my Open Problems Collection.)

In September 2015, I submitted sequence A261865:

$$A261865(n)$$ is the least integer $$k$$ such that some multiple of $$\sqrt k$$ falls in the interval $$(n, n+1)$$.

For example, $$A261865(3) = 3$$ because there is no multiple of $$\sqrt 1$$ in $$(3,4)$$ (since $$3 \sqrt{1} \leq 3$$ and $$4 \sqrt{1} \geq 4$$); there is no multiple of $$\sqrt{2}$$ in $$(3,4)$$ (since $$2 \sqrt{2} \leq 3$$ and $$3 \sqrt 2 \geq 4$$); but there is a multiple of $$\sqrt 3$$ in $$(3,4)$$, namely $$2\sqrt 3$$.

As indicated in the picture, the sequence begins $$\color{blue}{ 2,2,3,2,2},\color{red}{3},\color{blue}{2,2,2},\color{red}{3},\color{blue}{2,2},\color{red}{3},\color{blue}{2,2,2},\color{red}{3},\color{blue}{2,2},\color{red}{3},\color{blue}{2,2},\color{magenta}{7},\dots.$$

As the example illustrates, $$1$$ does not appear in the sequence. And almost by definition, asymptotically $$1/\sqrt 2$$ of the values are $$2$$s.

## Polygons on a “centered $$n$$-gon”

I asked a question on Math Stack Exchange, “When is it possible to find a regular $$k$$-gon in a centered $$n$$-gon“—where “centered $$n$$-gon” refers to the diagram that you get when illustrating central polygonal numbers. These diagrams are one of many possible generalizations of the triangular, square, and centered hexagonal grids. (Although it’s worth noting that the centered triangular grid is different from the ordinary triangular grid.)

## A catalog of polytopes and grids

On my OEIS wiki page, I’ve created some tables that show different kinds of polytopes in different kinds of grids. There are quite a number of combinations of polygons/polyhedra and grids that either don’t have an OEIS sequence or that I have been unable to find.

If you’re interested in working on filling in some of the gaps in this table, I’d love it if you let me now! And if you’d like to collaborate or could use help getting started, send me a message on Twitter!

## Parity Bitmaps from the OEIS

My friend Alec Jones and I wrote a Python script that takes a two-dimensional sequence in the On-Line Encyclopedia of Integer Sequences and uses it to create a one-bit-per-pixel (1BPP) “parity bitmaps“. The program is simple: it colors a given pixel is black or white depending on whether the corresponding value is even or odd.

### An Unexpected Fractal

We’ve now run the script on over a thousand sequences, but we still both agree on our favorite: the fractal generated by OEIS sequence A279212.

Fill an array by antidiagonals upwards; in the top left cell enter $$a(0)=1$$; thereafter, in the $$n$$-th cell, enter the sum of the entries of those earlier cells that can be “seen” from that cell.

Notice that in the images below, increasing the rows and columns by a factor of $$2^n$$ seems to increase the “resolution”, because the parity bitmap is self similar at 2x the scale. We still don’t have a good explanation for why we’d expect these images are fractals. If you know, please answer our question about it on Math Stack Exchange. (Alec and I have generated these images up to 16384 × 32768 resolution, roughly 536 megapixels.)

#### The Construction of the Sequence

The sequence is built up by “antidiagonals”, as shown in the GIF below. In the definition, “seen” means every direction a chess queen can move that already has numbers written down (i.e. north, west, northwest, or southwest). That is, look at all of the positions you can move to, add them all up, write that number in your square, move to the next square, and repeat. (The number in cell $$C$$ also counts the number of paths a queen can make from $$C$$ to the northwest corner using only N, NW, W, SW moves.)

(Interestingly, but only tangentially related: Code Golf Stack Exchange User flawr noticed that the number of north/west rook walks is related to the number of ways of partitioning a $$1 \times n$$ grid into triangles.)

## Parity Bitmaps for Other Sequences

It’s worth noting that many sequences are all black, consist of simple repeating patterns, or look like static. However, chess-type constructions, as illustrated by the GIF above, the one above yield images that look like the Sierpiński triangle. (See A132439 and A334017 below, and look at A334016 and A334745 via their OEIS entries.) Look below for a couple other sequences with interesting images too.

I ordered a poster-sized print of the A279212 fractal for Alec, and he framed it in his office.

Some ideas for further exploration:

## Stacking LEGO Bricks

Back in May, I participated in The Big Lock-Down Math-Off from The Aperiodical. In the Math-Off, I went head-to-head against Colin Beveridge (who has, hands-down, my favorite Twitter handle: @icecolbeveridge). Colin wrote about using generating functions to do combinatorics about Peter Rowlett’s toy Robot Caterpillar. Coincidentally and delightfully, I wrote about using generating functions to do combinatorics about Peter Kagey’s toy LEGOs.

Counting LEGO configurations is a problem dating back to at least 1974, when Jørgen Kirk Kristiansen counted that there are 102,981,500 ways to stack six 2×4 LEGOs of the same color into a tower of height six. According to Søren Eilers, Jørgen undercounted by 4!

In my Math-Off piece, I wrote about a fact that I learned from Math Stack Exchange user N. Shales—a fact that may be my (and Doron Zeilberger’s) favorite in all of mathematics: there are exactly $$3^{n-1}$$ ways to make a tower out of $$1 \times 2$$ LEGO bricks following some simple and natural rules. Despite this simple formula, the simplest known proof is relatively complicated and uses some graduate-level combinatorial machinery.

## The Rules

1. The bricks must lie in a single plane.
2. No brick can be directly on top of any other.
3. The bottom layer must be a continuous strip.
4. Every brick that’s not on the bottom layer must have at least one brick below it.

Gouyou-Beauchamps and Viennot first proved this result in their 1988 statistical mechanics paper, but the nicest proof that I know of can be found in Miklós Bóna’s Handbook of Enumerative Combinatorics (page 26). Bóna’s proof decomposes the stacks of blocks in a clever way and then uses a bit of generating function magic.

## Other rules

In preparation for the Math-Off piece, I asked a question on Math Stack Exchange about counting the number of towers without Rule 2. The user joriki provided a small and delightful modification of Bóna’s proof that proves that there are $$4^{n-1}$$ towers if only rules 1, 3, and 4 are followed.

It might also be interesting to consider the 14 other subsets of the rules. I encourage you to compute the number of corresponding towers and add any new sequences to the On-Line Encyclopedia of Integer Sequences. If you do so, please let me know! And I’d be happy to work with you if you’d like to contribute to the OEIS but don’t know how to get started.

Another natural question to ask: How many different towers can you build out of $$n$$ bricks if you consider mirror images to be the same? In the example above with the red bricks, there are six different towers, because there are three pairs of mirror images. By Burnside’s Lemma (or a simpler combinatorial argument) this is equivalent to counting the number of symmetric brick stacks. If there are $$s(n)$$ symmetric towers with $$n$$ bricks, then there are $$\displaystyle \frac 12 (3^{n-1}+s(n))$$ towers. For $$n = 4$$, there are three such towers, shown below in blue.

I asked about this function on Math Stack Exchange and wrote a naive Haskell program to compute the number of symmetric towers consisting of $$n \leq 19$$ bricks, which I added to the OEIS as sequence A320314. OEIS contributor Andrew Howroyd impressively extended the sequence by 21 more terms. I also added sequence $$A264746 = \frac 12 (3^{n-1}+A320314(n))$$, which counts towers up to reflection, and A333650, which is a table that gives the number of towers with $$n$$ bricks and height $$k$$.

## Stacking Ordinary Bricks

It is also interesting to count the number of (stable) towers that can be made out of ordinary bricks without any sort of mortar. I asked on Math Stack Exchange for a combinatorial rule for determining when a stack of ordinary bricks is stable. MSE user Jens commented that this problem is hard, and pointed to the OEIS sequence A168368 and the paper “Maximum Overhang” by Mike Paterson, Yuval Peres, Mikkel Thorup, Peter Winkler, and Uri Zwick, which provides a surprising example of a tower that one might expect to be stable, but in fact is not.

I’d still like to find a combinatorial rule, or implement a small physics engine, to determine when a stack of bricks is stable.

These problems and some generalizations can be found in Problem 33 of my Open Problem Collection. If you’d like to collaborate on any of these problems, let me know on Twitter. If you find yourself working on your own, I’d love for you to keep me updated with your progress!

(The graphics of LEGO bricks were rendered using the impressive and free LEGO Studio from BrickLink.)

## Regular Truchet Tilings

I recently made my first piece of math art for my apartment: a 30″×40″ canvas print based on putting Truchet tiles on the truncated trihexagonal tiling.

I first became interested in these sorts of patterns after my former colleague Shane sent me a YouTube video of the one-line Commodore 64 BASIC program:
 10 PRINT CHR$(205.5+RND(1)); : GOTO 10  I implemented a version of this program on my website, with the added feature that you could click on a section to recolor the entire component, and this idea was also the basis of Problem 2 and Problem 31 in my Open Problem Collection. I saw this idea generalized by Colin Beveridge in the article “Too good to be Truchet” in Chalkdust Magazine. In this article, Colin counts the ways of drawing hexagons, octagons, and decagons with curves connecting the midpoints of edges, and regions colored in an alternating fashion. In the case of the hexagon, there are three ways to do it, one of which looks like Palago tiles. It turns out that if you ignore the colors, the number of ways to pair up midpoints of the sides of a$latex 2n$-gon in such a way that the curves connecting the midpoints don’t overlap is given by the$latex n$-th Catalan number. For example, there are$latex C_4 = 14$ways of connecting midpoints of the sides of an octagon, where different rotations are considered distinct. There are three regular tilings of the plane by$latex 2n$-gons, the square tiling, the truncated square tiling, and the truncated trihexagonal tiling. Placing a Truchet tile uniformly at random over each of the$latex 2n\$-gons, results in a really lovely emergent structure.

If you find these designs as lovely as I do, I’d recommend taking a look at the Twitter bots @RandomTiling by Dave Richeson and @Truchet_Nested/@Trichet_Nested by @SerinDelaunay (based on a idea from Christopher Carlson) which feature a series of visually interesting generalizations of Truchet tilings and which are explained in Christopher’s blog post “Multi-scale Truchet Patterns“.

Edward Borlenghi has a blog post “The Curse of Truchet’s Tiles” about how he tried—mostly unsuccessfully—to sell products based on Truchet tiles, like carpet squares and refrigerator magnets (perhaps similar to “YoYo” magnets from Magnetic Poetry). The post is filled with lots of cool, alternative designs for square Truchet tiles and how they fit together. Edward got a patent for some of his ideas, and his attempt to sell these very cool products feels like it could have been my experience in another life.

If you want to see more pretty images and learn more about this, make sure to read Truchet Tilings Revisited by Robert J. Krawczyk! If you want to see what this looks like on a spherical geometry, check out Matt Zucker’s tweet. And if you want to try to draw some of these patterns for yourself, take a look at @Ayliean’s Truchet Tiles Zine.