This will not be a particularly gratifying math story. We’ll get 83% of the way to a fascinating instance of duality, and then swerve away at the last minute, and we’re left with bupkis.

The story starts with me facetiming my parents on December 13th. December 13th 2020 was the fourth night of Chanukkah, and our plan was to light candles together. I mentioned that my grocery delivery hadn’t included as many candles as I had ordered (Remote holidays? Weird grocery orders? This is the most 2020 story ever, so far…), and so rather than the 44 candles required to make a complete chanukkah’s-worth of candles (9 + 8 + 7 + … + 2, since each of the eight nights takes n candles plus 1 extra, called the shamash), I had only 24.

My mother joked that I could light them in binary:

She is, after all, the STEM teacher who taught me binary in the first place: Sitting in the occasional diner, she’d show me how to exchange the white sweetener packets (0) for the blue ones (1), and construct arbitrarily large integers (depending on the number of packets we could get our hands on).

Certainly binary would use fewer candles than the regular old unary. Over the course of the holiday, you’d use the regular 8 (one shamash for each night), plus the sequence:

1 + 1 + 2 + 1 + 2 + 2 + 3 + 1

In other words, 8 + 13 = 21.

To my parents’ patient amusement, I counted out each night separately:

1   00000001 = 1 candle
2   00000010 = 1 candle
3   00000011 = 2 candles
4   00000100 = 1 candle
5   00000101 = 2 candles
6   00000110 = 2 candles
7   00000111 = 3 candles
8   00001000 = 1 candle

I am not that much fun to facetime with.

But I was a bit peeved that there didn’t seem to be a pattern here: Given the nᵗʰ night of chanukkah, how many candles will you need?

For an arbitrarily long chanukkah, is there a general solution for how many candles you will have used?

Usually these sorts of simple problems have an elegant closed-form solution that jumps out at you if you just enumerate the first few. So I started:

….What…?

From the information here, can you figure out what the ninth night of nonochanukkah would look like? I sure can’t. What about the 111th night of unununikkah?

I’ve had this feeling before…

I had, by some absolutely wild coincidence, had this exact feeling of not knowing what the next sequence number is, only a week prior. (What comes next?) In my actual job I look a lot at “motifs,” or subgraph isomorphism on a large graph. In less scary terms, that just means looking for a small piece of a graph inside a larger graph. For example, here’s a highlighted triangle-motif in a bigger “host” graph:

The problem I had been working on was this.

Imagine you have an infinite grid of nodes in a graph:

Now, pick some number of nodes. Let’s say, n=4. What is the GREATEST number of edges you can use to connect that many nodes?

This is a cool, interesting question (you’ll just have to believe me). Subgraph isomorphism is a super interesting question for all sorts of problems in fields such as pharmaceutical research, route navigation, and — my personal favorite — neuroscience and brain-mapping!

Okay. Want a fun(?) easy (?) at-home activity to keep you busy for a few minutes? Try drawing the grid, and then choosing n nodes so that they have the MOST edges possible. For example, on 4 nodes:

There’s a good guess and a better guess. And below? That’s a BAD guess. If the below picture was your first guess, you should consider maybe practicing your shapes.

If you scan n from 0 to [big number], the maximum number of edges, I found, was the following:

You can actually prove this out pretty easily (albeit slowly) using some simple Python code:

import itertools
import networkx as nx

# A 4x4 grid graph:
G = nx.grid_graph(dim=[4, 4])

N = 4 # the number of nodes to connect

# The largest number of edges in the induced subgraphs of
# all possible four-node subgraphs:
print(max(
    len(G.subgraph(ns).edges())
    for ns in
    [i for i in itertools.combinations(G.nodes(), N)]
))

Again, I’ll note — this is a VERY SLOW way of computing this sequence. (Can you think of a faster one?) This code helpfully lives in a jupyter notebook called Trash.ipynb on my desktop.

Hey! That’s a very weird coincidence: Another set of hard-to-predict numbers, but… The same sequence?? (Maybe they’re not hard to predict for you, but I couldn’t tell you offhand how many edges you can cram into, say, a 20-node subgraph. If you have an answer, message me!!)

So then it follows that in a six-node motif on a grid, you should be able to make a graph with a maximum of (n=7) = 9 edges!

