Triangle Center Patterns

I made a video that illustrates a particularly interesting “discrete state random dynamical system,” which was inspired by a Tweet (and a mistake) that I saw.

First, be hypnotized by this video, which I recommend you watch in 4K, and then scroll down to read about the inspiration and the cool math going on under the hood.

Matt Henderson’s tweet

This whole exploration came from a “happy accident” that Matt Henderson made (and corrected) in the Tweets below. Watch the video in the first tweet, which shows an concrete example of the “discrete state random dynamical system” that I mentioned earlier.

Matt’s mistake got me interested! If the centroid and the incenter create such interesting and intricate designs, what about other triangle centers like the circumcenter or the orthocenter? In particular, I was interested in finding examples of interesting triangle centers from Clark Kimberling’s Encyclopedia of Triangle Centers (ETC), which is a database with over 53,000 named triangle centers, including all of those that you have heard about.

Patterns from other triangle centers

Instead of illustrating the results of this process on hexagons as Matt did in his tweet, I’ve done the iterative process on squares. Here are six examples illustrating the patterns for various triangle centers from ETC.

Some basics of triangle centers

In the video at the top, I interpolate between 20 chosen triangle centers in a continuous way so that we can see how the image transforms as we transform the choice of triangle center.

In order to understand what’s going on, you have to understand something about coordinates. We can define a triangle center with a map \(f\colon \mathbb{R}^3 \to \mathbb{R}\) such that \(f(a,b,c)\) is symmetric in \(b\) and \(c\). What we do is take the triangle with vertices \(\vec{v}_1\), \(\vec{v}_2\), and \(\vec{v}_3\), define \(a = |\vec{v}_2 – \vec{v}_3|\), \(b = |\vec{v}_1 – \vec{v}_3|\), and \(c = |\vec{v}_1 – \vec{v}_2|\), and define the midpoint as the weighted average \[\frac{f(a,b,c) \vec{v}_1 + f(b,c,a)\vec{v}_2, + f(c,a,b)\vec{v}_3}{f(a,b,c) + f(b,c,a) + f(c,a,b)}.\] Whenever \(f(a,b,c)\), \(f(b,c,a)\), and \(f(c,a,b)\) are simultaneously positive, this will describe a point inside the triangle. This way of describing points in space is called a “barycentric coordinate system“.

An illustration of the vertices and sides.

In the table below, I give examples of five triangle centers and their description in barycentric coordinates. In the case of \(X(2)\), the barycentric coodinates say that the centroid is just an honest average of the vertices. In all other cases, the other triangle centers are weighted averages of the vertices.

Triangle CenterBarycentric
X(1) = INCENTER\(f(a,b,c) = a\)
X(2) = CENTROID\(f(a,b,c) = 1\)
X(6) = SYMMEDIAN POINT\(f(a,b,c) = a^2\)
X(10) = SPIEKER CENTER\(f(a,b,c) = b + c\)
X(58) = ISOGONAL CONJUGATE OF X(10)\(\displaystyle f(a,b,c) = \frac{a^2}{b + c}\)
A table of five triangle centers and the corresponding barycentric coordinates.

A curve of triangle centers

The triangle centers in the video are all described by functions of the form \[f(a,b,c) = a^{x_1}(b + c – a)^{x_2} (bc)^{x_3} (b^{x_4} + c^{x_4})^{x_5},\] where \((x_1, x_2, x_3, x_4, x_5) \in \mathbb{R}^5\) and each frame follows a path in \(\mathbb{R}^5\), which intersects a triangle center from ETC for a single frame every ten seconds. In order to get this path in five-dimensional space, the code stitches together twenty piecewise-defined Bézier curves into a differentiable curve that goes through those twenty “anchor points”, as suggested by the following illustration. (Thankfully I could reuse some of the code I wrote for my Twitter bot @BotzierCurves!)

A two-dimensional example of a curve through seven anchor points.

In addition to choosing a slightly different triangle center in each frame, the colors of the points change throughout time as well. For example, in the picture below, the pixel is colored white if the same side is chosen twice in a row, red if the opposite side is chosen, and blue or green if the side to the left or right of the previous side is chosen. In the video, these colors change too, by following a Bézier curve through the three-dimensional RGB colorspace.

An illustration of a triangle center pattern where the color of the pixel depends on the order that the sides are chosen.

You can download the code for yourself by visiting my MathArt repository on Github. If you have thoughts on this, if you want to play around with these ideas together, or if you just want to chat, please don’t hesitate to reach out!

How to Make Animated Math GIFs: LaTeX + TikZ

