Project Euler: Problem 30 – Digit fifth powers

Problem

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

1634 = 1^4 + 6^4 + 3^4 + 4^4
8208 = 8^4 + 2^4 + 0^4 + 8^4
9474 = 9^4 + 4^4 + 7^4 + 4^4

As 1 = 1^4 is not a sum it is not included.

The sum of these numbers is 1634 + 8208 + 9474 = 19316.

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

Solution

This is pretty much easy problem. Here is the solution written in java. And it’s performance pretty cool 🙂

package projecteuler;

/**
 *
 * @author Shaiful Islam Palash
 */
public class Problem30 {
    public static void main(String[] args){
        solution1();
    }

    private static void solution1() {
        long fifthpower[] = new long[10];
        long n = 0; int pow = 5;
        for(int j=0; j<10; j++){
            n += Long.valueOf(CustomMath.pow(9, pow));
            fifthpower[j] = Long.valueOf(CustomMath.pow(j, pow));
        }
        long sumOfFifthPowers = 0;
        for(int i=2; i<n; i++){
            long sum = 0;
            for(char c : String.valueOf(i).toCharArray()){
                sum += fifthpower[Integer.valueOf(String.valueOf(c))];
                if(sum>i) break;
            }
            if(sum == i){
                System.out.println("this is what we look: " + i);
                sumOfFifthPowers += i;
            }
        }
        System.out.println("sum of all the numbers that can be written as the sum of fifth powers of their digits: " + sumOfFifthPowers);
    }
}

package projecteuler;

/**
 *
 * @author Shaiful Islam Palash
 */
public class CustomMath {
    
    public static String pow(long num, long pow){
        String result = "1", numm= String.valueOf(num);
        for (int j = 0; j < pow; j++) {
            result = CustomMath.multiply(result, numm);
        }
        return result;
    }
    
    public static String multiply(String a, String b){
        String result = "0";
        for(long i=0; i<Long.valueOf(b); i++){
            result = CustomMath.sum(result, a);
        }
        return result;
    }
    
    /**
     * Large summation
     * @param aLine
     * @param bLine
     * @return 
     */
    public static String sum(String aLine, String bLine) {
        if (bLine.length() >= aLine.length()) {
            String tmp = aLine;
            aLine = bLine;
            bLine = tmp;
        }

        char[] a = aLine.toCharArray();
        char[] b = bLine.toCharArray();
        StringBuffer sum = new StringBuffer();
        int cA = 0, cB = 0, cC = 0, cS = 0;
        int aLength = a.length - 1;
        int bLength = b.length - 1;

        while (true) {
            if (aLength >= 0) {
                cA = Integer.valueOf(String.valueOf(a[aLength]));
                if (bLength >= 0) {
                    cB = Integer.valueOf(String.valueOf(b[bLength]));
                } else {
                    cB = 0;
                }
                cS = cA + cB + cC;
                if (cS >= 10) {
                    cC = cS / 10;
                    cS = cS % 10;
                } else {
                    cC = 0;
                }
                sum.append(cS);


                aLength -= 1;
                bLength -= 1;
            } else {
                break;
            }
        }
        if (cC > 0) {
            sum.append(cC);
        }
        return sum.reverse().toString();
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s