… Wait. That’s not right, that’s only eight edges. Can you find a way to get another edge in?

As it turns out, you shouldn’t spend too much time trying. It’s impossible.

That’s because the sequence of numbers that I had discovered last week was the following:

0, 1, 2, 4, 5, 7, 8, 10, 12, …

But the number of total Chanukkah candles you need for a binary n-night holiday is:

0, 1, 2, 4, 5, 7, 9, 12, 13, …

In other words, they deviate. These are not the same sequence. (I had only been looking at relatively small motifs, and unless I had tried to draw the n=7 case last night, this blog post would have been much shorter and much wronger.)

So why are these sequences so similar??

The answer?

After our call, I hopped over to the Online Encyclopedia of Integer Sequences, and found this sequence:

0, 1, 2, 4, 5, 7, 9, 12, 13, 15, 17, 20, …

Its name? Maximal number of bonds joining n nodes in simple cubic lattice. In other words, the grid lattice from before was CLOSE! But off, and specifically, off by one dimension. Instead of these:

…I had actually needed these:

It is extremely 👏 weird 👏 that I had encountered two mysterious sequences in one week that turned out to be the same sequence. And what do the sums of 1’s in binary numbers have to do with subgraphs on the 3-grid? And, more abstractly, why is three the magical number of dimensions for which this is true? What does the set of binary-to-unary partial sums have to do with ℕ³??

Not the answer

As it turns out, by the 12th night of dodechanukkah, you would have used up 22 candles (plus twelve shamashim), but a 12-node subgraph of the cubic lattice can have only 21 edges.

So the sequences aren’t related after all, despite starting off identically, and having so many initial elements in common!

Therein lies the swerve. Oof. I was so excited to write a cool blog post about chanukkah/motif duality. Bummer!

The real sequence can be found here. It was, for some reason, not the first result in my search.

But I still want to know why, for N-ukkahs of n≤11, you can construct an induced n-node subgraph on the 3D infinite lattice with exactly the number of edges as there are 1’s in binary-n?

I’m telling you, some traditions really make no sense at all.

PS: חנכה, the Hebrew text for “Chanukkah,” has the numerological value of 83, which appears in both sequences. COINCIDENCE?!?!?

UPDATE AS OF DEC 20 2020

After posting this, I got some great feedback:

In an infinite-dimensional lattice, we can pack in n nodes at the binary expansions of 1 through n, gaining exactly the right number of edges for all n (one for each 1 in the binary expansions). Not sure how to prove it's optimal, but it is at least a reason for this pattern.

— sam_ford (@samford32501328) December 16, 2020

Card

There is a connection here, and an intuition to be had!

If you name nodes in your graph by their coordinate, then you might imagine a lattice graph in 3 dimensions has the following nodes:

(0, 0, 0)
(0, 0, 1)
(0, 1, 0)
...

And a graph in 4D:

(0, 0, 0, 0)
(0, 0, 0, 1)
(0, 0, 1, 0)
...

This enables us to draw a direct relationship between a candle in binary (with an ID of 00000000) and a node in any number of dimensions ≤8. In other words, there is a candle called 00000101 that corresponds to the node (1, 0, 1) in the 3D graph and (0, 1, 0, 1) in the 4D graph (and node (0, 0, 0, 0, 0, 1, 0, 1) in the 8D graph).

This means that in a 3D graph, the nodes corresponding to candles 8 and greater (anything that can’t be represented as a neighbor of (0, 0, 0)) require an additional “hop” away from the origin node. In other words, in low dimensions, the subgraphs have to “spread out” faster from the origin.

That’s because the number of neighbors that a node has is a function of the dimensionality of the lattice.

For fear of getting too technical here, this means that these sequences ARE indeed related! But they diverge because we run out of “local” space around our subgraph, for sufficiently high candle ID numbers.

So in order to actually have perfect correspondence between these sequences up to infinity, you’d need to have an infinite-dimensional lattice graph to store your subgraphs in.

Whew!

Thanks @samford32501328 and @Lopsidation for helping me to understand! The internet is a very cool place.

An update on May 1 2021: The brilliant Dr. Neil Sloane recently released a great YouTube video that mentions this sequence — the “binary weight of n” sequence. Check it out!