4

尝试解决 Project Euler 问题 119：

数字 512 很有趣，因为它等于其数字之和的某个幂：5 + 1 + 2 = 8，并且 8^3 = 512。具有此属性的数字的另一个示例是 614656 = 28^4。

我们将定义 an 为该序列的第 n 项，并坚持一个数字必须包含至少两位数字才能有和。

给定 a2 = 512 和 a10 = 614656。

找到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

4

2 回答 2

8

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

把问题转过来。数字的和是一个比较小的数（最大9×数字的位数），幂也会比较低（即使很小的数也不需要很大的幂就可以提升到15位数） .

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

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

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

于 2012-12-12T22:35:11.710 回答
5

关于那个数字总和......这里有一些确凿的事实：

 0% Scenario{vm=java, trial=0, benchmark=NaiveDigitSum} 542.90 ns; σ=11.00 ns @ 10 trials
50% Scenario{vm=java, trial=0, benchmark=BetterDigitSum} 42.13 ns; σ=1.42 ns @ 10 trials

     benchmark    ns linear runtime
 NaiveDigitSum 542.9 ==============================
BetterDigitSum  42.1 ==

测试代码：

import com.google.caliper.Runner;
import com.google.caliper.SimpleBenchmark;

public class Performance extends SimpleBenchmark {
  public void timeNaiveDigitSum(int reps) {
    for (int r = 0; r < reps; r++) sumDigits(r + 1_000_000);
  }
  public void timeBetterDigitSum(int reps) {
    for (int r = 0; r < reps; r++) sumDigitsBetter(r + 1_000_000);
  }
  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;
  }
  static int sumDigitsBetter(long n) {
    int sum = 0;
    for (; n != 0; sum += n % 10, n /= 10);
    return sum;
  }
  public static void main(String... args) {
    Runner.main(Performance.class, args);
  }
}

（剧透解决方案已删除，可通过编辑历史获得）

于 2012-12-12T21:57:13.517 回答