problem 065

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.
phillip1882
Posts: 5
Joined: Sat Jun 21, 2008 9:08 pm

problem 065

Post by phillip1882 »

i'm having a bit of difficulty with problem 65.
here's how I aproached it:
[spoiler]spoiler snipped by hk.[/spoiler]
this seems right but i get an incorrect answer. any suggestions?
can i pm my code to someone?

TripleM
Posts: 382
Joined: Fri Sep 12, 2008 2:31 am

Re: problem 065

Post by TripleM »

As mentioned in the red box at the top of the page, don't post anything that might give away how to solve a particular problem - I'd suggest you edit your ideas out of the post. Are you sure you've read what number you are trying to find convergents of?

sashole
Posts: 3
Joined: Wed Jun 15, 2011 4:26 am

Re: problem 065

Post by sashole »

In the problem, isn't the 2nd term in the sequence of convergents for e 2.5, not 3?

mynameisalreadytaken
Posts: 20
Joined: Sun Sep 25, 2011 10:20 pm

Re: problem 065

Post by mynameisalreadytaken »

No, in this Problem you don't use the sum over 1/n! to approximate e, but the continued fraction given in the text.

Thus:
1: 2
2: 2 + 1/1 = 3
3: 2 + 1/(1 + 1/2) = 8/3
4: 2 + 1/(1 + 1/(2 + 1/1)) = 11/4
etc.
Image

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

Re: problem 065

Post by jaap »

sashole wrote:In the problem, isn't the 2nd term in the sequence of convergents for e 2.5, not 3?
No, the second term is [2;1] which means 2+1/1 = 3.
The third term is [2;1,2] = 2+1/(1+1/2) = 8/3

To get 2.5, you would need [2;1,1] instead.

sashole
Posts: 3
Joined: Wed Jun 15, 2011 4:26 am

Re: problem 065

Post by sashole »

Thanks guys, great explanations

pimspelier
Posts: 41
Joined: Tue Jan 21, 2014 2:06 pm
Location: The Netherlands

Re: problem 065

Post by pimspelier »

The numbers just get too big... They don't even fit in unsigned long longs: is this a mistake I made, or is it part of the problem to overcome those huge numbers?
Image

User avatar
hk
Administrator
Posts: 10674
Joined: Sun Mar 26, 2006 9:34 am
Location: Haren, Netherlands

Re: problem 065

Post by hk »

This is not a mistake, the numbers exceed longlong capacity.
Image

pimspelier
Posts: 41
Joined: Tue Jan 21, 2014 2:06 pm
Location: The Netherlands

Re: problem 065

Post by pimspelier »

unsigned long long then? Or will I have to use an array to store those numbers?
Image

User avatar
hk
Administrator
Posts: 10674
Joined: Sun Mar 26, 2006 9:34 am
Location: Haren, Netherlands

Re: problem 065

Post by hk »

The number you have to find the sum of the digits of is significantly larger than 264. So unsigned longlong won't work.
Perhaps for this one it's better to change to a language with arbitrary precision like e.g. Python.
Image

pimspelier
Posts: 41
Joined: Tue Jan 21, 2014 2:06 pm
Location: The Netherlands

Re: problem 065

Post by pimspelier »

So there's no fast algorithm to do it, meaning I can't do it in C.

If true, Python it is :( .

And what is arbitrary precision?
Image

User avatar
Slaunger
Posts: 40
Joined: Mon Jul 19, 2010 11:23 pm

Re: problem 065

Post by Slaunger »

pimspelier wrote:So there's no fast algorithm to do it, meaning I can't do it in C.

If true, Python it is :( .

And what is arbitrary precision?
There is a fast algorithm, and it can be done in C of course, but is so much easier to do in a language with arbitrary sized integers, like Python :D. Do not fear it, it is a valuable addition of your tollbox. :)

I think arbitrary precision is modtly a term used for languages or libraries capable of handling floats with arbitrary precision. I think what is meant is arbitrary sized integers bound by memory (AFAIK, I'm not an expert), and of course with veery large integers there is also a slowdown in the execution of certain operations.

My solution for this problem runs in 1 ms in Python on an ancient Core2 Duo 2.2 GHz 32 bit platform.

That is fast enough I believe:)
Last edited by Slaunger on Wed Mar 19, 2014 11:02 pm, edited 1 time in total.
Image

pimspelier
Posts: 41
Joined: Tue Jan 21, 2014 2:06 pm
Location: The Netherlands

Re: problem 065

Post by pimspelier »

So there is a fast algortihm that doesn't rely on calculating the numerator? Interesting...
Well, I'll learn Python and I hope that there's an overview.
Image

User avatar
Slaunger
Posts: 40
Joined: Mon Jul 19, 2010 11:23 pm

Re: problem 065

Post by Slaunger »

pimspelier wrote:So there is a fast algortihm that doesn't rely on calculating the numerator?
I just stated there was a fast algorithm for solving the problem.
Image

Svartskägg
Posts: 55
Joined: Thu Mar 29, 2012 11:55 am
Location: Sweden

Re: problem 065

Post by Svartskägg »

pimspelier wrote:Well, I'll learn Python and I hope that there's an overview.
Isn't it easier to just write the functions you need for big numbers in C?
Image
320641_5486fc18ea1dcc4e9a8f29c7677a5c19 <-- my friend key

User avatar
hk
Administrator
Posts: 10674
Joined: Sun Mar 26, 2006 9:34 am
Location: Haren, Netherlands

Re: problem 065

Post by hk »

Having more than one programming language at one's disposal is certainly not a waste of time.
Writing bigint functions in C oneself is in general hardly useful.
Image

Svartskägg
Posts: 55
Joined: Thu Mar 29, 2012 11:55 am
Location: Sweden

Re: problem 065

Post by Svartskägg »

hk wrote:Writing bigint functions in C oneself is in general hardly useful.
But it is not difficult to write the big number functions needed to solve this problem. It does not take many lines of code. It sounds like pimspelier thinks he is forced to use another language than C to solve this problem.
Image
320641_5486fc18ea1dcc4e9a8f29c7677a5c19 <-- my friend key

TripleM
Posts: 382
Joined: Fri Sep 12, 2008 2:31 am

Re: problem 065

Post by TripleM »

Especially when, at the time this problem was created, the entire point was to write the code to do the additions.

User avatar
hk
Administrator
Posts: 10674
Joined: Sun Mar 26, 2006 9:34 am
Location: Haren, Netherlands

Re: problem 065

Post by hk »

TripleM wrote:Especially when, at the time this problem was created, the entire point was to write the code to do the additions.
Looking into the forum hardly anybody did, so that point was mostly missed from the beginning.
Remains the point that nowadays it's more useful to invest time in learning a language like Python, or to invest time in learning to handle a bigint library in C, than to spend time on designing a basic add/mul bigint library yourself.
And let's be honest: for someone that has learned to code in C, is it really a big effort to learn enough Python to solve this problem?
You could also state that nowadays the added value of this problem might be to learn to switch to the tool that's suited best.
Image

pimspelier
Posts: 41
Joined: Tue Jan 21, 2014 2:06 pm
Location: The Netherlands

Re: problem 065

Post by pimspelier »

Thanks for advising me: I now solved the problem in Python, and Python is indeed a nice language. I especially like the ability of handling big numbers :D.

And what is a bigint library?
Image

Post Reply