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.

My Favorite Sequences: A263135

This is the fourth in my installment of My Favorite Sequences. This post discusses sequence A263135 which counts penny-to-penny connections among \(n\) pennies on the vertices of a hexagonal grid. I published this sequence in October 2015 when I was thinking about hexagonal-grid analogs to the “Not Equal” grid. The square-grid analog of this sequence is A123663.

A263135: Placing Pennies

The sequences A047932 and A263135 are about placing pennies on a hexagonal grid in such a way that maximizes the number of penny-to-penny contacts, which occurs when you place the pennies in a spiral. A047932, counts the contacts when the pennies are placed on the faces of the grid; A263135 counts the contacts with the pennies placed on the vertices.

Pattern of placing pennies in A047932.
Pattern of placing pennies in A263135.

While spiral shapes maximize the number of penny-to-penny contacts, there are sometimes non-spiral shapes that have the same number of contacts. For example, in the case of the square grid, there are \(A100092(n)\) such ways to lay down \(n\) pennies on the square grid with the maximum number of connections. Problem 108 in my Open Problems Collection asks about generalizing this OEIS sequence to other settings such as the hexagonal grid.

A047932(11) = 21
A263135(22) = 27

Comparing contacts

Notice that the “face” pennies in A047932 can have a maximum of six neighbors, while the “vertex” pennies in A263135 can have a maximum of three. In the limit, most pennies are “interior” pennies with the maximum number of contacts, so \(A047932(n) \sim 3n\) and \(A263135(n) \sim \frac32n\).

Looking at the comparative growth rates, it is natural to ask how the number of connections of \(n\) face pennies compares to the number of connections of \(2n\) vertex pennies. In October 2015 I made a conjecture on the OEIS that this difference grew like sequence A216256.

Conjecture: For \(n > 0\), \[A263135(2n) – A047932(n) = \lceil\sqrt{3n – 3/4} – 1/2\rceil = A216256(n).\]

I believe that the sequence A216256 on the right hand side appears to be the same as the sequence “n appears \(\displaystyle\left\lfloor \frac{2n+1}{3} \right\rfloor\) times,” but I’d have to crack open my Concrete Mathematics book to prove it.

This is Problem 20 in my Open Problem Collection, and I’ve placed a small, $5 bounty on solving this conjecture—so if you have an idea of how to prove this, let me know in exchange for a latte! I’ve asked about this in my Math Stack Exchange question Circle-to-circle contacts on the hexagonal grid—so feel free to answer there or let me know on Twitter, @PeterKagey.

My Favorite Sequences: “Not Equal” Grid

This is the third installment in a recurring series, My Favorite Sequences. This post discusses OEIS sequence A278299, a sequence that took over two years to compute enough terms to add to the OEIS with confidence that it was distinct.

This sequence is discussed in Problem #23 of my Open Problems Collection, which asks for the smallest polyomino (by number of cells) whose cells you can color with \(n\) different colors such that any two different colors are adjacent somewhere in the polyomino. As illustrated below, when there are \(n=5\) colors (say, green, brown, blue, purple, and magenta) there is a \(13\)-cell polyomino which has a green cell adjacent to a blue cell and a purple cell adjacent to a brown cell and so on for every color combination. This is the smallest polyomino with the \(5\)-coloring property.

Five colors of blocks, where any two different colors of blocks are adjacent somewhere in the polyomino.

The Genesis: Unequal Chains

The summer after my third undergraduate year, I decided to switch my major to Math and still try to graduate on time. Due to degree requirements, I had to go back and take some lower-division classes that I was a bit over-prepared for. One of these classes—and surely my favorite—was Bill Bogley‘s linear algebra class, where I half-way paid attention and half-way mused about other things.

Bill wrote something simple on the board that sparked inspiration for me: $$a \neq b \neq c \neq a.$$ He wrote this to indicate that \(a\), \(b\), and \(c\) were all distinct, and this got me thinking: if we have to write a string of four variables in order to say that three variables are distinct, how many would we have to write down to say that four variables were distinct? It turns out that \(8\) will do the trick, with one redundancy: $$a\neq b \neq c \neq d \neq b \color{red}{\neq} c \neq a.$$ Five variables? \(11\): $$a_1 \neq a_2 \neq a_3 \neq a_4 \neq a_5 \neq a_3 \neq a_1 \neq a_4 \neq a_2 \neq a_5.$$ What about \(n\) variables?

My colleague and the then-President of the OSU Math Club, Tommy Pitts, made quick work of this problem. He pointed out that “not equal” is a symmetric, non-transitive, non-reflexive relation. This means that we can model this with a complete graph on \(n\) vertices, where each edge is a relation. Then the number of variables needed in the expression is the number of edges in the complete graph, plus the minimum number of Eulerian paths that we can split the graph into. Searching for this in the OEIS yields sequence A053439. $$A053439^*(n) = \begin{cases} \binom{n}{2} + 1 & n \text{ is odd} \\ \binom{n}{2} + \frac n 2 & n \text{ is even}\end{cases}$$

A Generalization: Unequal Chainmail

