Select Page

# Knuth’s Up-Arrow Notation For Exponentiation

Team 1 - Programming
Published: February 13, 2023

Knuth’s up-arrow notation, also known as Knuth’s arrow notation, is a mathematical notation for exponentiation that was introduced by Donald Knuth in his book “Concrete Mathematics”. It uses a sequence of up-arrows () to represent exponentiation with various bases and exponents.

Approach: Exponentiation depends on the number of arrows used in the notation. Here is a general approach for each type of exponentiation represented by the up-arrow notation.

• One Arrow (a↑b): For this type of exponentiation, the approach is to multiply the base a by itself b times. This is equivalent to a * a * a * … * a where there are b a‘s. .000000000000000000000000000For Example, 5↑4 is represented as 5↑4 = 5^4 = 625
• Two Arrows (a↑↑b): For this type of exponentiation, the approach is to raise the base a to the power of a b times. This is equivalent to a^(a^(a^(…))) where there are b a‘s inside the parentheses. For Example, 3↑↑4 is represented as 3↑↑3 = 3^(3^3) = 3^27 = 7625597484987.
• Three or More Arrows: For this type of exponentiation, the approach is to perform the exponentiation operation b times, with each exponentiation operation taking the previous result as its base. The first exponentiation is performed using the base a. For Example, 2↑↑↑3 is represented as 2↑↑↑3 = 2↑↑(2↑↑2) = 2↑↑(2^2) = 2↑↑4 = (2^(2^(2^2))) = 2^16 = 65536

Below is the implementation of Knuth’s up-arrow notation:

## C++

 `#include ``using` `namespace` `std;``typedef` `long` `long` `int` `lli;`` ` `lli knuth_arrow(``int` `a, ``int` `k, ``int` `b)``{`` ` `    ``    ``if` `(b == 0)``        ``return` `1;``    ``if` `(k == 1)``        ``return` `pow``(a, b);`` ` `    ``return` `knuth_arrow(a, k - 1, knuth_arrow(a, k, b - 1));``}`` ` `int` `main()``{`` ` `    ``    ``cout << knuth_arrow(5, 1, 4) << endl;`` ` `    ``    ``cout << knuth_arrow(3, 2, 3) << endl;`` ` `    ``    ``    ``cout << knuth_arrow(2, 3, 3) << endl;``    ``return` `0;``}`

## Java

 `public` `class` `GFG {``    ``public` `static` `long` `knuth_arrow(``int` `a, ``int` `k, ``long` `b)``    ``{``        ``        ``if` `(b == ``0``)``            ``return` `1``;``        ``if` `(k == ``1``)``            ``return` `(``long``)Math.pow(a, b);``        ``return` `knuth_arrow(a, k - ``1``,``                           ``knuth_arrow(a, k, b - ``1``));``    ``}`` ` `    ``    ``public` `static` `void` `main(String[] args)``    ``{``        ``        ``System.out.println(knuth_arrow(``5``, ``1``, ``4``));`` ` `        ``        ``System.out.println(knuth_arrow(``3``, ``2``, ``3``));`` ` `        ``        ``        ``System.out.println(knuth_arrow(``2``, ``3``, ``3``));``    ``}``}`

## Python3

 ` ` ` ` `def` `knuth_arrow(a, k, b):``        ``    ``if` `b ``=``=` `0``:``        ``return` `1``    ``if` `k ``=``=` `1``:``        ``return` `a``*``*``b``    ``return` `knuth_arrow(a, k``-``1``, knuth_arrow(a, k, b``-``1``))`` ` ` ` `print``(knuth_arrow(``5``, ``1``, ``4``))`` ` `print``(knuth_arrow(``3``, ``2``, ``3``))`` ` `print``(knuth_arrow(``2``, ``3``, ``3``))`
Output

```625
7625597484987
65536```

Time Complexity: O(K)
Auxiliary Space: O(K)

Source: www.geeksforgeeks.org