The first animated GIF that I ever made was made with the LaTeX package TikZ and the command line utility ImageMagick. In this post, I’ll give a quick example of how to make a simple GIF that works by layering images with transparent backgrounds on top of each other repeatedly.

TikZ code

In our first step toward making the above GIF, we’ll make a PDF where each frame contains one of the above circles on a transparent background. In this case, each circle is placed uniformly at random with its center in a \(10 \times 10\) box, with a radius in \([0,1]\), and whose color gets progressively more red and less green with a random amount of blue at each step.

\documentclass[tikz]{standalone}
\usepackage{tikz}

\begin{document}
\foreach \red[evaluate=\red as \green using {255 - \red}] in {0,1,...,255} {
  \begin{tikzpicture}
    \useasboundingbox (0,0) rectangle (10,10);
    \pgfmathrandominteger{\blue}{0}{255}
    \definecolor{myColor}{RGB}{\red,\green,\blue}
    \fill[myColor] ({10*random()},{10*random()}) circle ({1+random()});
  \end{tikzpicture}
}
\end{document}

Starting with \documentclass[tikz]{standalone} says to make each tikzpicture its own page in the resulting PDF.

Next we loop through values of \red from 0 to 255, each time setting \green to be equal to 255 - \red so that with each step the amount of red goes up and the amount of green goes down.

The command \useasboundingbox (0,0) rectangle (10,10); gives each frame a \(10 \times 10\) bounding box so that all of the frames are the same size and positioned the same way.

The command \pgfmathrandominteger{\blue}{0}{255} chooses a random blue values between 0 and 255.

The command \fill[myColor] ({10*random()},{10*random()}) circle ({1+random()}); places a circle with its center randomly chosen in the \(10 \times 10\) box and with a radius between \(1\) and \(2\).

ImageMagick

When we compile this code, we get a PDF with one circle on each page. In order do turn this PDF into an animated GIF, we convert the PDF using ImageMagick, a powerful command-line utility for handling images. If we named our PDF bubbles.pdf then running the following code will give us an animated GIF called bubbles.gif.

convert -density 300 -delay 8 -loop 0 -background white bubbles.pdf bubbles.gif

I hope that you use this blog post as a jumping off point for making animated GIFs of your own! If you do, please reach out to share them with me!

XOR Triangles

In this post, I’ll explore the math behind one of my Twitter bots, @xorTriangles. This bot was inspired by the MathOverflow question “Number triangle,” asked by user DSM posted in May 2020.

(I gave an overview of my Twitter bots @oeisTriangles in my post “Parity Bitmaps from the OEIS“. And if you want to build your own bot, I showed the steps for building @BotfonsNeedles in parts I, II, and III of my three-part series “A π-estimating Twitter bot”.)

In May 2020, MathOverflow user DSM posted a question “Number triangle” where they asked about the following construction:

Start with a list of \(n\) bits (\(0\)s and \(1\)s), and to get the next row, combine all adjacent pairs via the XOR operation, \(\oplus\). (A mathematician might call this “addition modulo \(2\).”) That is $$\begin{alignat*}{2} 0 \oplus 0 &= 1 \oplus 1 &&= 0 \quad\text{and} \\ 0 \oplus 1 &= 1 \oplus 0 &&= 1.\end{alignat*}$$

For example, starting with the row \(110101\), the resulting triangle is $$1~~~1~~~0~~~1~~~0~~~1\\ 0~~~1~~~1~~~1~~~1\\ 1~~~0~~~0~~~0\\ 1~~~0~~~0\\ 1~~~0\\ 1$$

We’re especially interested in understanding the triangles with rotationally symmetric boundaries (and consequently insides)! OEIS sequence A334556 enumerates all of the rotationally symmetric triangles with a \(1\) in the upper left corner.

@xorTriangles

My Twitter bot @xorTriangles posts these triangles four times a day, alternating between the triangles described above and a “mod \(3\)” analog. If you want to see how it works, you can check it out on Github.

Here is an illustration by Michael De Vlieger that shows many small XOR triangles and which is available on the OEIS.

Michael De Vlieger’s image on the OEIS.
My Twitter bot @xorTriangles currently follows the same convention.

Mathematica

One way to find a rotationally symmetric XOR triangle is by setting up a system of equations. Using the convention that the top row of the triangle is labeled \(x_0, x_1, \dots, x_n\), we can use the Pascal’s Triangle-like construction to set up a system of linear equations over \(\mathbb{Z}/2\mathbb{Z}\). The solutions of this system of equations are precisely those that correspond to the XOR triangle we care about! This allows us to write down a matrix whose null space is the set of such triangles:

$$\begin{align}x_n &= x_0\\x_{n-1} &= x_0 + x_1\\x_{n-2} &= x_0 + 2x_1 + x_2\\ &\vdots \\ x_k &= \sum_{i=0}^{n-k} \binom{n-k}{i}x_i \\ &\vdots \\ x_0 &= \binom{n}{1}x_0 + \binom{n}{1}x_1 + \dots + \binom{n}{n}x_n\end{align}$$

Using Mathematica to find the null space works like this:

value[i_, j_, n_] := Binomial[i, j] - If[j == n - i, 1, 0];
xorSeedsBasis[n_] := NullSpace[
  Table[value[i, j, n], {i, 0, n}, {j, 0, n}],
  Modulus -> 2
];

Because this is the null space of a \(n+1 \times n+1\) matrix over \(\mathbb{Z}/2\mathbb{Z}\), we know that there must be \(2^M\) rotationally symmetric XOR triangles, where \(M\) is an integer—which isn’t obvious from the original construction!

Related OEIS sequences

If you’re interested in learning more about this construction, reach out to me or take a look at some of these related OEIS sequences:

  • A334596: Number rotationally symmetric triangles of size \(n\) with \(1\)s in the corners.
  • A334591: Largest triangle of \(0\)s in the XOR triangle generated by the binary expansion of \(n\).
  • A334592: Total number of \(0\)s in the XOR triangle generated by the binary expansion of (n).
  • A334593: Total number of \(1\)s in the XOR triangle generated by the binary expansion of \(n\).
  • A334594: Binary interpretation of the \(k\)-th row of the XOR triangle generated by the binary expansion of \(n\).
  • A334930: Numbers that generate rotationally symmetrical XOR-triangles featuring singleton zero bits in a hexagonal arrangement. (from Michael De Vlieger, see his illustration)

Robot Walks

I’ve gotten a lot of mathematical inspiration from Project Euler questions, but perhaps the question that has gotten me thinking the most is Project Euler Problem 208: Robot Walks. In this problem, a robot takes steps either to the right or the left, and at each step, it turns \(\frac 15\) of the way of a circle.

Project Euler Problem 208

Demo

I started thinking about this problem more seriously after I met Chase Meadors at the 2018 Graduate Student Combinatorics Conference and learned about his Javascript applet which allows a user to control a (virtual) robot 🤖 by using the left and right arrow keys. By repeating the same sequence of moves (e.g. \(4\) steps to the right followed by \(2\) steps to the left) I found that the robot traced out surprising symmetric patterns.

I cloned Chase’s Github Repo so that I could customize the robot further. If you go to the URL https://peterkagey.github.io/project-euler-208/?n=8&w=3,2,5,1 you’ll see an example of a robot walk, where n=8 means that each step will be \(\displaystyle \frac 18\) of a circle, and w=3,2,5,1 means that the robot will follow the pattern of \(3\) steps to the right followed by \(2\) steps to the left, followed by \(5\) steps to the right, followed by \(1\) step to the left, and repeating this pattern until it returns to where it began.

Stack Exchange Questions

I’ve asked a number of questions on Math Stack Exchange (MSE) and Code Golf Stack Exchange (CGSE) about these problems.

Openish Problem Collection

I’ve also asked about this setup in my Openish Problem Collection in Problem 41 and in Problem 69.

A series of problems directed related to Project Euler problem #208.
A question about the area enclosed by a robot’s path.

@RobotWalks

Twice each day, my Twitter Bot @RobotWalks tweets a randomly generated Robot Walk cycle. Check out the Github code if you want to see how it works, and read my series on making a Twitter Bot if you want to make something like it for yourself.

Jessica’s Robot Walk Prints

I ordered some canvas prints of some numerologically significant walks for my friend Jessica, which she hung behind her TV. There’s no doubt that this caused her to form a deep mental association between me and The Good Place.

Some prints that I made for my friend Jessica

What’s next?

Some day, I want to laser cut or 3D print some coasters based on these designs. Reach out to me if that’s something that you’re interested in, and we can do it together!

Pour Le Science and the anti-Sum-Product Problem

In March 2021, I got an out-of-the-blue email from OEIS editor Michel Marcus which totally delighted me. He wrote:

This afternoon I went to the library.
And I was browsing “Pour La Science” the French version of the Scientific American.
And here is what I saw.

I like the mysterious tone.

He included this photo of an excerpt of an article, which on the first line mentioned an OEIS sequence of mine (with my name slightly misspelled):

Michel Marcus’s photo of an article in Pour La Science. (Translated below)

The article, translated