This was around 2014, at which time I was writing letters to my friend Alec Jones whenever I—rather frequently!—stumbled upon a new math problem that interested me. In the exchange of letters, he suggested a 2D version of this puzzle. Write the \(n\) variables in the square grid, and say that two variables are unequal if they’re adjacent.

While Tommy solved the 1D version of the problem quickly, the 2D version was much more stubborn! However we were able to make some progress. We found some upper bounds (e.g. the 1D solution) and some lower bounds, and we were able to prove that some small configurations were optimal. Finally, in November 2016, we had ten terms: enough to prove that this sequence was not in the OEIS. We added it as A278299.

\(a(n)\) is the tile count of the smallest polyomino with an \(n\)-coloring such that every color is adjacent to every other distinct color at least once.

OEIS sequence A278299.

(In May 2019, Alec’s student Ryan Lee found the \(11\)th term: \(A278299(11) = 34\). \(A278299(12)\) is still unknown.)

A screenshot from my game illustrating the largest known term: \(A278299(14) = 56\). Every number is connected to every other number. The red edges refer to redundant connections.

We found these terms by establishing some lower bounds (as explained below) and then implementing a Javascript game (which you can play here) with a Ruby on Rails backend to allow people to submit their hand-crafted attempts. Each solution was constructive proof of an upper bound, so when a user submitted a solution that matched the lower bound, we were able to confirm that term of the sequence.

(One heuristic for making minimal configurations is to start with the construction in OEIS sequence A260643 and add cells as necessary in an ad hoc fashion.)

Lower bounds

There are a few different ways of proving lower bounds.

  • We know that there needs to be at least \(\binom{n}{2}\) relations, one between each pair of variables. OEIS sequence A123663 gives the “number of shared edges in a spiral of n unit squares,” which can be used to compute a lower bound: $$A039823(n) = \left\lceil \frac{n^2+n+2}{4}\right\rceil$$
  • Every number needs to be in contact with at least (n-1) other numbers, and each occurrence can be in contact with at most (4) others. So each number needs to occur at least \(\lceil \frac{n-1}{4}\rceil\) times, for a total of \(n\lceil \frac{n-1}{4}\rceil\) occurrences. This bound is usually weaker than the above bound.
  • For the cases of \(n = 5\) and \(n=9\), the lower bounds were proved using ad hoc methods, by looking at how many cells would need to have a given number of neighbors.

Upper Bounds

Besides the upper bound that comes from the 1-dimensional version of the problem, that only upper bounds that I know of come from hand-crafted submissions on my Javascript game on my website.

Do you have any ideas for an explicit and efficient algorithm for constructing such solutions? If so, let me know on Twitter @PeterKagey.

Asymptotics

The lower and upper bounds show that this is asymptotically bounded between \(n^2/4\) and \(n^2/2\). It’s possible that this doesn’t have a limit at all, but it would be interesting to bound the liminf and limsup further. My intuition is that \(n^2/4\) is the right answer, can you prove or disprove this?

