This month we searched for a starting arrangement to an algorithm that maximized its number of steps. We can generalize the active square’s corner numbers from integers to reals, consider the four numbers on the corners of the active square to be an element of R4, and the function representing a step to be
| f((a,b,c,d)) = ( | a-b | , | b-c | , | c-d | , | d-a | ). |
Without loss of generality we can consider an input (a,b,c,d) to have a largest and b>d. By simple case checking, the only such arrangement that doesn’t lead to (0,0,0,0) in fewer than 10 steps has a>b>c>d. We further can “normalize” our input by subtracting d from everything, and then dividing by a-d, to get a general input of the form (1,x,y,0) for 1>x>y>0. In order to find arbitrarily long sequences of integer inputs for f we want to search for a real input to f that never reaches (0,0,0,0). This would be achieved if the normalized output of f matches the input. In normalized space, we want either
x = (1-x-y)/(1-y) AND y = (x-2y)/(1-y)
or
x = (x+y-1)/x AND y = (2x-y-1)/x
The first set of equations resolves to
x3-4x2+6x-2=0
which happily has a zero at approximately x=0.456311…, and a corresponding y=0.160713….
The second set of equations resolves to a cubic without a zero between 0 and 1, so there is a unique fixed point of this normalized function. Now the only challenge is to find integer points (a,b,c,0) that are as close as possible, when normalized, to (1,x,y,0), and test them to see how large their g values are. Searching over all c values between 1 and 10,000,000, choosing a small set of a and b that are near to c/y and cx/y respectively, will find the optimal quadruple 8646064;3945294;1389537;0, which has g value 44. Observant solvers noticed some overlaps with these special input integers and the Tribonacci sequence!
Congrats to this month’s solvers that found the smallest maximal input!