mathematical solution of hacker rank projecteuler :48

Question

Question is from Hacker Rank, I want mathematical solution...

Find the last ten digits of the series...

1^1 + 2^2 + 3^3 + ⋯ + N^N

if N is too big number

as where 1 <= N <= 2000000

i have code that loop over N, but it takes too much time to complete for N>1000000.

any idea to reduce time ???

code:
n = int(input())
if(n>=1 and n<=2*1e6):
    s=0
    for i in range(1, n+1):
        s+=(i**i)
    print(s%10000000000)

First move this question to "Mathematics", then play with different values of N and write what you found. You have to try before asking. — TT_ stands with Russia, Sep 20 '14 at 20:45
i have code that uses loop through N, but it takes too much time to complete for N>1000000 — Vishal Raj, Sep 20 '14 at 20:46
@TT_ I'd say this belongs here, not math.se. But he needs to show a bit more effort. And why are you going to N<=2e6, when Project Euler just goes to 1e3? — Teepeemm, Sep 24 '14 at 20:24
plz visit : https://www.hackerrank.com/contests/projecteuler/challenges/euler048 — Vishal Raj, Sep 26 '14 at 03:30
Take the modulus inside of the loop: `s %= 10**10`. It will mean taking the modulus many more times, but it will keep things from too crazily into arbitrarily big integers. The next step is to find a method that allows you to take modulus as you take powers (or write your own). Most big integer libraries have such a method. — Teepeemm, Sep 26 '14 at 14:19

score 0 · Accepted Answer · edited May 23 '17 at 11:59

This looks like Python, so I’ll assume that’s what you’re using (you should tag your question with the language you’re using).

The big problem is that i**i is humongous, so Python is using big integers to keep track of everything. Since 2e6^(2e6) has 12602060 digits, that’s too much to compute quickly (and way more than the 10 digits you need). This also means that my suggestion of moving the modulus into the loop probably wouldn’t have helped.

The solution is to take the modulus while you’re taking the exponentiation (for details see Modular exponentiation. Some implementations are here. Using Python makes this simpler, since you don’t need to worry about integer overflow (which, ironically, is what caused your original problem).

But Python makes this even easier, since pow allows you to specify an optional modulus. So you could rewrite your original code as:

n = int(input())
if ( 1<=n<=2e6 ):
  s = 0
  for i in range(1,n+1):
    s += pow(i,i,10**10)
  print(s%(10**10))

But we can simplify this further. Python also includes a sum function, so you could use a list comprehension and rewrite the above as

n = int(input())
if ( 1<=n<=2e6 ):
  s = sum( pow(i,i,10**10) for i in range(1,n+1) )
  print(s%(10**10))

But it’s silly to assign a variable for only one step. So you’d rewrite that as

n = int(input())
if ( 1<=n<=2e6 ):
  print(sum( pow(i,i,10**10) for i in range(1,n+1) ) % 10**10)

But you may prefer to use the command line interface for Python, and not worry about checking the input:

sum( pow(i,i,10**10) for i in range(1,2*10**6+1) ) % 10**10

mathematical solution of hacker rank projecteuler :48

1 Answers1