Friedman's vector reduction problem

The vector reduction problem is a combinatorial problem researched by Harvey Friedman.

Let x = (x₁...x_k). Find the greatest i < k such that x_i is positive, and replace x_i and x_i+1 (if exists) by x_i - 1 and x₁ + ... + x_k, 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↑‎↑‎2^1,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[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

Friedman's vector reduction problem

Sources[]

See also[]