Michel had sent me a snippet of the article “Addition et multiplication, des tables qui intriguent” by French Computer Science professor Jean-Paul Delahaye. I read French quite clumsily, so I sent it to my friend Alec, and he volunteered a translation.

Sloane [verb not pictured] of my sequence A337655, Peter Kagey, who must have been informed of changes to the encyclopedia, proposed this second way of accounting for addition and multiplication. This has yielded a new entry in the encyclopedia, the following A337946:

1, 3, 7, 12, 22, 30, 47, 61, 85, 113, 126, 177, 193, 246, 279, 321, 341, 428, 499, 571, 616, 686, 754, 854, 975, 1052, 1150, 1317, 1376, 1457, …

Impossible Little Tables

Let’s consider the fourth question. The response is negative this time: no, it’s not possible that the tables of addition and multiplication have simultaneously only a few distinct values. This is a result of Paul Erdős and Endre Szemerédi from 1983, which we state precisely here:

“There exist two constants \(C>0\) and \(e > 0\) such that, for the set \(E\) of real numbers of […]

Translation by Alec Jones

A Sum-Product Problem

The article—or at least the part that I could make sense of—is about the opposite of Erdos’s Sum-Product Problem. This article explores questions about the greatest number of different values in the corresponding addition and multiplication tables for different sequences of positive integers.

Addition table for the first six terms of A005282, the lexicographically earliest infinite sequence with the maximum-sum property.
Multiplication table for the first six terms of A066720, the lexicographically earliest infinite sequence with the maximum-property property.

Jean-Paul’s sequence, A337655, is the lexicographically earliest (greedy) sequence such that for all \(n\) both the addition and multiplication tables of the first \(n\) terms have \(\binom{n+1}{2}\) distinct terms (the greatest number).

Addition table for A337655.
Multiplication table for A337655.

The addition and multiplication tables share some values. For example, they both have a \(2\), a \(4\), a \(7\), a \(10\), and so on. My sequence, A337946, is similar to Jean-Paul’s but with the additional restriction that the addition and multiplication tables cannot have any values in common.

Addition table for A337946.
Multiplication table for A337946.

Some related sequences

I’ve recently added some new sequences to the OEIS related to these sequences.

One way of thinking of A066720 is that it’s the lexicographically earliest infinite sequence \(S = \(a_i\)_{i=1}^{\infty}\) such that for all \(n\) the set \(S_n = \{a_i\}_{i=1}^{n}\) consisting of the first \(n\) terms of \(S\) has the property that \(S_n \times S_n = \{xy \mid x, y \in S_n\}\) has exactly \(\binom{n+1}{2}\) elements—the most possible.

A347498: minimize the largest term

If instead of minimizing the lexicographic order, we instead minimize the size of the largest element, we get OEIS sequence A347498: for each \(n\), find the least \(m\) such that there exists a subset \(T_n \subseteq \{1, 2, \dots, m\}\) with \(n\) elements such that \(|T_n \times T_n| = \binom{n+1}{2}\). \(A347498(n)\) records the value of the \(m\)s.

For example, \(A347498(8) = 11\) as illustrated by the table below.

Multiplication table illustrating \(A347498(8) = 11\).

A347499: Examples with minimized largest element

We wish to record examples of the sequences described in the above section. There are \(A348481(n)\) subsets of \(\{1,2,…,A347499(n)\}\) with the distinct product property, but we record the lexicographically earliest one in OEIS sequence A347499.

 n | Distinct product subset of {1,2,...,A347499(n)}
---+-------------------------------------------------------
 1 | {1}
 2 | {1, 2}
 3 | {1, 2, 3}
 4 | {1, 2, 3, 5}
 5 | {1, 3, 4, 5,  6}
 6 | {1, 3, 4, 5,  6,  7}
 7 | {1, 2, 5, 6,  7,  8,  9}
 8 | {1, 2, 5, 6,  7,  8,  9, 11}
 9 | {1, 2, 5, 6,  7,  8,  9, 11, 13}
10 | {1, 2, 5, 7,  8,  9, 11, 12, 13, 15}
11 | {1, 2, 5, 7,  8,  9, 11, 12, 13, 15, 17}
12 | {1, 2, 5, 7,  8,  9, 11, 12, 13, 15, 17, 19}
13 | {1, 5, 6, 7,  9, 11, 13, 14, 15, 16, 17, 19, 20}
14 | {1, 2, 5, 7, 11, 12, 13, 16, 17, 18, 19, 20, 21, 23} 

For all of the known values, the lexicographically earliest subset begins with \(1\). Is this true in general?

A347570: Sums with more terms

