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++
// C++ code to demonstrate Knuth's Up-Arrow// Notation For Exponentiation#include <bits/stdc++.h>using namespace std;typedef long long int lli;// Function to find valuelli knuth_arrow(int a, int k, int b){ // a (k's ↑) 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));}// Driver codeint main(){ // 5↑4 = 5^4 = 625 cout << knuth_arrow(5, 1, 4) << endl; // 3↑↑3 = 3^(3^3) = 3^27 cout << knuth_arrow(3, 2, 3) << endl; // 2↑↑↑3 = 2↑↑(2↑↑2) = 2↑↑(2^2) = // 2↑↑4 = (2^(2^(2^2))) = 2^16 cout << knuth_arrow(2, 3, 3) << endl; return 0;} |
Java
// Java code to demonstrate Knuth's Up-Arrow// Notation For Exponentiationpublic class GFG { public static long knuth_arrow(int a, int k, long b) { // a (k's ↑) 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)); } // Driver code public static void main(String[] args) { // 5↑4 = 5^4 = 625 System.out.println(knuth_arrow(5, 1, 4)); // 3↑↑3 = 3^(3^3) = 3^27 System.out.println(knuth_arrow(3, 2, 3)); // 2↑↑↑3 = 2↑↑(2↑↑2) = 2↑↑(2^2) = 2↑↑4 = // (2^(2^(2^2))) = 2^16 System.out.println(knuth_arrow(2, 3, 3)); }} |
Python3
# Python code to demonstrate Knuth's Up-Arrow# Notation For Exponentiationdef knuth_arrow(a, k, b): # a (k's ↑) b if b == 0: return 1 if k == 1: return a**b return knuth_arrow(a, k-1, knuth_arrow(a, k, b-1))# 5↑4 = 5 ^ 4 = 625print(knuth_arrow(5, 1, 4))# 3↑↑3 = 3^(3 ^ 3) = 3 ^ 27print(knuth_arrow(3, 2, 3))# 2↑↑↑3 = 2↑↑(2↑↑2) = 2↑↑(2 ^ 2) = 2↑↑4 =# (2^(2^(2 ^ 2))) = 2 ^ 16print(knuth_arrow(2, 3, 3)) |
C#
// C# code to demonstrate Knuth's Up-Arrow// Notation For Exponentiationusing System;public class GFG { // Function to find value private static long knuth_arrow(int a, int k, long b) { // a (k's ↑) 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)); } // Driver code static public void Main(string[] args) { // 5↑4 = 5^4 = 625 Console.WriteLine(knuth_arrow(5, 1, 4)); // 3↑↑3 = 3^(3^3) = 3^27 Console.WriteLine(knuth_arrow(3, 2, 3)); // 2↑↑↑3 = 2↑↑(2↑↑2) = 2↑↑(2^2) = // 2↑↑4 = (2^(2^(2^2))) = 2^16 Console.WriteLine(knuth_arrow(2, 3, 3)); Console.ReadKey(); }}// This Code is Contributed by Prasad Kandekar(prasad264) |
Javascript
function 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));}// 5↑4 = 5 ^ 4 = 625console.log(knuth_arrow(5, 1, 4));// 3↑↑3 = 3^(3 ^ 3) = 3 ^ 27console.log(knuth_arrow(3, 2, 3));// 2↑↑↑3 = 2↑↑(2↑↑2) = 2↑↑(2 ^ 2) = 2↑↑4 =// (2^(2^(2 ^ 2))) = 2 ^ 16console.log(knuth_arrow(2, 3, 3)); |
Output
625 7625597484987 65536
Time Complexity: O(K*b)
Auxiliary Space: O(K*b)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
