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!

A π-estimating Twitter bot: Part III

In the final part of this three-part series, I’ll give technical step-by-step instructions for how to wire up our Twitter bot, @BotfonsNeedles, to Docker and deploy it on the free tier of AWS Lambda, so that it can run until the end of time. I’ll also include some tips that I wish I knew when I got started.

If you’d like to make a Twitter bot, but find this guide intimidating, you can fork the repository and follow the README on the GitHub page for my other bot, @oeisTriangles. Or better yet, I would love to set up a call and walk you through it step-by-step! Just let me know on Twitter.

The plan

And in this final part, we will

  • build and run a Docker image so that you can run it on a local server,
  • push the Docker image up to Amazon Elastic Container Registry (ECR),
  • hook up the Docker image to an AWS Lambda function, and
  • configure the function to run on a timer in perpetuity.
My Twitter bot, @RobotWalks, deployed using the techniques in this article.
My Twitter bot, @xorTriangles, which posts every 12 hours via AWS Lambda.

Turn it into a Docker image

Next, we’ll package this up in a Docker image so that AWS Lambda has everything that it needs to run this function. Begin by downloading Docker if you don’t already have it installed.

Next, we’re going to add a new file called Dockerfile from an AWS base image for Python, which will look like this.

FROM amazon/aws-lambda-python:3.8

RUN pip install tweepy
RUN pip install Pillow -t .

COPY random_needle.py ./
COPY needle_drawer.py ./
COPY secrets.py ./
COPY twitter_accessor.py ./
COPY tweet_builder.py ./
COPY app.py ./

CMD ["app.handler"]
  • The FROM line says that we’re going to use an Amazon Linux box that has been pre-configured to have Python 3.8.
  • The RUN lines help us to install the Python libraries that we need.
  • The COPY lines say to move the corresponding files from the local directory to the current directory (./) of the Linux box.
  • The CMD line says that when you talk to the server, it should respond with the handler function from the app.py file.

Building a Docker image

Now, we’re going to build the Docker image. Make sure you’re in the proper directory and name the bot botfons-needles (or something else you’d like) by running the following command in the directory containing your Dockerfile:

docker build -t botfons-needles .

This command will probably take a while to run. It’s downloading everything to make a little Linux box that can run Python 3.8, and doing some additional tasks as specified by your Dockerfile. Once this process is done, set up a local server (on port 9000) for the bot where you can test it out by running

docker run -p 9000:8080 botfons-needles

In order to test your code, run the following cURL command in a new terminal:

curl -XPOST "http://localhost:9000/2015-03-31/functions/function/invocations" -d '{}'

If everything works, you’re ready to move on to the next step. More likely, something is a little off, and you’ll want to stop the server, and rebuild the image. To do this, find the name of the local server with

docker container ls

which will return a CONTAINER ID such as bb81431991sb. You can use this ID to stop the container, remove the container, and remove the image.

$ docker stop bb81431991sb
$ docker rm bb81431991sb
$ docker image rm botfons-needles

Then make your changes, and start again from the docker build step.

My first Twitter bot, @oeisTriangles. Read about this in my blog post, “Parity Bitmaps from the OEIS“.

Push to Amazon ECR

In this step, we’ll push our Docker image up to Amazon. So go to Amazon ECR, log in or create an account, navigate to the ECR console, and select “Create repository” in the upper right-hand corner.

This will bring up a place for you to create a repository name.

Now once there’s a repository available, we’re ready to push our local copy up. Start by downloading the AWS Command Line Interface and logging in to AWS. Notice that there are *two* references to the server location (us-east-1) and one reference to your account number (123456789).

aws ecr get-login-password --region us-east-1 \
| docker login --username AWS \
  --password-stdin 123456789.dkr.ecr.us-east-1.amazonaws.com

Now all you need to do is tag your docker image and push it up. Get your Docker image ID with docker image ls, and (supposing it’s 1111111111), tag it with the following command (again, making sure to specify the right server location and account number):

