# UVa 371. Ackermann Function

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.

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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(); } }
view raw UVa371.java hosted with ❤ by GitHub

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