Self powers
2014-12-12
Problem 048: Self powers
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<
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 |