Subscribe Bookmark



Jun 23, 2011

Graph makeover: Fractal scatterplot

One of the marvels of the Internet is the Online Encyclopedia of Integer Sequences (OEIS). Started 50 years ago by Neil J. A. Sloane (pic) as a graduate student, the repository now contains more than 256,000 integer sequences run by a non-profit OEIS Foundation with Sloane still at the helm. (Aside: I wanted to donate $1,000 to the foundation so I could have my name next to Donald Knuth's on the short list of $1,000 donors, but my wife provided a voice of reason as usual.)

Why do we need an encyclopedia of integer sequences? If your study produces a sequence of integers, you can use the encyclopedia to see what the next term is or what else is known about the sequence. For (a contrived) example, if you're counting carbon trees and get counts of 4, then 9, then 18, then 42 trees when you add more and more atoms, you can look up "4, 9, 18, 42" in the OEIS and find sequence A000678, which has more information and even a formula.

For the 50th anniversary, the foundation produced a poster featuring nine visually interesting sequences. One, A229037 the greedy sequence with no three equally-spaced items forming an arithmetic sequence, was this scatterplot:


The graph was automatically generated by the website, and the interesting aspect is that the sequence appears to have a fractal structure in this space in that each cluster of points is a larger version of a previous cluster. However, there are two artifacts of the graph that obscure that information. There is serious over-striking of points, especially at the low end. Also, the clusters appear to get more sparse just because the spacing is growing, but the dots are staying the same size. As an attempt to remedy those artifacts, I made a version with translucent and variably-sized dots.


I think it's easy to see the fractal structure now. When I shared it with Sloane, he promptly added it to the sequence's web page and plans to update the poster as well. By the way, this sequence has a graphical explanation that hints at why it has a graphical structure: No three points in the scatterplot fall along the same line with equal spacing.

I'll leave you with a puzzle involving another sequence from the poster A250001. It's the number of ways to arrange n circles, ignoring size and not allowing single-point intersections. This image from the poster shows 7 of the 14 ways of arranging 3 circles. Can you find the other 7? There are 168 ways of arranging 4 circles, and no one knows how many ways there are to arrange 5 or more circles.


1 Comment
Community Member

Rick Wicklin wrote:

Regarding the arrangements of circles, you might find it interesting that the ways to arrange n circles so that they do not intersect is related to Hilbert's 16th problem, which can be summarized by the statement "what are the possible topologies of real algebraic varieties (level sets of polynomials of degree d)?" The intersecting cases are transition states (critical level states) where one topological type merges into another as a coefficient of the polynomial varies.