2014-12-12

Problem 048: Self powers

Description:

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.

Solution:
v   v0p01**<  >:30p::>20p\1-:  #v_\$\$v
5>8#<"}"* #*>:|      ^%g01*g02:\<   2
>5+:::*:*: ^^-># \$# .# @#1g03%g01+g0<
Start
??
Pause
Reset
Output:
Stack:   (0)

Explanation:

I like the occasionally really easy problems between the others. It's like a little break sometimes.

The "trick" here is to understand the modulo operator. If you have (a + b) % c you can also write a%c + b%c. And also you can write (a * b)%c as (a%c) * (b%c).

So all we do is calculate the sum kinda normally, but we do modulo 10^10 after each step (every addition and multiplication). We guarantee this way that out numbers never exceed the range of an 64bit integer.

 Interpreter steps: 11 530 541 Execution time (BefunExec): 3.73s (3.09 MHz) Program size: 37 x 3 (fully conform befunge-93) Solution: 9110846700 Solved at: 2014-12-12

made with vanilla PHP and MySQL, no frameworks, no bootstrap, no unnecessary* javascript