docker tag 1111111111 123456789.dkr.ecr.us-east-1.amazonaws.com/botfons-needles

Now you’re ready to push! Simply change 123456789 to your account number and us-east-1 to your server location in the following command and run it:

docker push 123456789.dkr.ecr.us-east-1.amazonaws.com/botfons-needles

Hook up to AWS Lambda

Now you’re ready to wire this up to a AWS Lambda function! Start by going to the AWS Lambda console and click “Create function”

To create a function from the AWS Lambda console, click “Create function” in the upper right-hand corner.

This will take you to a page where you’ll want to select the third option “Container image” at the top, give your function a name (e.g. myTwitterBot) and select the Container image URI by clicking “Browse images” and selecting the Docker image you pushed up.

Search for the image you just pushed up, choose the latest tag, and “Select image”.

Then the dialog will go away, and you can click “Create function”, after which your function will start to build—although it may take a while!

Next, you’ll want to test your function to make sure that it’s able to post to Twitter properly!

With the default RAM and time limit, it’s likely to time out. If the only thing that you’re using AWS for is posting this Twitter bot, then it doesn’t hurt to go to the “Configuration” tab and increase the memory and timeout under “General configuration”. (I usually increase Memory to 1024 MB and Timeout to 15 seconds, which has always been more than enough for me.)

Increase memory to 1024 MB and timeout to 15 seconds.

Run it on a timer

If things are running smoothly, then all that’s left to do is to set up a trigger. Do this by selecting “Triggers” in the “Configuration” tab, clicking “Add Trigger”, selecting “EventBridge (CloudWatch Events)”, and making a new rule with schedule expression rate(12 hours).

That’s it! AWS Lambda should trigger your bot on the interval you specified!

There’s only one step left: send me a message or tag me on Twitter @PeterKagey so that I can follow your new bot!

A π-estimating Twitter bot: Part II

This is the second part of a three part series about making the Twitter bot @BotfonsNeedles. Click here for Part I.

In this 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 𝜋.

In the next 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

Get access to the Twitter API

When I made my first Twitter bot, I followed the article “How to Make a Twitter Bot With Python“.

In order to have your Python code post to your Twitter feed, you’ll need to register for a Twitter developer account, which you can do by going to https://developer.twitter.com/ and clicking apply. You’ll need to link the account to a phone number and fill out a few minutes of forms. For all four of my bots, (@oeisTriangles, @xorTriangles, @RobotWalks, and this bot) I’ve been approved right away.

Keep in mind that you can only use your phone number on two Twitter accounts—so you’ll have to use a Google Voice number or something else if you want to make more than two bots.

Once you’re approved, go to the Developer Portal, click on the Projects & Apps Overview, and click on the blue “+ New Project” button. You will be given a series of short questions, but what you submit isn’t too important.

Create a new project by clicking “+ New Project” via the Projects & Apps overview

Getting the API Keys

Once you’ve filled out the form, you should be sent to a page with an API Key and API Secret Key. This is essentially the password to your account, so don’t share these values.

A screenshot showing a (fake) API Key and API Secret Key.

We’re going to take these values and place them in a new file called secrets.py, which will look like this:

API_KEY        = "3x4MP1e4P1kEy"
API_SECRET_KEY = "5Ecr3TK3Y3x4MP1e4P1kEytH150nEi510nG"

Getting the Access Token

Once we close the API Key dialog, we’ll need to update our app to allow us to both read and write. We can do this by clicking on the gear to access our projects “App settings”.

Click the gear to access the settings.

Once you’re in, you’ll want to edit the App permissions to “Read and Write”.

Click “Edit” to update from “Read Only” to “Read and Write”.

Then go to the “Keys and Tokens” page (which you can do by clicking the key icon from the app settings page), and generate an Access Token and Secret.

Click “Generate” to make an access token and secret.

When you click “Generate” you should get an Access Token and a Access Token Secret, which you need to add to your secrets.py file.

