10,958 Pages

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