Perhaps instead of asking when all sums \(x + y\) are distinct for \(x \leq y\), we want to know when all sums \(x_1 + x_2 + \dots + x_n\) are distinct for \(x_1 \leq x_2\leq \dots \leq x_n\). This family of sequences are sometimes called \(B_n\) sequences and have been studied by the likes of Richard Guy.

I’ve recorded the lexicographically earliest \(B_n\) sequences in OEIS sequence A347570.

n\k | 1  2   3   4    5     6     7      8
----+------------------------------------------
  1 | 1, 2,  3,  4,   5,    6,    7,     8, ...
  2 | 1, 2,  4,  8,  13,   21,   31,    45, ...
  3 | 1, 2,  5, 14,  33,   72,  125,   219, ...
  4 | 1, 2,  6, 22,  56,  154,  369,   857, ...
  5 | 1, 2,  7, 32, 109,  367,  927,  2287, ...
  6 | 1, 2,  8, 44, 155,  669, 2215,  6877, ...
  7 | 1, 2,  9, 58, 257, 1154, 4182, 14181, ...
  8 | 1, 2, 10, 74, 334, 1823, 8044, 28297, ... 

I ask about this family of sequences in a recent question on Code Golf Stack Exchange.

Other ideas?

Did this post spark any related ideas? Let me know about them on Twitter @PeterKagey—I’d love to hear about them!

Zimin Words and Bifixes

One of the earliest contributions to the On-Line Encyclopedia of Integer Sequences (OEIS) was a family sequences counting the number of words that begin (or don’t begin) with a palindrome:

  • Let \(f_k(n)\) be the number of strings of length \(n\) over a \(k\)-letter alphabet that begin with a nontrivial palindrome” for various values of \(k\).
  • Let \(g_k(n)\) be the number of strings of length n over a \(k\)-letter alphabet that do not begin with a nontrivial palindrome.
  • Number of binary strings of length \(n\) that begin with an odd-length palindrome. (A254128)

(If I had known better, I would have published fewer sequences in favor of a table, and I would have requested contiguous blocks of A-numbers.)

I must have written some Python code to compute some small terms of this sequence, and I knew that \(g_k(n) = k^n – f_k(n)\), but I remember being at in my friend Q’s bedroom when the recursion hit me for \(f_k(n)\): $$f_k(n) = kf_k(n-1) + k^{\lceil n/2 \rceil} – f_k\big(\lceil \frac n 2 \rceil \big)$$

“Bifix-free” words

One sequence that I didn’t add to the OEIS was the “Number of binary strings of length n that begin with an even-length palindrome”—that’s because this was already in the Encyclopedia under a different name:

A094536: Number of binary words of length n that are not “bifix-free”.

0, 0, 2, 4, 10, 20, 44, 88, 182, 364, 740, 1480, 2980, 5960, …

A “bifix” is a shared prefix and suffix, so a “bifix-free” word is one such that all prefixes are different from all suffixes. More concretely, if the word is \(\alpha_1\alpha_2 \dots \alpha_n\), then \((\alpha_1, \alpha_2, \dots, \alpha_k) \neq (\alpha_{n-k+1},\alpha_{n-k+2},\dots,\alpha_n)\) for all \(k \geq 1\).

The reason why the number of binary words of length \(n\) that begin with an even length palindrome is equal to the number of binary words of length \(n\) that have a bifix is because we have a bijection between the two sets. In particular, find the shortest palindromic prefix, cut it in half, and stick the first half at the end of the word, backward. I’ve asked for a better bijection on Math Stack Exchange, so if you have any ideas, please share them with me!

In 2019–2020, Daniel Gabric, Jeffrey Shallit wrote a paper closely related to this called Borders, Palindrome Prefixes, and Square Prefixes.

Zimin words

A Zimin word can be defined recursively, but I think it’s most suggestive to see some examples:

  • \(Z_1 = A\)
  • \(Z_2 = ABA\)
  • \(Z_3 = ABACABA\)
  • \(Z_4 = ABACABADABACABA\)
  • \(Z_n = Z_{n-1} X Z_{n-1}\)

All Zimin words \(Z_n\) are examples of “unavoidable patterns”, because every sufficiently long string with letters in any finite alphabet contains a substring that matches the \(Z_n\) pattern.

For example the word \(0100010010111000100111000111001\) contains a substring that matches the Zimin word \(Z_3\). Namely, let \(A = 100\), \(B = 0\), and \(C = 1011\), visualized here with each \(A\) emboldened: \( 0(\mathbf{100}\,0\,\mathbf{100}\,1011\,\mathbf{100}\,0\,\mathbf{100})111000111001\).

