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}