``` 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 ``` ```package algs24; import stdlib.*; /* *********************************************************************** * Compilation: javac PerfectPower.java * Execution: java PerfectPower x | more * * Print out all 64-bit integers of the form a^b where b <= x. * * Limitations * ---------- * - currently prints out duplicates, i.e., when a itself is a perfect * power, then there is more than one way to get a^b * * % java PerfectPower 2 * 4 = 2^2 * 8 = 2^3 * 9 = 3^2 * 16 = 2^4 * 16 = 4^2 * 25 = 5^2 * 27 = 3^3 * * % java PerfectPower 10 * 1024 = 2^10 * ... * 7450580596923828125 = 5^27 * 7516865509350965248 = 52^11 * 8335775831236199424 = 78^10 * 8650415919381337933 = 13^17 * 9065737908494995456 = 38^12 * *************************************************************************/ public class XPerfectPower implements Comparable { private final long value; private final int a; private final int b; public XPerfectPower(int a, int b) { this.value = power(a, b); this.a = a; this.b = b; } // brute force exponentation suffices public static long power(int a, int b) { long pow = 1; for (int i = 0; i < b; i++) { pow *= a; } return pow; } public int compareTo(XPerfectPower that) { if (this.value < that.value) return -1; else if (this.value > that.value) return +1; else return 0; } public String toString() { return value + " = " + a + "^" + b; } public static void main(String[] args) { int x = 2; if (args.length == 1) x = Integer.parseInt(args[0]); // initialize priority queue MinPQ pq = new MinPQ<>(); // maximum power representable as a long is 2^62 for (int b = x; b <= 62; b++) { pq.insert(new XPerfectPower(2, b)); } // find smallest power, print out, and update while (!pq.isEmpty()) { XPerfectPower p = pq.delMin(); StdOut.println(p); // add next perfect power if it doesn't overflow a long if (Math.pow(p.a + 1, p.b) < Long.MAX_VALUE) pq.insert(new XPerfectPower(p.a + 1, p.b)); } } } ```