Binary solo from Bret at 1:26.

I’ve written a Ruby script that generates a random string of length 29 and uses a regular expression to find the first instance of a substring matching the pattern \(Z_3 = ABACABA\). You can run it on TIO, the impressive (and free!) tool from Dennis Mitchell.

# Randomly generates a binary string of length 29.
random_string = 29.times.map { [0,1].sample }.join("")
p random_string
# Finds the first Zimin word ABACABA
p random_string.scan(/(.+)(.+)\1(.+)\1\2\1/)[0]
# Pattern:             A   B   A C   A B A

Why 29? Because all binary words of length 29 contain the pattern \(Z_3 = ABACABA\). However, Joshua Cooper and Danny Rorabaugh’s paper provides 48 words of length 28 that avoid that pattern (these and their reversals):

1100000010010011011011111100
1100000010010011111101101100
1100000010101100110011111100
1100000010101111110011001100
1100000011001100101011111100
1100000011001100111111010100
1100000011011010010011111100
1100000011011011111100100100
1100000011111100100101101100
1100000011111100110011010100
1100000011111101010011001100
1100000011111101101100100100

1100100100000011011011111100
1100100100000011111101101100
1100100101101100000011111100
1100110011000000101011111100
1100110011000000111111010100
1100110011010100000011111100
1101010000001100110011111100
1101010000001111110011001100
1101010011001100000011111100
1101101100000010010011111100
1101101100000011111100100100
1101101100100100000011111100

The Zimin Word \(Z_2 = ABA\) and Bifixes

The number of Zimin words of length \(n\) that match the pattern ABA is equal to the number of of words that begin with an odd-length palindrome. Analogously, the number of words with a bifix is equal to the number of words that begin with an even-length palindrome. The number of these agree when \(n\) is odd.

I’ve added OEIS sequences A342510A342512 which relate to how numbers viewed as binary strings avoid—or fail to avoid—Zimin words. I asked users to implement this on Code Golf Stack Exchange.

Richard Guy’s Partition Sequence

Neil Sloane is the founder of the On-Line Encyclopedia of Integer Sequences (OEIS). Every year or so, he gives a talk at Rutgers in which he discusses some of his favorite recent sequences. In 2017, he spent some time talking about a 1971 letter that he got from Richard Guy, and some questions that went along with it. In response to the talk, I investigated the letter and was able to sort out Richard’s 45-year-old idea, and correct and compute some more terms of his sequence.

Richard Guy and his sequences

Richard Guy was a remarkable mathematician who lived to the remarkable age of 103 years, 5 months, and 9 days! His life was filled with friendships and collaborations with many of the giants of recreational math: folks like John Conway, Paul Erdős, Martin Gardner, Donald Knuth, and Neil Sloane. But what I love most about Richard is how much joy and wonder he found in math. (Well, that and his life-long infatuation with his wife Louise.)

Richard guy mountaineering at age 98 with a photo of his late wife, Louise.

[I’m] an amateur [mathematician], I mean I’m not a professional mathematician. I’m an amateur in the more genuine sense of the word in that I love mathematics and I would like everybody in the world to like mathematics.

Richard Guy in Fascinating Mathematical People: Interviews and Memoirs

Richard’s letter to Neil

In January 2017, Neil Sloane gave a talk at Doron Zeilberger’s Experimental Mathematics Seminar, and about six minutes in, Neil discusses a letter that Richard sent to him at Cornell—which was the forwarded to Bell Labs—in June 1971.

Richard Guy’s 1971 letter to Neil Sloane.

When I was working on the book, the 1973 Handbook of Integer Sequences, I would get letters from Richard Guy from all over the world. As he traveled around, he would collect sequences and send them to me.

Neil Sloane, Rutgers Experimental Mathematics Seminar

At 11:30, Neil discusses “sequence I” from Richard’s letter, which he added to the OEIS as sequence A279197:

Number of self-conjugate inseparable solutions of \(X + Y = 2Z\) (integer, disjoint triples from \(\{1,2,3,\dots,3n\}\)).

Neil mentioned in the seminar that he didn’t really know exactly what the definition meant. With some sleuthing and programming, I was able to make sense of the definition, write a Haskell program, correct the 7th term, and extend the sequence by a bit. The solutions for \(A279197(1)\) through \(A279197(10)\) are listed in a file I uploaded to the OEIS, and Fausto A. C. Cariboni was able to extend the sequence even further, submitting terms \(A279197(11)\)–\(A279197(17)\).

How the sequence works.

