Integers Sequences in the Footsteps of Giants
A few days ago, Aapeli Vuorinen and I, posted a One on Epsilon blog post about multiplication tables. Creating that post, was one of the most fun experiences I had since getting into recreational mathematics . It even got me to revisit one of my biggest previous life passions — mathematical research.
You see, up until two or three years ago, mathematical research was what I passionately did. It is only recently, that I changed my focus towards education and exposition. Yes, I am still a University academic, but you won’t find me late at night, working on the BRAVO effect, or other aspects of queueing theory which I loved. I rather spend all the time that I can get on One on Epsilon.
The idea of the blog post was simple: look at the numbers in the multiplication table and carry out some statistics about how many of them appear.
Then Aapeli and I spent an evening together creating a simple animation where each spot on the multiplication table is a pixel that is shaded based on how often the number appears on the table. Numbers that appear frequently are light blue and numbers that are rare are darker. Nothing fancy, but fun to watch:
We then naturally asked: As these multiplication tables grow, how many unique numbers appear on the table?
It is quite an interesting question. After all, in an n x n table, you know that there are at most n² numbers that can appear — but clearly not all of them do. For starters, prime numbers greater than n don’t appear. Further, many numbers appear at least twice because the table is symmetric.
So how many numbers do appear? What is the proportion of numbers that appear as n grows large? Does this proportion converge to some constant? Or perhaps it tends to zero?
Out of curiosity, I computed the proportion for large n. A few details are in the One on Epsilon blog post. I also reached out to some fellow colleagues. I just thought it was a neat enough question to have. What happens to that proportion? My curious soul, did not let it go. I enjoyed not knowing. I enjoyed the question. It was sitting in my heart and I wanted to share the joy.
Then, after some communication with colleagues, I decided to look at the sequence:
1, 3, 6, 9, 14, 18, 25, 30, 36, 42, 53, 59,…
This is the sequence of number of unique numbers in the n x n times table. For example, the 10'th number, 42 is for the 10 x 10 table. I then did the obvious thing to do these days….. you guessed it — search the web!
But where? So here is the main take-away from this blog post: I keyed it into The Online Encyclopaedia of Integer Sequences (OEIS).
Try it yourself, copy the numbers above and paste them in the OEIS search field. You’ll get the entry: https://oeis.org/A027424 . It reads: Number of distinct products ij with 1 <= i, j <= n (number of distinct terms in n X n multiplication table). Exactly what I was looking for!
The information on OEIS, associated with this sequence indicated that the great Paul Erdős suggested this problem and had some initial results years ago. It was then considered by more great mathematicians that followed. Alas, my question was asked before — and even answered! The latest complete account is by Kevin Ford.
While my numerical investigation indicates that the sequence perhaps grows quadratically (leading to a non-zero constant for the proportion), the proofs of these great researchers actually show that it grows slightly slower. Hence the proportion roughly behaves like 1/log(n) for large n. It goes to 0 (but slowly).
Now, I am enjoying looking at some of the literature that I was led to via OEIS. If you want to take a quick look, perhaps the most accessible first source to consider is this recent academic presentation, by Richard P. Brent (joint with Carl Pomerance). Don’t stress, if you don’t get all the details. Just enjoy the ride.
I’m humbled by all these giants and the mathematical truths that they discovered. It brings me joy.