Problem 048
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.
This forum is NOT meant to discuss solution methods for a problem.
See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.
This forum is NOT meant to discuss solution methods for a problem.
In particular don't post any code fragments or results.
Don't start begging others to give partial answers to problems
Don't ask for hints how to solve a problem
Don't start a new topic for a problem if there already exists one
Don't start begging others to give partial answers to problems
Don't ask for hints how to solve a problem
Don't start a new topic for a problem if there already exists one
See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
Problem 048
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
 Posts: 410
 Joined: Sat Dec 22, 2007 8:15 pm
Re: Problem 048
Problem 048 (View Problem)
Check to be sure that you're copypasting 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?
Check to be sure that you're copypasting 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?
Want some
3.14159265358979323846264338327950288419716939937510
58209749445923078164062862089986280348253421170679...?
3.14159265358979323846264338327950288419716939937510
58209749445923078164062862089986280348253421170679...?
Re: Problem 048
Very sure. I don't wanna post the answer here though...
 elendiastarman
 Posts: 410
 Joined: Sat Dec 22, 2007 8:15 pm
Re: Problem 048
Alright. PM me and I'll have a look. (I've already solved it, feel free to check there.)
Want some
3.14159265358979323846264338327950288419716939937510
58209749445923078164062862089986280348253421170679...?
3.14159265358979323846264338327950288419716939937510
58209749445923078164062862089986280348253421170679...?

 Posts: 2
 Joined: Thu Feb 17, 2011 2:31 pm
Problem 48
Is there any efficient algorithm to solve this problem. I managed to solve this usual the naive looping method.
Re: Problem 048
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.
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.

 Posts: 2
 Joined: Thu Feb 17, 2011 2:31 pm
Re: Problem 048
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
Re: Problem 048
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)

 Posts: 1
 Joined: Fri May 13, 2011 1:44 pm
Re: Problem 048
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?
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?
Re: Problem 048
Try looking into modular exponentiation as well.
Re: Problem 048
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.
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.

 Posts: 1
 Joined: Tue Aug 23, 2011 11:55 pm
Re: Problem 048
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?
Re: Problem 048
The rightmost / least significant.TheThinker wrote: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?
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.
_{Jaap's Puzzle Page}

 Posts: 5
 Joined: Sat Aug 27, 2011 3:46 pm
Re: Problem 048
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^{2})*Exp(3^{3})*...*Exp(1000^{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
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^{2})*Exp(3^{3})*...*Exp(1000^{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
Re: Problem 048
Explaining how to use modular exponentiation to solve this problem would fall into the category of "spoilers", which are not allowed on this board.
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.singermornings2 wrote:By the way the final number is really big and I don't know which kind of variable should I use,
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 wrote:I thougt of another way of doing it just to keep the intermediate results small, which is: Exp(sum)=Exp(1)*Exp(2^{2})*Exp(3^{3})*...*Exp(1000^{1000}) and then using logarithms, but came up to nothing. Anyone knows if there's a way of doing it with my method?

 Posts: 5
 Joined: Sat Aug 27, 2011 3:46 pm
Re: Problem 048
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
Thank you very much