Descending Dungeon Numbers in J

Neil Sloane of the On-Line Encyclopedia of Integer Sequences has graced us with another appearance on Numberphile. In this video he discusses the sequence of “descending dungeon” numbers, their origins, how to construct them, and why they’re interesting.

I suggest you watch the video for a full explanation, but as a quick introduction, the sequence of descending dungeon numbers are generated by repeatedly reinterpreting a number as if it were written in a higher and higher base.

The sequence begins at 10. From there, we interpret 10 as if it were written in base 11, which gives us 11 in decimal (11 * 1 + 11 * 0). The next number in the sequence is 11 interpreted in base 12, or 13 (12 * 1 + 12 * 1). 13 is followed by 16. 16 is followed by 20, and so on.

Let’s try our hand at modeling the descending dungeon using the J programming language.

At the heart of our descending dungeon is the interpretation a number in a given base. J’s “base” verb (#.) lets us do just this, assuming our number is split into a list of its digits:

So it looks like we’re already half way there! Now we need a way of splitting a number into its component digits so we can feed it into #.. It turns out that we can do this using the inverse of the base verb, #.inv or #.:_1:


   10 #.inv 10
1 0
   10 #.inv 11
1 1
   10 #.inv 13
1 3
   10 #.inv 16
1 6

Great! We can now write a verb that accepts our current descending dungeon number and the next base to interpret it in, and spits our the next descending dungeon number in our sequence:


   11 (#.10&#.inv) 10
11
   12 (#.10&#.inv) 11
13
   13 (#.10&#.inv) 13
16
   14 (#.10&#.inv) 16
20

We’ll probably want to flip the order of our arguments to make it more ergonomic to feed in our list of bases, and reduce down to our sequence values:


   10 (#.10&#.inv)~ 11
11
   11 (#.10&#.inv)~ 12
13
   13 (#.10&#.inv)~ 13
16
   16 (#.10&#.inv)~ 14
20

With that change, we can easily “insert” (/) our verb between each element of our list of bases, and come up with the descending dungeon number at that point in the sequence:


   (#.10&#.inv)~/ 10
10
   (#.10&#.inv)~/ 10 11
11
   (#.10&#.inv)~/ 10 11 12
13
   (#.10&#.inv)~/ 10 11 12 13
16

We can “infix” (\) this verb to apply it to all successive parts of our list to build our our full list of descending dungeon numbers:


   (#.10&#.inv)~/\ 10 11 12 13
10 11 13 16

Now all that’s left is to clean up how we build our list of bases and plot our descent into the dungeon:


   plot (#.10&#.inv)~/\ 10 + i. 20

The video asks the question, “how quickly do these numbers grow?” The answer seems to be “very slowly, and then very quickly.” But where does that shift happen? The numbers of the sequence that we’ve seen so far seem to be increasing by a linearly increasing amount.

10 + 1 is 11. 11 + 2 is 13. 13 + 3 is 16. 16 + 4 is 20, and so on…

Let’s use J to calculate the difference between successive numbers in our descending dungeons sequence:


   sequence =: (#.10&#.inv)~/\ 10 + i. 20
   2(-~/;._3) sequence
1 2 3 4 5 6 7 8 9 10 22 48 104 224 480 1024 2176 4608 9728

We can look at this as the discrete derivative of our sequence, or the difference between each successive element. We can see that for the first ten steps into our descending dungeon, this delta increases linearly. However once we get to the eleventh step, things go off the rails.

So it seems like we can stand by our answer and definitively say that the descending dungeons sequence grows “very slowly, and then very quickly.” Good work, everyone. Mystery solved.

Overall, this was an interesting exercise in exploring numerical bases, and a fun excuse to practice our J skills. Here’s hoping Neil Sloane stars in another Numberphile video very soon!