On an unrelated note, check out Arrow by half-alive, one of the best songs ever.

Just for simplification, instead of the arrow symbol, I will use the ^ symbol, so 3^^8 = 3↑↑8. If you see 3^^{4}5, please don’t freak out.

Up-arrow notation is a hyperoperation devised by Donald Knuth in 1976. a^^{n}b can be defined with three simple properties:

a^b = a^{b}

a^^{n}1 = a (for n > 1)

a^^{n}b = a^^{n-1}(a^^{n}(b-1)) (for n > 1, b > 1)

Let’s go over them, one by one.

First property: pretty simple. With one up arrow, it’s just exponentiation.

Second property: still simple. If b = 1, a^^{n}b = a, as long as n > 1.

Third property: actually simple if you understand the basics. Donald Knuth stated that, for a^^…^^b with n ^’s, it is equivalent to a^^{n-1}(a^^{n-1}(a^^{n-1}(…^^{n-1}(a^^{n-1}a)…))) with b a’s. Using a form of recursion, the third property can be reformed into the statement that Donald Knuth proposed.

What are some examples of up-arrow notations?

Let’s do the first example: 2^^3. That’s 2^2^2, and it’s not (2^2)^2, and it’s 2^(2^2). 2^2 = 2^{2} = 4, and 2^4 = 2^{4} = 16. The second: 3^^^3, which is also familiar, isn’t it? We went over it in the Graham’s Number post. With 3^^^3, that’s 3^^(3^^3), which is already huge. 3^^3 = 3^{33} = 3^27 = 7625597484987, or 7.6 trillion. For the outer double arrow, that’s 3^3^3^3^…^3^3^3 with 7.6 trillion 3’s.

Yeah. It’s big.

In fact, the function n^^{n}n is larger than all primitive-recursive functions, which… I have no idea.

That’s detail.

My third Favourites post is coming soon, and I will see you then.