Base-k Arrow Notation

python code

def hyper(a, b, c): # a^^...(c ^s)...^b
  if c<1: return a*b
  if b<2: return a
  return hyper(a, hyper(a, b-1, c), c-1)

def R(n, k1, k2): # replace k1 to k2 in base-k1 arrow notation of n
  if n<k1*k1:
    return n//k1*k2+n%k1
  b=2; c=1
  while hyper(k1, b, c+1) <= n: c += 1
  while hyper(k1, b+1, c) <= n: b += 1
  return hyper(k2, b, R(c, k1, k2)) + R(n - hyper(k1, b, c), k1, k2)

def G(n, b=3): # Goodstein function using base-k arrow notation
  if n < 1: return b
  return G(R(n, b, b+1)-1, b+1)

Proof (sketch) that G(n) is well-difined

For a "structure" $s$ of base-k arrow notation, a corresponding ordinal $O(s)$ can be defined by replacing:

• $1$ with $\omega$
• $k$ with $\omega^2$
• $k\uparrow ^{s'}c$ with $\omega ^{O(s')+c}$

Example

base-3 arrow notation of 390: $3\uparrow ^{2}2\times 12+3\uparrow ^{1}2\times 2+3\times 2+2$

corresponding ordinal: $\omega ^{\omega 2+2}12+\omega ^{\omega 1+2}2+\omega ^{2}2+\omega 2$

If $R(n,k_{1},k_{2})$ preserve the structure of the notation, the corresponding ordinal decreases in each step of G(n)