The idea here is to partition \(\{1,2,3,\dots,3n\}\) into length-3 arithmetic progressions, \(\bigl\{\{X_i,Z_i,Y_i\}\bigr\}_{i=1}^{n}\). And in particular, we want them to be inseparable and self-conjugate.

An inseparable partition is one whose “smallest” subsets are not a solution for a smaller case. For example, if \(n=3\), then the partition \[\bigl\{ \{1,3,5\}, \{2,4,6\}, \{7,8,9\} \bigr\}\] is separable, because if the subset \(\bigl\{ \{1,3,5\}, \{2,4,6\} \bigr\}\) is a solution to the \(n=2\) case.

A self-conjugate partition is one in which swapping each \(i\) with each \(3n+1-i\) gets back to what we started with. For example, \(\bigl\{\{1,3,5\}, \{2,4,6\}\bigr\}\) is self-congugate, because if we replace the \(1\) with a \(6\) and the \(2\) with a \(5\), and the \(i\) with a \(7-i\), then we get the same set: \(\bigl\{\{6,4,2\}, \{5,3,1\} \bigr\}\)

(1,3,5),  (2,7,12), (4,9,14),  (6,8,10),  (11,13,15)
(1,3,5),  (2,8,14), (4,7,10),  (6,9,12),  (11,13,15)
(1,5,9),  (2,3,4),  (6,8,10),  (7,11,15), (12,13,14)
(1,5,9),  (2,4,6),  (3,8,13),  (7,11,15), (10,12,14)
(1,6,11), (2,3,4),  (5,10,15), (7,8,9),   (12,13,14)
(1,6,11), (2,7,12), (3,8,13),  (4,9,14),  (5,10,15)
(1,7,13), (2,4,6),  (3,9,15),  (5,8,11),  (10,12,14)
(1,7,13), (2,8,14), (3,9,15),  (4,5,6),   (10,11,12)
(1,8,15), (2,3,4),  (5,6,7),   (9,10,11), (12,13,14)
(1,8,15), (2,4,6),  (3,5,7),   (9,11,13), (10,12,14)
(1,8,15), (2,4,6),  (3,7,11),  (5,9,13),  (10,12,14)
Each line shows one of the \(A279197(5) = 11\) inseparable, self-conjugate partitions of \(\{1,2,\dots,15\}\).

Generalizing Richard Guy’s idea

Of course, it’s natural to wonder about the separable solutions, or what happens if the self-conjugate restriction is dropped. In exploring these cases, I found four cases already in the OEIS, and I computed five more: A282615A282619.

SeparableInseparableEither
Self-conjugateA282615A279197 A282616
Non-self-conjugateA282618A282617 A282619
EitherA279199A202705 A104429
Table of sequences counting the ways of partitioning a set into length-3 arithmetic progressions, subject to various restrictions.

Generalizing further

There are lots of other generalizations that might be interesting to explore. Here’s a quick list:

  • Look at partitions of \(\{1,2,\dots,kn\}\) into \(n\) parts, all of which are an arithmetic sequence of length \(k\).
  • Count partitions of \(\{1,2,\dots,n\}\) into any number of parts of (un)equal size in a way that is (non-)self-conjugate and/or (in)separable.
  • Consider at partitions of \(\{1,2,\dots,3n\}\) into \(n\) parts, all of which are an arithmetic sequence of length \(3\), and whose diagram is “non-crossing”, that is, none of the line segments overlap anywhere. (See the 6th and 11th cases in the example for \(A279197(6) = 11\).)

If explore any generalizations of this problem on your own, if you’d like to explore together, or if you have an anecdotes about Richard Guy that you’d like to share, let me know on Twitter!

Polytopes with Lattice Coordinates

Problems 21, 66, and 116 in my Open Problem Collection concern polytopes with lattice coordinates—that is, polygons, polyhedra, or higher-dimensional analogs with vertices the square or triangular grids. (In higher dimensions, I’m most interested in the \(n\)-dimensional integer lattice and the \(n\)-simplex honeycomb).

The \(A334581(4) = 84\) ways to place an equilateral triangle on the tetrahedral grid with four points per side.
Illustration showing three of the \(\binom{7+2}{4} = 126\) equilateral triangles on a grid with seven points per side.

This was largely inspired by one of my favorite mathematical facts: given a triangular grid with \(n\) points per side, you can find exactly \(\binom{n+2}{4}\) equilateral triangles with vertices on the grid. However, it turns out that there isn’t a similarly nice polynomial description of tetrahedra in a tetrahedron or of triangles in a tetrahedron. (Thanks to Anders Kaseorg for his Rust program that computed the number of triangles in all tetrahedra with 1000 or fewer points per side.)

