Tag Archives: Math

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 A342510–A342512 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: 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!

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: A282615–A282619.

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!

A π-estimating Twitter bot: Part I

This is the first part of a three part series about making the Twitter bot @BotfonsNeedles. In this part, I will write a Python 3 program that

In the second part, I’ll explain how to use the Twitter API to

  • post the images to Twitter via the Python library Tweepy, and
  • keep track of all of the Tweets to get an increasingly accurate estimate of \(\pi\).

In the third part, I’ll explain how to

  • Package all of this code up into a Docker container
  • Push the Docker image to Amazon Web Services (AWS)
  • Set up a function on AWS Lambda to run the code on a timer
An example of dropping 100 needles in Buffon’s needle problem. Needles that cross a vertical line are colored red.

Buffon’s needle problem

Buffon’s needle problem is a surprising way of computing \(\pi\). It says that if you throw \(n\) needles of length \(\ell\) randomly onto a floor that has parallel lines that are a distance of \(\ell\) apart, then the expected number of needles that cross a line is \(\frac{2n}\pi\). Therefore one way to approximate (\pi) is to divide \(2n\) by the number of needles that cross a line.

I had my computer simulate 400 needle tosses, and 258 of them crossed a line. Thus this experiment approximates \(\pi \approx 2\!\left(\frac{400}{258}\right) \approx 3.101\), about a 1.3% error from the true value.

63/100 needles cross a vertical line; approximates \(\pi \approx 200/63 \approx 3.174\).
61/100 needles cross a vertical line; approximates \(\pi \approx 200/61 \approx 3.279\).
68/100 needles cross a vertical line; approximates \(\pi \approx 200/68 \approx 2.941\).
66/100 needles cross a vertical line; approximates \(\pi \approx 200/66 \approx 3.030\).

Modeling in Python

Our goal is to write a Python program that can simulate tossing needles on the floor both numerically (e.g. “258 of 400 needles crossed a line”) and graphically (i.e. creates the PNG images like in the above example).

The RandomNeedle class.

We’ll start by defining a RandomNeedle class which takes

  • a canvas_width, \(w\);
  • a canvas_height, \(h\);
  • and a line_spacing, \(\ell\).

It then initializes by choosing a random angle (\theta \in [0,\pi]) and random placement for the center of the needle in \[(x,y) \in \left[\frac{\ell}{2}, w -\,\frac{\ell}{2}\right] \times \left[\frac{\ell}{2}, h -\,\frac{\ell}{2}\right]\] in order to avoid issues with boundary conditions.

Next, it uses the angle and some plane geometry to compute the endpoints of the needle: \[\begin{bmatrix}x\\y\end{bmatrix} \pm \frac{\ell}{2}\begin{bmatrix}\cos(\theta)\\ \sin(\theta)\end{bmatrix}.\]

The class’s first method is crosses_line, which checks to see that the \(x\)-values at either end of the needle are in different “sections”. Since we know that the parallel lines occur at all multiples of \(\ell\), we can just check that \[\left\lfloor\frac{x_\text{start}}{\ell}\right\rfloor \neq \left\lfloor\frac{x_\text{end}}{\ell}\right\rfloor.\]

The class’s second method is draw which takes a drawing_context via Pillow and simply draws a line.

import math
import random

class RandomNeedle:
  def __init__(self, canvas_width, canvas_height, line_spacing):
    theta = random.random()*math.pi
    half_needle = line_spacing//2
    self.x = random.randint(half_needle, canvas_width-half_needle)
    self.y = random.randint(half_needle, canvas_height-half_needle)
    self.del_x = half_needle * math.cos(theta)
    self.del_y = half_needle * math.sin(theta)
    self.spacing = line_spacing

  def crosses_line(self):
    initial_sector = (self.x - self.del_x)//self.spacing
    terminal_sector = (self.x + self.del_x)//self.spacing
    return abs(initial_sector - terminal_sector) == 1

  def draw(self, drawing_context):
    color = "red" if self.crosses_line() else "grey"
    initial_point  = (self.x-self.del_x, self.y-self.del_y)
    terminal_point = (self.x+self.del_x, self.y+self.del_y)
    drawing_context.line([initial_point, terminal_point], color, 10)

By generating \(100\,000\) instances of the RandomNeedle class, and keeping a running estimation of (\pi) based on what percentage of the needles cross the line, you get a plot like the following:

This estimates \(\pi\approx 2\left(\frac{10000}{63681}\right) \approx 3.1407\) an error of 0.03%.

The NeedleDrawer class

The NeedleDrawer class is all about running these simulations and drawing pictures of them. In order to draw the images, we use the Python library Pillow which I installed by running

pip3 install Pillow

When an instance of the NeedleDrawer class is initialized, makes a “floor” and “tosses” 100 needles (by creating 100 instances of the RandomNeedle class).

The main function in this class is draw_image, which makes a \(4096 \times 2048\) pixel canvas, draws the vertical lines, then draws each of the RandomNeedle instances.

(It saves the files to the /tmp directory in root because that’s the only place we can write file to our Docker instance on AWS Lambda, which will be a step in part 2 of this series.)

from PIL import Image, ImageDraw
from random_needle import RandomNeedle

class NeedleDrawer:
  def __init__(self):
    self.width   = 4096
    self.height  = 2048
    self.spacing = 256
    self.random_needles = self.toss_needles(100)

  def draw_vertical_lines(self):
    for x in range(self.spacing, self.width, self.spacing):
      self.drawing_context.line([(x,0),(x,self.height)],width=10, fill="black")

  def toss_needles(self, count):
    return [RandomNeedle(self.width, self.height, self.spacing) for _ in range(count)]
 
  def draw_needles(self):
    for needle in self.random_needles:
      needle.draw(self.drawing_context)

  def count_needles(self):
    cross_count = sum(1 for n in self.random_needles if n.crosses_line())
    return (cross_count, len(self.random_needles))

  def draw_image(self):
    img = Image.new("RGB", (self.width, self.height), (255,255,255))
    self.drawing_context = ImageDraw.Draw(img)
    self.draw_vertical_lines()
    self.draw_needles()
    del self.drawing_context
    img.save("/tmp/needle_drop.png")
    return self.count_needles()

Next Steps

In the next part of this series, we’re going to add a new class that uses the Twitter API to post needle-drop experiments to Twitter. In the final part of the series, we’ll wire this up to AWS Lambda to post to Twitter on a timer.

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!

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

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.

A photo of the canvas print
The original image

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.

An example of a hexagonal Truchet tiling. Cameron Browne would call this particular example a Palago “creature“, which are counted by Arnauld Chevallier‘s brilliant program.

It turns out that if you ignore the colors, the number of ways to pair up midpoints of the sides of a \(2n\)-gon in such a way that the curves connecting the midpoints don’t overlap is given by the \(n\)-th Catalan number. For example, there are \(C_4 = 14\) ways of connecting midpoints of the sides of an octagon, where different rotations are considered distinct.

Two distinct rotations
Eight distinct rotations
Four distinct rotations

There are three regular tilings of the plane by \(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 \(2n\)-gons, results in a really lovely emergent structure.

Square tiling
Truncated square tiling, randomly colored

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.