
Hello! I’m Peter!
Blog
-
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 MemoirsRichard’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 SeminarAt 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.
Separable Inseparable Either Self-conjugate A282615 A279197 A282616 Non-self-conjugate A282618 A282617 A282619 Either A279199 A202705 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
- In Part I of this series, we wrote the Python code that outputs Tweets (with images) for @BotfonsNeedles.
- In Part II of this series, we got a Twitter API key and hooked it up to the program with Tweepy.
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 thehandler
function from theapp.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 yourDockerfile
: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 port9000
) for the bot where you can test it out by runningdocker 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 asbb81431991sb
. 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’s1111111111
), 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 andus-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 inTwitterAccessor
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 fromget_running_estimate
, formats it withpi_digits_distance
anderror_estimate
and writes the text for the tweet.post_tweet
uses the API inTwitterAccessor
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 calledhandler
, 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!