How do you calculate 3^3^3^3? (What algo / struct?)

12577936...00739387 (1.2577936e+3638334640024) # Wolfram - 12580142...00739387 (3638334640025 digits) 

import math class BigInt: """BigInt gives integer approximation and easy to read strings""" _first = "" _last = "" _length = None # BigInt  val: int = None # actual int, if applicable  def __init__(self, val: int = 0) -> None: """BigInt gives integer approximation and easy to read strings Args: val (int | BigInt, optional): Defaults to 0. """ self.set(val) def set(self, val: int): """Update large integer with int or BigInt Args: val (int | BigInt): integer to update Returns: BigInt: returns self """ if isinstance(val, BigInt): self.val = val.val if val.val is None: self._first = val._first self._last = val._last self._length = val._length return else: self.val = val try: float(self.val) except OverflowError: self._first = self.first self._last = self.last self._length = None self.val = None return self @property def first(self) -> str: """ Returns: str: initial part of BigInt """ if self._first: return self._first if not self.val: return "" return str(self.val)[:8] @property def last(self) -> str: """ Returns: str: ending part of BigInt. """ if self._last: return self._last if not self.val: return "" return str(self.val)[-8:] @property def length(self): """ Returns: BigInt | None: length of BigInt, as another BigInt, if applicable """ if self._length: return self._length if not self.val: return None return BigInt(len(str(self.val))) def __repr__(self) -> str: if not self.val or self.val > 10 ** 16: s = "" if self.last: s = f"{self.first}...{self.last}" e = "" if self.length: m = "" if self.first: m = self.first[0] if len(self.first) > 1: m += "." + self.first[1:] e = f"{m}e+{self.length}" if s: if e: return f"{s} ({e})" return s return e return f"{self.val}" class Tower(BigInt): """Exponent tower, of 3 by default""" k: int base: int def __init__(self, k: int, base: int = 3) -> None: """Exponent tower, of 3 by default Args: k (int): Number of bases in the tower base (int, optional): Defaults to 3. """ self.k = k self.base = base super().__init__(base) prev = BigInt(1) def up_pow(m: int) -> None: out = BigInt() if self.val: try: float(base) ** self.val self.set(base ** self.val) return except OverflowError: pass log = self.val * math.log10(base) fl = math.floor(log) r = log - fl out._first = f"{(10 ** r):.7f}".replace(".", "") if r > 0 else "" out._length = BigInt(fl) elif prev.val: loglog = prev.val * math.log10(base) + math.log10(math.log10(base)) fl = math.floor(loglog) r = loglog - fl length = BigInt() length._first = f"{(10 ** r):.7f}".replace(".", "") if r > 0 else "" length._length = BigInt(fl) out._length = length out._last = tetmod_digits(int(BigInt(base).last), m) out.val = None self.set(out) for m in range(2, k + 1): next_prev = BigInt(self) up_pow(m) prev = next_prev def modpow(base: int, exp: int, mod: int) -> int: """Modular exponentiation Adapted from https://en.wikipedia.org/wiki/Modular_exponentiation#Implementation_in_Lua ``` py (base ** exp) % mod ``` Args: base (int): exp (int): mod (int): Returns: int: """ r = 1 base = base % mod while exp: if exp % 2: r = (r * base) % mod exp = exp // 2 base = (base ** 2) % mod return r def modpow_digits(base: int, exp: int, digits: int = 8) -> str: """Last digits of exponentiation ``` py (base ** exp) % (10 ** digits) # With frontmost "0" padding ``` Args: base (int): exp (int): digits (int, optional): Defaults to 8. Returns: str: string of digits, representing n last digits """ mod = 10 ** digits return str(modpow(base, exp, mod)).rjust(digits, "0") def tetmod(base: int, k: int, mod: int) -> int: """Tetration with modulo Adapted from https://math.stackexchange.com/a/4225702/958918 ``` py (base ↑↑↑ k) % mod ``` Args: base (int): k (int): mod (int): Returns: int: """ if k == 1: return base % mod elif k == 2: return modpow(base, base, mod) phi = euler_phi(mod) return modpow(base, phi + tetmod(base, k - 1, phi) % phi, mod) def tetmod_digits(base: int, k: int, digits: int = 8) -> str: """Last digits of tetration ``` py (base ↑↑↑ k) % (10 ** digits) # With frontmost "0" padding ``` Args: base (int): k (int): digits (int, optional): Defaults to 8. Returns: str: string of digits, representing n last digits """ mod = 10 ** digits return str(tetmod(base, k, mod)).rjust(digits, "0") def euler_phi(n: int) -> int: """Euler's Phi From https://www.geeksforgeeks.org/eulers-totient-function/ Args: n (int): Returns: int: the count (number) of coprimes less than n """ # Initialize result as n  result = n # Consider all prime factors  # of n and subtract their  # multiples from result  p = 2 while p * p <= n: # Check if p is a  # prime factor.  if n % p == 0: # If yes, then  # update n and result  while n % p == 0: n = int(n / p) result -= int(result / p) p += 1 # If n has a prime factor  # greater than sqrt(n)  # (There can be at-most  # one such prime factor)  if n > 1: result -= int(result / n) return result if __name__ == "__main__": for n in range(2, 6 + 1): print("-", n, Tower(n))