Up arrow and down arrow notation

I recently ran into a tweet saying that if ** denotes exponentiation then // should denote logarithm. With this notation, for example, if we say

 3**4 == 81

we would also say

 81 // 3 == 4.

This runs counter to convention since // has come to be a comment marker or a notation for integer division. I assume the original proposal was meant to be funny, or at most semi-serious, but it would have made sense had notation developed that way.

Donald Knuth's arrow notation for hyperexponentiation works that way. An up arrow denotes repeated exponentiation and a down arrow denotes repeated logarithm.

Up arrow notation

One up arrow denotes repeated multiplication, i.e. exponentiation.

Two up arrows denote repeated exponentiation, i.e. hyperexponentiation.

Three up arrows denotes repeated applications of double arrow, etc.

Here's how you could calculate

using Python:

 def hyperexp(b, k, n): if n == 0: return 1 if k == 1: return b**n return hyperexp(b, k-1, hyperexp(b, k, n-1))

This function grows shockingly quickly. The first four values of hyperexp(2, 2, n) starting with n=1 are 2, 4, 16, and 65536. But the fifth value has over 19,000 digits.

Up arrow notation comes up sometimes, for example, in analysis of algorithms.

Down arrow notation

The downarrow notation is less common, and a little more complicated.

The logarithm of a number x base b is the number of times you'd need to multiply b by itself to get x. So if down arrow is the inverse of up arrow, down arrow is logarithm.

Now what should two down arrows represent? It should be the inverse of down up arrows. For example,

and so we should have

That means the double down arrow counts how many times you have to use up arrows to get from 4 to 65536. But notice we're counting things. We're assuming there are an integer number of times you can apply up arrows to define the down arrows. In general you can't do that. What if we change 65536 to 65535 above?

So here's where there's a slight complication, an asymmetry between up arrow and down arrow notation. Repeated up arrows count the number of times you have to apply down arrows to get something less than or equal to the base. See MathWorld, for example.

Seems like down arrow notation might be useful in number theory where iterated logs are common. (There's a joke that asks what sound a number theorist makes when drowning. Answer: log log log ".)

Related posts

• Big-O and related notation
• Four uncommon but handy notations
• Prime factors, phone numbers, and the normal distribution