Problem 048

[geminizin]

Is there something wrong about problem 48? I'm pretty sure the answer is correct because I even verified it with published solutions on the internet.

[elendiastarman]

Problem 048 (View Problem)

Check to be sure that you're copy-pasting the number alone, and not any extra whitespace. Also be sure you're entering the last 10 digits, not all 3000+ digits or so...

That help?

[geminizin]

Very sure. I don't wanna post the answer here though...

[elendiastarman]

Alright. PM me and I'll have a look. (I've already solved it, feel free to check there.)

[ZombieFromHell]

Is there any efficient algorithm to solve this problem. I managed to solve this usual the naive looping method.

[harryh]

A. Please don't start a new thread here, if there is already one for the specific problem.

B. W.r.t. efficient methods : I suggest you read through the problem's forum (in the main site), where those who have solved it before you, are discussing their methods.

[ZombieFromHell]

Yeah i checked the forum link that appeared after the submission, It was more like a discussion on how the same thing is done on different languages and the thread seems to be locked. Atleast does a logic to find the last n digits of the summation series ? or this is the only way

[GenePeer]

I doubt there is. The best way to make this more efficient is to have an efficient exponentiating function, which is the same as Problem 122 (View Problem)

[wsmithrill]

I'm also interested in the maths behind this problem. I started with the naive looping method which yielded a result up to about 150^150 in the minute "allowed"
I did some research and found the square and multiply method for exponentiation a number, implemented this and got the answer in about 5 minutes. It's possible my multiply and add methods are not as efficient as they could be, but basically would like to know if I should try to optimise these, or try to further optimise my exponentiating method? I know it's difficult to answer without code samples to see which of my methods are the lamest, but how have others solved it? Which methods for exponentiating have been used?

[GenePeer]

Try looking into modular exponentiation as well.

[DednDave]

I agree.
Not only is the discussion in that forum all about "how to do the same thing in different languages", the thread is locked and does not allow discussion of the algorithm, itself.
Anyone can write a loop in their language of choice.
And I do not care to focus on which is fastest or how many lines of code are required.
I am interested in discussion of the most efficient method (algorithm).
I am new to Project Euler, and I find this very disappointing.

[TheThinker]

I have a really stoopid question... Does "the last 10 digits of the series" refer to the most significant (i.e., leftmost) or least significant (i.e. rightmost) digits?

[jaap]

I have a really stoopid question... Does "the last 10 digits of the series" refer to the most significant (i.e., leftmost) or least significant (i.e. rightmost) digits?

The rightmost / least significant.

By the way, if it had been the leftmost, then you could probably have just ignored the 1^1 to 995^995 terms, as they wouldn't have made a difference to the answer.

[singermornings2]

Hello, I'm trying to solve this problem and during mi "google research" I found out about modular exponentiation. I'm sure that's the concept I need to solve it because Matlab doesn't like adding that numbers in a for loop
I found this: http://en.wikipedia.org/wiki/Modular_exponentiation
But I don't really understand that modulo thing. How can I apply it to the problem? What do I do with the modulo and how do I choose it? Is that a way to do only the power part of the problem? (2^2, 3^3... n^n) and then adding them up is another part?
By the way the final number is really big and I don't know which kind of variable should I use, some kind of long double, but as I don't know how big the final result is I don't know whether it will fit or not
I thougt of another way of doing it just to keep the intermediate results small, which is: Exp(sum)=Exp(1)*Exp(2²)*Exp(3³)*...*Exp(1000¹⁰⁰⁰) and then using logarithms, but came up to nothing. Anyone knows if there's a way of doing it with my method?
Thank you very much for your help and sorry for posting such a long message

[thundre]

Explaining how to use modular exponentiation to solve this problem would fall into the category of "spoilers", which are not allowed on this board.

By the way the final number is really big and I don't know which kind of variable should I use,

Actually the final answer is only 10 digits. The sum is 3001 digits (9966 bits), and that's the hard part of the problem. Today's computers are designed to calculate 64 bits at a time. It's easy to write loops that multiply and add, but if your language can't count beyond 64 bits, you have to use a different approach.

I thougt of another way of doing it just to keep the intermediate results small, which is: Exp(sum)=Exp(1)*Exp(2²)*Exp(3³)*...*Exp(1000¹⁰⁰⁰) and then using logarithms, but came up to nothing. Anyone knows if there's a way of doing it with my method?

That's a very creative transformation of the problem, but it doesn't help. It actually produces a much larger intermediate result, and it doesn't get you over the precision hurdle.

[singermornings2]

Okay, thanks for your help and sorry for the spoiler. I'll keep investigating because I'm quite sure I understand the modular exponentiation part, now I need to find out how to store the number or how to compute only the last ten digits. Can you give me a hint?
Thank you very much