## 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

Don't post any spoilers
phillip1882
Posts: 5
Joined: Sat Jun 21, 2008 10:08 pm

### problem 065

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 3:31 am

### Re: problem 065

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 5:26 am

### Re: problem 065

In the problem, isn't the 2nd term in the sequence of convergents for e 2.5, not 3?
Posts: 20
Joined: Sun Sep 25, 2011 11:20 pm

### Re: problem 065

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.
jaap
Posts: 555
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

### Re: problem 065

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 5:26 am

### Re: problem 065

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

### Re: problem 065

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?
hk
Posts: 11114
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

### Re: problem 065

This is not a mistake, the numbers exceed longlong capacity.
pimspelier
Posts: 41
Joined: Tue Jan 21, 2014 2:06 pm
Location: The Netherlands

### Re: problem 065

unsigned long long then? Or will I have to use an array to store those numbers?
hk
Posts: 11114
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

### Re: problem 065

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.
pimspelier
Posts: 41
Joined: Tue Jan 21, 2014 2:06 pm
Location: The Netherlands

### Re: problem 065

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?
Slaunger
Posts: 40
Joined: Tue Jul 20, 2010 12:23 am

### Re: problem 065

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 . 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.
pimspelier
Posts: 41
Joined: Tue Jan 21, 2014 2:06 pm
Location: The Netherlands

### Re: problem 065

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.
Slaunger
Posts: 40
Joined: Tue Jul 20, 2010 12:23 am

### Re: problem 065

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.
Svartskägg
Posts: 55
Joined: Thu Mar 29, 2012 12:55 pm
Location: Sweden

### Re: problem 065

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?

320641_5486fc18ea1dcc4e9a8f29c7677a5c19 <-- my friend key
hk
Posts: 11114
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

### Re: problem 065

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.
Svartskägg
Posts: 55
Joined: Thu Mar 29, 2012 12:55 pm
Location: Sweden

### Re: problem 065

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.

320641_5486fc18ea1dcc4e9a8f29c7677a5c19 <-- my friend key
TripleM
Posts: 382
Joined: Fri Sep 12, 2008 3:31 am

### Re: problem 065

Especially when, at the time this problem was created, the entire point was to write the code to do the additions.
hk
Posts: 11114
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

### Re: problem 065

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.
pimspelier
Posts: 41
Joined: Tue Jan 21, 2014 2:06 pm
Location: The Netherlands

### Re: problem 065

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 .

And what is a bigint library?