Generalizations

  • We could play this game on the triangular grid, or in the 3-dimensional cubic grid. Do you have ideas of other graphs that you could do this on?
  • This game came from Tommy’s analysis of looking at “not equal to” as a symmetric, non-reflexive, non-transitive relation. Can you do a similar analysis on other kinds of relations?
  • Is there a good way of defining what it means for two solutions to be the same? For a given number of variables, how many essentially different solutions exist? (Related: Open problem #108.)
  • What if we think of left-right connections as being different from up-down connections, and want both? Or what if we want each variable \(x\) to be neighbors with another \(x\)?

If you have ideas about these questions or any questions of your own, please share them with me by leaving a comment or letting me know on Twitter, @PeterKagey!

My Favorite Sequences: A289523

This the second post in a recurring series, My Favorite Sequences. If you like this sort of thing, check out the Integer Sequence Review from The Aperiodical!

A289523: Packing Circles of Increasing Area

A plot of the circles in A289523.

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?

A scatter plot of A289523.

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.

An animation illustrating successive generations of circles on a square spiral.

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

An illustration of the first dozen terms of A261865

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

A scatterplot of \(A261865(n)\). Notice the records at \(A261865(184)=38\) and \(A261865(8091)=43\).

A conjecture about density

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.

Let’s denote the asymptotic density of terms that are equal to \(n\) by \(d_n\). It’s easy to check that \(d_1 = 0\), (because multiples of \(\sqrt 1\) are never between any integers) and \(d_2 = 1/\sqrt 2\), because multiples of \(\sqrt 2\) are always inserted. I conjecture in Problem 13 of my Open Problem Collection that $$a_n = \begin{cases}\displaystyle\frac{1}{\sqrt n}\left(1 – \sum_{i=1}^{n-1} a_i\right) & n \text{ is squarefree}\\[5mm] 0 & \text{otherwise}\end{cases}$$

If this conjecture is true, then the following table gives approximate densities.

\(i\)\(d_i\)
\(1\)\(d_1 = 0\%\)
\(2\)\(d_2 = 70.7\%\)
\(3\)\(d_3 = 16.9\%\)
\(4\)\(d_4 = 0\%\)
\(5\)\(d_5 = 5.54\%\)
\(6\)\(d_6 = 2.79\%\)
\(7\)\(d_7 = 1.53\%\)
\(10\)\(d_{10} = 0.797\%\)
\(11\)\(d_{11} = 0.519\% \)
\(399\)\(d_{399} = 3.53 \times 10^{-11} \%\)

This was computed with the Mathematica code:

d[i_] := (d[i] = If[
  SquareFreeQ[i], 
  N[(1 - Sum[d[j], {j, 2, i - 1}])/Sqrt[i], 50], 
  0
])

Finding Large Values

I’m interested in values of \(n\) such that \(A261865(n)\) is large, and I reckon that there are clever ways to construct these, perhaps by looking at some Diophantine approximations of \(\sqrt{2}, \sqrt{3}, \sqrt{5}, \sqrt{6}, \dots\). In February, I posted a challenge on Code Golf Stack Exchange to have folks compete in writing programs that can quickly find large values of \(A261865(n)\).

Impressively, Noodle9’s C++ program won the challenge. In under a minute, this program found that the input \(n=1001313673399\) makes \(A261865\) particularly large: \(A261865(1001313673399) = 399\). Within the time limit, no other programs could find a value of \(n\) that makes \(A261865(n)\) larger.

\(n\)Order of magnitude\(A261865(n)\)Time
1 \(1 \times 10^{0}\)2(0s)
3 \(3 \times 10^{0}\)3 (0s)
23 \(2.3 \times 10^{1}\)7 (0s)
30 \(3.0 \times 10^{1}\)15 (0s)
184 \(1.84 \times 10^{2}\)38 (0s)
8091 \(8.091 \times 10^{3}\)43 (0s)
16060 \(1.606 \times 10^{4}\)46 (0s)
16907 \(1.691 \times 10^{4}\)58 (0s)
20993 \(2.099 \times 10^{4}\)61 (0s)
26286 \(2.629 \times 10^{4}\)97 (0s)
130375 \(1.304 \times 10^{5}\)118 (0s)
169819 \(1.698 \times 10^{5}\)127 (0s)
2135662 \(2.136 \times 10^{6}\)130 (0s)
2345213 \(2.345 \times 10^{6}\)187 (0s)
46272966 \(4.627 \times 10^{7}\)193 (1s)
222125822 \(2.221 \times 10^{8}\)210 (5.2s)
237941698 \(2.379 \times 10^{8}\)217 (5.7s)
257240414 \(2.572 \times 10^{8}\)227 (6.2s)
1205703469 \(1.206 \times 10^{9}\)267 (31s)
1558293414 \(1.558 \times 10^{9}\)299 (41.8s)
4641799364 \(4.642 \times 10^{9}\)303 (2.1m)
6600656102 \(6.601 \times 10^{9}\)323 (3m)
11145613453 \(1.115 \times 10^{10}\)335 (5.2m)
20641456345 \(2.064 \times 10^{10}\)354 (9.8m)
47964301877 \(4.796 \times 10^{10}\)358 (22.9m)
105991039757 \(1.06 \times 10^{11}\)385 (52m)
119034690206 \(1.19 \times 10^{11}\)397 (59.1m)
734197670865 \(7.342 \times 10^{11}\)455 (6.4h)
931392113477 \(9.314 \times 10^{11}\)501 (8.4h)
1560674332481 \(1.561 \times 10^{12}\)505 (14.2h)
A table of record values as computed by Code Golf Stack Exchange user Neil. The first 16 values agree with Jon E. Schoenfield’s computations that were added to the OEIS in September 2015

Related Ideas

Sequence \(A327953(n)\) counts the number of positive integers \(k\) such that there is some integer \(\alpha^{(n)}_k > 2\) where \(\alpha^{(n)}_k\sqrt{k} \in (n, n+1)\). It appears to grow roughly linearly like \(A327953(n) \sim 1.3n\), but I don’t know how to prove this.

  • Take any function \(f\colon\mathbb N \rightarrow \mathbb R\) that is positive, has positive first derivative, and has negative second derivative. Then, what is the least \(k\) such that some multiple of \(f(k)\) is in \((n,n+1)\)?
  • For example, what is the least integer \(k \geq 3\) such that there is a multiple of \(\ln(k)\) in \((n, n+1)\)?
  • What is the least \(k \in \mathbb N\) such that there exists \(m \in \mathbb N\) with \(k2^{1/m} \in (n,n+1)\)?
  • What is the least \(m \in \mathbb N\) such that there exists \(k \in \mathbb N\) with \(k2^{1/m} \in (n,n+1)\)?
  • A343205 is the auxiliary sequence that gives the value \(m\) such that \(m\sqrt{A261865(n)} \in (n, n+1)\). Does this sequence have an infinite limit inferior?
Scatterplot of A343205, generated in Mathematica. If the main conjecture is true, then this is not bounded below by \(\alpha n\) for any positive value of \(\alpha\).

If you can answer any of these questions, or if you spend time thinking about this, please let me know on Twitter, @PeterKagey!