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:
625 7625597484987 65536
Time Complexity: O(K)
Auxiliary Space: O(K)