# Finding the last ten digits of $\sum_{n=1}^{1000} n^n$

This is my solution to Project Euler Problem 48.

Problem:

The series, $1^1 + 2^2 + 3^3 + ... + 10^{10} = 10405071317$ .

Find the last ten digits of the series, $1^1 + 2^2 + 3^3 + ... + 1000^{1000}$.

I would like feedback/advice to possibly increase efficiency and/or correct incorrect practices.

public static void main(String[] args) {
BigInteger start, sum = BigInteger.valueOf(0);

for (int i = 1; i <= 1000; i++) {
start = BigInteger.valueOf(i);
}
String sumStr = sum.toString();
System.out.println(sumStr.substring(sumStr.length() - 10));
}

• Hint: Use number theory to simplify the series modulo 10^10 – 1110101001 Oct 12 '16 at 5:24
• I second that. Project Euler are not programming problems. They aren't even algorithm problems. They are maths problems. Most of them can be extremely simplified by using a little bit of number theory or combinatorics. – Jörg W Mittag Oct 12 '16 at 8:19
• @JörgWMittag In my experience the mathy approaches optimize the performance, but they rarely simplify the code. The OP's code is short, easy to understand and runs in a fraction of a second. I'd only switch to mathy approaches when summing tens of millions of numbers. – CodesInChaos Oct 12 '16 at 9:09

• Use the right data type. The last ten digits of the sum is same as the sum modulo $10000000000 = 10^{10}$, which is smaller than $2^{34}$. All computations can be comfortably done with 64-bit integers; invoking BigInteger is a definite overkill. Extracting ten digits via string operations is also quite suboptimal.

• Reuse your computations. Once you computed $k = n^n$, use it to compute $(2n)^{2n} = 2^{2n} n^{2n} = 2^{2n}k^2$.

• Devise an algorithm. The logic of the previous bullet applies to any $mn$: $(mn)^{mn} = m^{mn}n^{mn} = (m^m)^n (n^n)^m$. This observation lends itself to the scheduling of computations very close to be optimal. Think about divisibility in general and prime numbers in particular.

• Any multiple of 10 raised to the corresponding power is surely divisible by $10^{10}$, and can be safely omitted from summation, but this is a minor optimization.

• All your proposed changes unnecessarily complicate the code which is already fast enough (My C# port takes 70ms and goes down to 2ms using the modPow optimization). So I'd only do them if you really want to view the problem as a math problem and not as a coding problem. – CodesInChaos Oct 12 '16 at 8:51
• The scope of start is larger than necessary
• The name of start is misleading, it should be something like base or perhaps bigI/iBig since it's just the big integer representation of i.
• Personally I'd eliminate it entirely, inlining the BigInteger.valueOf(i)
• I don't like using a single variable declaration, where some of the variables get initialized and some don't.
• You can use BigInteger.modPow with a modulus of 10^10, but for the small numbers you're dealing with, that might be considered premature optimization since the original code is already fast enough (70ms vs 2ms in my C# test)
• I'd replace your string manipulation with a modulus operation