#include <iostream>
    #include <cmath>
    
    using namespace std;
    
    int powi(int x, int e)
    {
        int y = 1;
        while(e) {
            if (e&1) y *= x;
            x*=x;
            e >>= 1;
        }
        return y;
    }
    
    int main(int argc, char * argv[])
    {
        for(int n = 1; n <= 10000; ++n)
        {
            int d = 0, m = n;
            while(m) { d += m%10; m /= 10; }
            int e = 1;
            if (d > 1) e = round(log(n)/log(d));
            if (powi(d,e) == n)
                cout << n << ": " << d << "^" << e << " = " << n << endl;
        }
    }