## DEV Community is a community of 758,269 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Discussion on: How do you calculate 3^3^3^3? (What algo / struct?)

Pacharapol Withayasakpunt

I made it, but I could get the first digits right (according to WolframAlpha).

``````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

```

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

```

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))
``````