Friedman's vector reduction problem

The vector reduction problem is a combinatorial problem researched by Harvey Friedman.
Let x = (x1...xk). Find the greatest i < k such that xi is positive, and replace xi and xi+1 (if exists) by xi - 1 and x1 + ... + xk, respectively.
The number of times a vector (n, 0,...0) of length k can be reduced is lower bounded by A(k - 1, n) and upper bounded by A(k, n + c), where A is Friedman's version of the Ackermann function and c is a constant.
For example, the vector (2, 0, 0, 0, 0) can be reduced over 2↑‎↑‎21,000,000 times.
A program for reducing vectors is as follows:
class vector():
 
 def __init__(self):
 global v
 v = []
 done = False
 
 # input first entry (required)
 v1 = int_input(msg = "Enter first element: ", err = "Invalid entry, must be non-negative integer", min_val = 0)
 v.append(v1)
 # input other entries
 while not done:
 val = raw_input("Enter next element (-1 to stop): ")
 try:
 val = int(val)
 if val == -1:
 done = True
 elif val < -1:
 print "Invalid entry, must be non-negative integer"
 else:
 v.append(val)
 except:
 print "Invalid entry, must be non-negative integer"
 print "Vector entered: " + str(self)
 def run(self):
 # input number of iterations
 global iterations
 iterations = int_input(msg = "Enter number of iterations (0 to run until end): ", err = "Invalid entry, must be non-negative integer", min_val = 0)
 if iterations == 0:
 a = 1
 while sum(v[0:len(v) - 1]):
 self.v_reduce(a, v)
 a = a + 1
 else:
 for a in range(1, iterations):
 self.v_reduce(a, v)
 if sum(v[0:len(v) - 1]) == 0:
 break
 # returns vector in string format
 def __str__(self):
 return "%s" % (v,)
 
 # vector "reduction"
 def v_reduce(self, ct, *vec):
 vec = list(vec[0])
 t = sum(vec)
 m = max_index(vec)
 self.set_list(m, vec[m] - 1)
 self.set_list(m + 1, t)
 print "Iteration: " + str(ct) + ", v = " + str(self)
 
 def set_list(self, idx, new):
 v[idx] = new
 
# input integer
def int_input(msg = "Input value: ", err = "Invalid input", min_val = 0):
 valid_input = False
 while not valid_input:
 val = raw_input(msg)
 try:
 val = int(val)
 if val < min_val:
 print err
 else:
 valid_input = True
 except:
 print err
 return val
# get index of largest non-zero value
def max_index(vec):
 i = -1
 max_val = 0
 l = len(vec)
 for idx in range(0, l - 1):
 if vec[idx] > max_val:
 max_val = vec[idx]
 i = idx
 return i
 
# to allow clean import
if __name__ == "__main__":
 g = vector()
 g.run()
== Sources ==
* Friedman, Harvey. Lecture Notes on Enormous Integers
== See also ==
Category:Functions
Category:Theorems
Category:Up-arrow notation level