The underlying concepts of UVa 371: Ackermann Functions have been discussed in great details in our post of Collatz problem. In this post, we simply outlines an ad-hoc algorithm as a solution to this problem as follows.

import java.io.PrintWriter; | |

import java.util.Scanner; | |

public class Main { | |

private final Scanner in; | |

private final PrintWriter out; | |

private final static int _MaxValue = 1000000; | |

private final static long[] memo = new long[_MaxValue]; | |

public Main() { | |

in = new Scanner(System.in); | |

out = new PrintWriter(System.out, true); | |

} | |

public Main(Scanner in, PrintWriter out) { | |

this.in = in; | |

this.out = out; | |

} | |

private static long[] getInts(String input) { | |

String[] ints = input.trim().split(" "); | |

long[] rets = new long[2]; | |

rets[0] = Long.parseLong(ints[0]); | |

rets[1] = Long.parseLong(ints[1]); | |

return rets; | |

} | |

private void solveAckermannProblem(long from, long to) { | |

long maxValue = from; | |

long maxLength = 0; | |

for (long i = from; i <= to; i++) { | |

long length = computeCycleLength(nextAckermannNumber(i)); | |

if (maxLength < length) { | |

maxValue = i; | |

maxLength = length; | |

} | |

} | |

out.println(String | |

.format("Between %d and %d, %d generates the longest sequence of %d values.", | |

from, to, maxValue, maxLength)); | |

} | |

private static long computeCycleLength(long n) { | |

if (n == 0) | |

return 0; | |

if (n == 1) | |

return 1; | |

if (n < _MaxValue && memo[(int) n] != 0) | |

return memo[(int) n]; | |

long len = 1 + computeCycleLength(nextAckermannNumber(n));// computing | |

// length of | |

// Ackermann | |

// sequence | |

if (n < _MaxValue) // storing it in cache | |

memo[(int) n] = len; | |

return len; | |

} | |

public static long nextAckermannNumber(long n) { | |

if (n % 2 == 0) | |

return n / 2; | |

else | |

return n * 3 + 1; | |

} | |

public void run() { | |

while (in.hasNextLine()) { | |

long[] range = getInts(in.nextLine()); | |

if ((range[0] == 0) && (range[1] == 0)) | |

break; | |

long from = Math.min(range[0], range[1]); | |

long to = Math.max(range[0], range[1]); | |

solveAckermannProblem(from, to); | |

} | |

} | |

public static void main(String[] args) { | |

Main solver = new Main(); | |

solver.run(); | |

} | |

} |

Please leave a comment if you have any question regarding this problem or implementation. Thanks.

## 2 thoughts on “UVa 371. Ackermann Function”