The \(4\)-simplex (the \(4\)-dimensional analog of a triangle or tetrahedron) with \(n-1\) points per side, has a total of \(\binom{n+2}{4}\) points, so there is some correspondence between points in some \(4\)-dimensional polytope, and triangles in the triangular grid. This extends to other analogs of this problem: the number of squares in the square grid is the same as the number of points in a \(4\)-dimensional pyramid.

The \(\binom{n+2}{4}\) equilateral triangles

I put a Javascript applet on my webpage that illustrates a bijection between size-\(4\) subsets of \(n+2\) objects and triangles in the \(n\)-points-per-side grid. You can choose different subsets and see the resulting triangles. (The applet does not work on mobile.)

The solid blue triangle corresponding to the subset \(\{4,5,8,15\} \subseteq \{1,2,\dots,16\}\).
The two smaller numbers in the subset give the size and orientation of the blue triangle, and the two larger numbers give the position.

Polygons with vertices in \(\mathbb{Z}^n\)

This was also inspired by Mathologer video “What does this prove? Some of the most gorgeous visual ‘shrink’ proofs ever invented”, where Burkard Polster visually illustrates that the only regular polygons with vertices in \(\mathbb{Z}^n\) (and thus the \(n\)-simplex honeycomb) are equilateral triangles, squares, and regular hexagons.

Polyhedra with vertices in \(\mathbb{Z}^3\)

There are some surprising examples of polyhedra in the grid, including cubes with no faces parallel to the \(xy\)-, \(xz\)-, or \(yz\)-planes.

An example of a cube from Ionascu and Obando: the convex hull of \(\{(0,3,2),(1,1,4),(2,2,0),(2,5,3),(3,0,2),(3,3,5),(4,4,1),(5,2,3)\}\)

While there are lots of polytopes that can be written with vertices in \(\mathbb{Z}^3\), Alaska resident and friend RavenclawPrefect cleverly uses Legendre’s three-square theorem to prove that there’s no way to write the uniform triangular prism this way! However, he provides a cute embedding in \(\mathbb{Z}^5\): the convex hull of $$\scriptsize{\{(0,0,1,0,0),(0,1,0,0,0),(1,0,0,0,0),(0,0,1,1,1),(0,1,0,1,1),(1,0,0,1,1)}\}.$$

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

If you have any ideas about this, let me know on Twitter or post an answer to the Stack Exchange question above.

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.

  Square Rectangular Centered Square Triangular Centered Hexagonal
Equilateral Triangle A000332 A008893
Square A002415 A130684 A006324
Regular Hexagon A011779 A000537
Regular Polygon A002415 A130684 A006324  ? A339483*
Triangle A045996 A334705  ?  ? A241223
Rectangle A085582 A289832  ?
Right Triangle A077435  ?  ?  ? A241225
OEIS sequences for polygons on 2-dimensional grids.
Sequences marked with “*” are ones that I’ve authored, cells marked with “—” have no polygons, and cells marked with “?” do not have a corresponding sequence that I know of.
CubicTetrahedralOctahedral
Equilateral TriangleA102698A334581* A342353*
SquareA334881*A334891* ?
Regular HexagonA338322* ? ?
Regular PolygonA338323* ? ?
Triangle ? ? ?
Rectangle ? ? ?
Right Triangle ? ? ?
Regular TetrahedronA103158A269747 ?
CubeA098928 ? ?
OctahedronA178797 ? ?
Platonic SolidA338791 ? ?
OEIS sequences for polytopes on 3-dimensional grids.
Sequences marked with “*” are ones that I’ve authored, and cells marked with “?” do not have a corresponding sequence that I know of.

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.

A048152 Parity Bitmap
A048152 parity bitmap, rescaled through Lospec’s Pixel Art Scaler.
A207409 parity bitmap
A207409 parity bitmap.

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

A279212 parity bitmap
512 rows and 256 columns of A279212.
A279212 parity bitmap
2048 rows and 1024 columns of A279212.

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

Animation of A279212 construction

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

A132439 parity bitmap.
A301851 parity bitmap.
A334017 parity bitmap.
A237620 parity bitmap.

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

Alec’s fractal, framed above his fountain pen ink and tasteful books.

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!

Animated GIF of rotating LEGO stack
One of the 102,981,504 ways to stack six 2×4 LEGOs into a tower of height six.

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.
An tower that violates rule 1.
A tower that violates rule 2.
A tower that violates rule 3.
A tower that violates rule 4.

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.

A surprising example of an unstable tower.
See Figure 5 of the Paterson, Peres, Thorup, Winkler, and Zwick paper.

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