Add this to the list of bizarre things you can do in Ruby:

class Object
  def new
    Class.new
  end
end

p Class.new.new.new.new.new.new.new.new.new.new.new

# prints "#<Class:0x401bf9dc>"

The other day on a train I was investigating the different ways that numbers can be represented using an “extended binary” when I happened upon an interesting sequence.

Extended binary has the same values for the digits (2⁰, 2¹, 2², 2³…), but instead of allowing only coefficients of 0 and 1, we allow any natural number. So the number 6 can be represented in any of the following ways:

• 1·2² + 1·2¹
• 1·2² + 2·2⁰
• 3·2¹
• 2·2¹ + 2·2⁰
• 1·2¹ + 4·2⁰

So the number six has five representations. If we count the number of representations for each number, starting with 0, we get the following sequence:

1, 1, 2, 2, 3, 3, 5, 5, 7, 7, 10, 10, 13, 13, 18, 18, 23, 23, 30, 30, 37, 37, 47, 47, 57, 57, …

The first thing I do when analyzing a sequence is to look at the differences between the successive numbers. In this case every number repeats, but if we remove the repeats, like so:

1, 2, 3, 5, 7, 10, 13, 18, 23, 30, 37, 47, 57, …

And then take the difference between each of these numbers, we get:

1, 1, 2, 2, 3, 3, 5, 5, 7, 7, 10, 10, …

Sloane’s has it as A040039, with the subtitle:

First differences of A033485; also A033485 with terms repeated.

There’s a way to describe prime numbers without mentioning divisibility (or multiplication, division, or any arithmetic at all actually) that I suspect might be easier to digest for people who aren’t the least bit thrilled by number theory.

We just need one preliminary concept. Consider an arrangement of objects into identical rows forming a rectangular grid, like this:

We’ll call it a rectangle as long as all of its sides are at least two objects long. This should all be pretty intuitive.

Note that in the previous example there are 35 objects in total. We could get this by multiplying, but if we’re trying not to use arithmetic, we could also get it by counting. So because we have a rectangle with 35 objects in it, we’ll say that 35 must be a rectangular number. All it means for a number to be rectangular is that if you have that particular number of objects, you can arrange them into a rectangle somehow. Because the rectangles must have sides at least 2, the smallest rectangular number must be 4:

Having now defined ‘rectangular number’ in terms that I optimistically suspect a preschooler could understand, we can get prime numbers with just this:

A prime number is any number greater than one that is not rectangular.

This is a negative definition for sure, but we can make it constructive by turning it into a method for showing a number is prime. This is as simple as checking all possible rectangle-shapes (or row-lengths). For example, to show that 37 is a prime, we look at what happens when we try to make a rectangle with every possible row length:

There’s always something leftover. So to be prime is to completely escape all attempts at rectangularization. I think it’s fascinating to consider very large primes, for which there would be millions, trillions, or however arbitrarily many plausible row sizes to make a rectangle from, and none of them work.

My last post where I introduced the idea of maximally irregular graphs ended with a question — can there be two distinct (non-isomorphic) maximally irregular graphs of the same order? I had found this not to be the case up to order 9, but of course we can’t be sure that there aren’t any without a formal proof.

Within minutes of publishing the first post, I started getting ideas of how such a proof might go, but I didn’t have the opportunity and the will to formalize it until just recently.

First a lemma to simplify a bit. For a graph of n nodes containing all degrees from 1 to (n-1), there will always be one duplicate degree, and I didn’t specify in my definition which degree it might be. So the first thing we should note is that, for orders greater than 3, it can’t be of degree (n-1) OR of degree 1. It can’t be of degree (n-1), because that would mean there are two vertices connected to every other vertex, which demands that every vertex have degree at least 2, which precludes the existence of a vertex of degree 1, which we require. The duplicate can’t be of degree 1 either, because then there are two vertices that are only connected to the one vertex of maximal degree, which precludes the existence of a vertex of degree (n-2), which must necessarily be connected to all but one vertex. So for a large enough graph (> 3 vertices, so that 1≠(n-2)), there will be one unique vertex of degree (n-1), and one unique vertex of degree 1.

Having established that, we can outline the proof. The proof will be one of infinite descent, which will create a contradiction when combined with our observation that only one maximally irregular graph exists for each order less than ten. So given two distinct graphs of order n, we will construct two distinct graphs of order (n-2).

So we assume the existence of two non-isomorphic graphs on n vertices, G and H. Then we construct G’ and H’ by taking the induced subgraph that results from removing the vertices of degree 1 and (n-1) from each graph. All we have to show is that G’ and H’ are maximally irregular for order (n-2), and that they cannot be isomorphic.

To show that they are maximally irregular, consider what happens to the remaining vertices when the largest and smallest degree vertices are removed, as in the example order-15 graph below:

The degree-1 vertex was only connected to the degree-(n-1) vertex, and so its removal does not change the degrees of any of the remaining vertices. The degree-(n-1) vertex, however, was connected to every remaining vertex, and so removing it will decrement the degree of every remaining vertex. So this subset of vertices in the original graph had degrees in the range [2,(n-2)], and so decrementing each of them gives vertices of degrees [1,(n-3)], which is exactly the requirements for a maximally irregular graph of order (n-2).

All that remains is to show that G’ and H’ cannot be isomorphic. We can do this by contradiction — if G’ and H’ are isomorphic, then we can show that G and H must be isomorphic as well, contradicting our original assumption that they are distinct. To show this, let us assume we have a bijection between the vertices of G’ and H’ — I claim that if we use this same bijection for G and H, adding that the vertices of degree (n-1) are mapped to each other and the vertices of degree 1 are mapped to each other, that it will be an isomorphism. This should be obvious once we note that for the degree (n-1) vertices, all other vertices are connected to them, so they are trivially equivalent; and for the degree-1 vertices, they are only connected to the degree (n-1) vertices, which are mapped to each other. So the connections between the two graphs are preserved.

And that’s it. Given any two distinct maximally irregular graphs of the same order, we can produce two smaller distinct maximally irregular graphs by removing two vertices from each graph. This process can be repeated as many times as necessary to produce two distinct maximally irregular graphs of order less than or equal to nine, and we have searched exhaustively to be sure that these do not exist. Therefore, for every order >= 2, there is one unique maximally irregular graph, so we can speak of the maximally irregular graph for any given order.

As a reward for anybody who actually read this far, I supply images of the maximally irregular graphs on 25, 50, 75, and 100 nodes.