| rdfs:comment
| - 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, b) and upper bounded by A(k + 1, n + c), where A is Friedman's version of the Ackermann function and c is a constant. For example, {2, 0, 0, 0, 0} can be reduced over 2↑↑21,000,000 times. A Python program for "reducing" vectors is as follows: def max_index(vec):
|
| abstract
| - 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, b) and upper bounded by A(k + 1, n + c), where A is Friedman's version of the Ackermann function and c is a constant. For example, {2, 0, 0, 0, 0} can be reduced over 2↑↑21,000,000 times. A Python program for "reducing" vectors is as follows: 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 1.
* 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 1.
* 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 1.
* to allow clean import if __name__ == "__main__": g = vector() g.run()
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)