Goldstein Numbers

goldstein_numbers.rb

# Based on "How Infinity Explains the Finite" from PBS Infinite Series
# https://www.youtube.com/watch?v=oBOZ2WroiVY

# How to find the next goodstein number
#
# For 13 in base 2 
#   13
#   = 2^3 + 2^2 + 2^0
#   = 2^(2^1 + 2^0) + 2^(2^1) + 2^0
# Switch 2s in the base to 3s
#   3^(3^1 + 3^0) + 3^(3^1) + 3^0
#   = 3^4 + 3^3 + 3^0 = 81 + 27 + 1
#   = 109
# Subtract 1 to get
#   109-1
#   = 108
# 
# For 1279 in base 4
#   1279
#   = 1*4^5 + 3*4^3 + 3*4^2 + 3*4^1 + 3*4^0
#   = 1*4^(4^1 + 4^0) + 3*4^3 + 3*4^2 + 3*4^1 + 3*4^0
# Swtich 4s in base to 5s
#   1*5^(5^1 + 5^0) + 3*5^3 + 3*5^2 + 3*5^1 + 3*5^0
#   = 5^(5+1) + 3*125 + 3*25 + 3*5 + 3
#   = 15_625 + 375 + 75 + 15 + 3
#   = 16093
# Subtract 1 to get
#   16093-1
#   = 16092
#
# She said "eventually they hit zero and terminate",
# Which I'll interpret as conditionally subtracting 1
# This will mean we never go lower than 0


# so we can make sure the function we just wrote works before going on to functions that depend on it
def assert_equal(expected, actual)
  return if expected == actual
  raise StandardError, "Expected #{expected.inspect}, got #{actual.inspect}", caller
end


# For a given goldstein number in a given base, return the next goldstein number
def goodstein_next(n:, base:)
  return n if n.zero?
  in_next_base(n, base) - 1
end
def in_next_base(n, base)
  return n if n < base # b/c it's the coefficient of base^0=1, which doesn't change as base changes
  exponent    = (Math.log(n) / Math.log(base)).floor
  digit       = base**exponent # eg if exponent was 2 in base 10, it would be the 3rd digit, the hundreds digit
  coefficient = n/digit        # note that this is integer division
  remainder   = n - coefficient*digit
  next_place  = (base+1) ** in_next_base(exponent, base)
  coefficient*next_place + in_next_base(remainder, base)
end
assert_equal 0,     goodstein_next(n: 0,    base: 12)
assert_equal 108,   goodstein_next(n: 13,   base: 2) # reasoned through above, confirmed in video
assert_equal 16092, goodstein_next(n: 1279, base: 4) # reasoned through above, confirmed in video


def goodstein_seq(n, length, base=2)
  return []  if length.zero?
  return [n] if n.zero?
  successor = goodstein_next n: n, base: base
  [n] + goodstein_seq(successor, length-1, base+1)
end
assert_equal [],                     goodstein_seq(13, 0)
assert_equal [13, 108, 1279, 16092], goodstein_seq(13, 4) # confirmed in video
assert_equal [2, 2, 1, 0],           goodstein_seq(2, 100)

# Lets look at a few sequences
len = 8
goodstein_seq(0, len) # => [0]
goodstein_seq(1, len) # => [1, 0]
goodstein_seq(2, len) # => [2, 2, 1, 0]
goodstein_seq(3, len) # => [3, 3, 3, 2, 1, 0]
goodstein_seq(4, len) # => [4, 26, 41, 60, 83, 109, 139, 173]
goodstein_seq(5, len) # => [5, 27, 255, 467, 775, 1197, 1751, 2454]
goodstein_seq(6, len) # => [6, 29, 257, 3125, 46655, 98039, 187243, 332147]


def goodstein_size(n)
  size = 0
  loop do
    size += 1
    break if n.zero?
    n = goodstein_next(n: n, base: size+1)
  end
  size
end
assert_equal 1, goodstein_size(0)
assert_equal 2, goodstein_size(1)
assert_equal 4, goodstein_size(2)
assert_equal 6, goodstein_size(3) # confirmed from video

# The number it takes to terminate at goodstein_size(4) is so big 
# that she writes it with exponents of exponents:
#   3*2^(3*2^27 + 27) - 3
# Ruby won't even calculate its size:
#   $ ruby -e 'p 3*(2**(3*(2**27) + 27)) - 3'
#   -e:1: warning: in a**b, b may be too big
#   Infinity
# Wikipedia says this about it:
# > Elements of G(4) continue to increase for a while, but at base 3⋅2^402_653_209,
# > they reach the maximum of 3⋅2^402_653_210−1, stay there for the next 
# > 3⋅2^402_653_209 steps, and then begin their first and final descent.