3
\$\begingroup\$

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);
        sum = sum.add(start.pow(i));
    }
    String sumStr = sum.toString();
    System.out.println(sumStr.substring(sumStr.length() - 10));
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Hint: Use number theory to simplify the series modulo 10^10 \$\endgroup\$ – 1110101001 Oct 12 '16 at 5:24
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Jörg W Mittag Oct 12 '16 at 8:19
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – CodesInChaos Oct 12 '16 at 9:09
10
\$\begingroup\$
  • 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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – CodesInChaos Oct 12 '16 at 8:51
2
\$\begingroup\$
  • 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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.