java - Project Euler #119 加快速度

Question

尝试解决 Project Euler 问题 119:

The number 512 is interesting because it is equal to the sum of its digits raised to some power: 5 + 1 + 2 = 8, and 8^3 = 512. Another example of a number with this property is 614656 = 28^4.

We shall define an to be the nth term of this sequence and insist that a number must contain at least two digits to have a sum.

You are given that a2 = 512 and a10 = 614656.

Find a30.

问题: 是否有比仅检查每个数字直到找到 a30 更有效的方法来找到答案？

我的代码

    int currentNum = 0;
    long value = 0;
    for (long a = 11; currentNum != 30; a++){ //maybe a++ is inefficient
        int test = Util.sumDigits(a);
        if (isPower(a, test)) {
            currentNum++;
            value = a;
            System.out.println(value + ":" + currentNum);
        }
    }
    System.out.println(value);

isPower 检查 a 是否为检验功效。 Util.sumDigits:

    public static int sumDigits(long n){
        int sum = 0;
        String s = "" + n;
        while (!s.equals("")){
            sum += Integer.parseInt("" + s.charAt(0));
            s = s.substring(1);
        }
        return sum;
    }

程序已经运行了大约 30 分钟(时间长了可能会溢出)。输出(到目前为止):

81:1

512:2

2401:3

4913:4

5832:5

17576:6

19683:7

234256:8

390625:9

614656:10

1679616:11

17210368:12

34012224:13

52521875:14

60466176:15

205962976:16

612220032:17

Answer 1

解决方案是一个 15 位数字。祝你好运，优化总和，使之运行得足够快，以检查每个数字。

彻底解决问题。数字之和是一个比较低的数字(最多9×这个数字的位数)，而且幂也比较低(即使是一个小数字，提高到15位也不需要很大的幂) .

因此，遍历总和和幂，计算总和(您可以在内部循环中使用乘法保持运行总计，甚至不需要幂计算)，然后将其数字相加以查看它是否与您的循环变量匹配。

数字不会按顺序排列，因此计算超出您需要的数量并对结果进行排序。

应该在大约一秒钟内运行。