### 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.

### 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))
}
}
//返回找到的第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