当前位置:首页 » Project Euler » 详细页

Digit power sum 题号:119 难度: 30 中英对照

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

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.

Solution

该题可如下求解: 设该数为 $x$,各位数字之和为$n$,该数满足 *Digit power sum*,则有 $$ n \geq 2, k \geq 2, n^k \geq 10 , isDigigtSumPower(n^k) == True $$ 我们给出一个界限*limit*,每次增大 $2^{10}$,求在界限 limit 下满足条件的至少30个数,若不够30个就增大limit再次寻找。 由于 $n \geq 2$ 且 $limit = 2^k$ ,所以只要对$n$的指数只需要求到$k$ ,判断在 $j \in \{1 \sim k\}$内,对$n$遍历$n^j$ 是否是Digit Sum Number。 通过快速的遍历,使用*SortSet* 存储符合条件的点(其中点已经经过去重升序排列),我们找到第三十个满足条件的点输出即可。

Code

import java.math.BigInteger;
import java.util.*;
public class p119 {
    public static void main(String[] args) {
        long start=System.nanoTime();
        String result = run();
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
    }

	/*
	 * Candidates have the form n^k, where n >= 2, k >= 2, n^k >= 10, and isDigitSumPower(n^k) == true.
	 * We also impose n^k < limit. If there are at least 30 candidates under 'limit',
	 * then the 30th smallest candidate is the answer. Otherwise we raise the limit and search again.
	 *
	 * We only need to try the exponents k until 2^k exceeds the limit.
	 * We only need to try the bases n until the power of the digit sum is too small to match n^k.
	 * The power of the digit sum is digitSum(n^k)^k, which is at most (9 * digitLength(n^k))^k.
	 */

    private static final int INDEX = 30;  // 1-based

    public static String run() {
        for (BigInteger limit = BigInteger.ONE; ; limit = limit.shiftLeft(10)) {
            SortedSet<BigInteger> candidates = new TreeSet<>();
            // 通过Big Integer中 shiftLeft 方法实现左移, 左移k位,即 2^k
            for (int k = 2; BigInteger.valueOf(1).shiftLeft(k).compareTo(limit) < 0; k++) {
                for (int n = 2; ; n++) {
                    BigInteger pow = BigInteger.valueOf(n).pow(k);
                    if (pow.compareTo(limit) >= 0 && pow.toString().length() * 9 < n)
                        break;
                    // 找到满足条件的数
                    if (pow.compareTo(BigInteger.TEN) >= 0 && isDigitSumPower(pow))
                        candidates.add(pow);
                }
            }
            //返回找到的第30个数
            if (candidates.size() >= INDEX)
                return new ArrayList<>(candidates).get(INDEX - 1).toString();
        }
    }


    // Returns true iff there exists k >= 2 such that x = digitSum(x)^k.
    private static boolean isDigitSumPower(BigInteger x) {
        int digitSum = digitSum(x);
        if (digitSum == 1)  // Powers of 10 are never a power of 1
            return false;

        BigInteger base = BigInteger.valueOf(digitSum);
        BigInteger pow = base;
        while (pow.compareTo(x) < 0)
            pow = pow.multiply(base);
        return pow.equals(x);
    }

    // 数x的各位数字之和
    private static int digitSum(BigInteger x) {
        if (x.signum() < 1)
            throw new IllegalArgumentException("Only for positive integers");
        int sum = 0;
        for (char c : x.toString().toCharArray())
            sum += c - '0';
        return sum;
    }

}
248155780267521
10ms