Problem 048

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
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.

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


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
Post Reply
geminizin
Posts: 2
Joined: Tue Jul 13, 2010 4:40 am

Problem 048

Post by 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.

User avatar
elendiastarman
Posts: 410
Joined: Sat Dec 22, 2007 8:15 pm

Re: Problem 048

Post by 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... :P

That help?
Want some
3.14159265358979323846264338327950288419716939937510
58209749445923078164062862089986280348253421170679...?
Image

geminizin
Posts: 2
Joined: Tue Jul 13, 2010 4:40 am

Re: Problem 048

Post by geminizin »

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

User avatar
elendiastarman
Posts: 410
Joined: Sat Dec 22, 2007 8:15 pm

Re: Problem 048

Post by elendiastarman »

Alright. PM me and I'll have a look. (I've already solved it, feel free to check there.)
Want some
3.14159265358979323846264338327950288419716939937510
58209749445923078164062862089986280348253421170679...?
Image

ZombieFromHell
Posts: 2
Joined: Thu Feb 17, 2011 2:31 pm

Problem 48

Post by ZombieFromHell »

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

harryh
Posts: 2091
Joined: Tue Aug 22, 2006 9:33 pm
Location: Thessaloniki, Greece

Re: Problem 048

Post by 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
Posts: 2
Joined: Thu Feb 17, 2011 2:31 pm

Re: Problem 048

Post by 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

User avatar
GenePeer
Posts: 112
Joined: Sat Apr 03, 2010 1:14 pm
Contact:

Re: Problem 048

Post by 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)
Image

wsmithrill
Posts: 1
Joined: Fri May 13, 2011 1:44 pm

Re: Problem 048

Post by 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?

User avatar
GenePeer
Posts: 112
Joined: Sat Apr 03, 2010 1:14 pm
Contact:

Re: Problem 048

Post by GenePeer »

Try looking into modular exponentiation as well.
Image

DednDave
Posts: 1
Joined: Thu Aug 11, 2011 7:02 pm

Re: Problem 048

Post by 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
Posts: 1
Joined: Tue Aug 23, 2011 11:55 pm

Re: Problem 048

Post by 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?

User avatar
jaap
Posts: 551
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Problem 048

Post by jaap »

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?
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
Posts: 5
Joined: Sat Aug 27, 2011 3:46 pm

Re: Problem 048

Post by 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 :lol:
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(22)*Exp(33)*...*Exp(10001000) 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 :oops:

thundre
Posts: 356
Joined: Sun Mar 27, 2011 10:01 am

Re: Problem 048

Post by 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.
singermornings2 wrote: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.
singermornings2 wrote:I thougt of another way of doing it just to keep the intermediate results small, which is: Exp(sum)=Exp(1)*Exp(22)*Exp(33)*...*Exp(10001000) 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.
Image

singermornings2
Posts: 5
Joined: Sat Aug 27, 2011 3:46 pm

Re: Problem 048

Post by 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

Post Reply