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^45, please don’t freak out.
Up-arrow notation is a hyperoperation devised by Donald Knuth in 1976. a^nb can be defined with three simple properties:
- a^b = ab
- a^n1 = a (for n > 1)
- a^nb = 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^nb = 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-1a)…))) 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 = 22 = 4, and 2^4 = 24 = 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 = 333 = 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^nn is larger than all primitive-recursive functions, which… I have no idea.
My third Favourites post is coming soon, and I will see you then.