001package algs24; 002import stdlib.*; 003/* *********************************************************************** 004 * Compilation: javac PerfectPower.java 005 * Execution: java PerfectPower x | more 006 * 007 * Print out all 64-bit integers of the form a^b where b <= x. 008 * 009 * Limitations 010 * ---------- 011 * - currently prints out duplicates, i.e., when a itself is a perfect 012 * power, then there is more than one way to get a^b 013 * 014 * % java PerfectPower 2 015 * 4 = 2^2 016 * 8 = 2^3 017 * 9 = 3^2 018 * 16 = 2^4 019 * 16 = 4^2 020 * 25 = 5^2 021 * 27 = 3^3 022 * 023 * % java PerfectPower 10 024 * 1024 = 2^10 025 * ... 026 * 7450580596923828125 = 5^27 027 * 7516865509350965248 = 52^11 028 * 8335775831236199424 = 78^10 029 * 8650415919381337933 = 13^17 030 * 9065737908494995456 = 38^12 031 * 032 *************************************************************************/ 033 034public class XPerfectPower implements Comparable<XPerfectPower> { 035 private final long value; 036 private final int a; 037 private final int b; 038 039 public XPerfectPower(int a, int b) { 040 this.value = power(a, b); 041 this.a = a; 042 this.b = b; 043 } 044 045 // brute force exponentation suffices 046 public static long power(int a, int b) { 047 long pow = 1; 048 for (int i = 0; i < b; i++) { 049 pow *= a; 050 } 051 return pow; 052 } 053 054 public int compareTo(XPerfectPower that) { 055 if (this.value < that.value) return -1; 056 else if (this.value > that.value) return +1; 057 else return 0; 058 } 059 060 public String toString() { 061 return value + " = " + a + "^" + b; 062 } 063 064 065 public static void main(String[] args) { 066 int x = 2; 067 if (args.length == 1) x = Integer.parseInt(args[0]); 068 069 // initialize priority queue 070 MinPQ<XPerfectPower> pq = new MinPQ<>(); 071 072 // maximum power representable as a long is 2^62 073 for (int b = x; b <= 62; b++) { 074 pq.insert(new XPerfectPower(2, b)); 075 } 076 077 // find smallest power, print out, and update 078 while (!pq.isEmpty()) { 079 XPerfectPower p = pq.delMin(); 080 StdOut.println(p); 081 082 // add next perfect power if it doesn't overflow a long 083 if (Math.pow(p.a + 1, p.b) < Long.MAX_VALUE) 084 pq.insert(new XPerfectPower(p.a + 1, p.b)); 085 } 086 } 087 088}