Thus your secrets.py file should contain four lines:

API_KEY             = "3x4MP1e4P1kEy"
API_SECRET_KEY      = "5Ecr3TK3Y3x4MP1e4P1kEytH150nEi510nG"
ACCESS_TOKEN        = "202104251234567890-exTrAacC3551Nf0"
ACCESS_TOKEN_SECRET = "5eCr3t0KEnGibB3r15h"

hello_twitter.py

Next, we’ll hook this up to the Twitter API via tweepy, which I’ll install in the terminal using pip:

$ pip3 install tweepy

And make a file called twitter_accessor.py that looks exactly like this:

from secrets import *
import tweepy

class TwitterAccessor:
  def __init__(self):
    auth = tweepy.OAuthHandler(API_KEY, API_SECRET_KEY)
    auth.set_access_token(ACCESS_TOKEN, ACCESS_TOKEN_SECRET)
    self.api = tweepy.API(auth)

  def read_last_tweet(self):
    timeline = self.api.user_timeline(count=1, exclude_replies=True, tweet_mode='extended')
    return timeline[0].full_text

Next, we’ll check that everything is working by making a file called hello_twitter.py:

from twitter_accessor import TwitterAccessor

new_status = "Hello Twitter!"
TwitterAccessor().api.update_status(new_status)
print("Posted status: '" + new_status + "'")

Run it via the command line:

$ python3 hello_twitter.py

If something looks broken, try to fix it. (If it’s broken because of something I’ve said, let me know.)

Reading and writing Tweets

Now you can delete your hello_twitter.py file, because we’re about to do this for real! In part 3, we’re going to wire this up to AWS Lambda, which has certain preferences for how we structure things. With this in mind, I’d recommend following my naming conventions, unless you have a reason not to.

Each Tweet should have copy that looks like this:

This trial dropped 100 needles, 59 of which crossed a line. This estimates π ≈ 2*(100/59) ≈ 3.38, an error of 7.90%.

In total, 374 of 600 needles have crossed a line.
This estimates π ≈ 3.20, an error of 2.13%.

BotfonsNeedles should parse the “374 of 600”, throw 100 more needles, and report on the updated estimate of \(\pi\).

An implementation

I’ve made a file called tweet_builder.py, with five functions:

  • pi_digits_difference takes an estimate of \(\pi\) and outputs an appropriate length string. For example, if the estimate is \(3.14192919\), then it will output "3.14192", which are all of the correct digits, plus the first two that are wrong. If the estimate is \(3.20523\), then it will output “3.20".
  • error_estimate takes an estimate of \(\pi\) and computes the right number of digits to show in its percent error. For example, if the estimate is \(3.20523\) (which is \(2.0256396\%\) too big) then it will output "2.02%".
  • get_running_estimate uses the API in TwitterAccessor to look up the last tweet—then throws some needles, and outputs both the total number of needles tossed and the total number of needles that cross a line.
  • tweet_copy takes the information from get_running_estimate, formats it with pi_digits_distance and error_estimate and writes the text for the tweet.
  • post_tweet uses the API in TwitterAccessor to send the tweet to Twitter, with an image to match.

Most of these implementations are just details which can be found on Github, but I want to highlight post_tweet, the function that is likely to be the most relevant to you.

def post_tweet(self):
  file_name = self.drawer.draw_image()
  copy = self.tweet_copy()
  self.accessor.api.update_with_media(filename=file_name, status=copy)
  return copy

What’s next

In Part III, we’ll get this running in a Docker container and have it run on AWS Lambda.

If you want to get a head start, make a file called app.py with a function called handler, which AWS Lambda will call. This function should return a string, which will get logged.

from tweet_builder import TweetBuilder

def handler(event, context):
  return TweetBuilder().post_tweet()

As usual, if you have any questions or ideas, there’s nothing I love more than collaborating. If you want help getting your bot off the ground, ask me about it on Twitter, @PeterKagey!

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!

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

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.