Project Euler Forum

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?

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?

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

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.

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.

Thanks guys, great explanations

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?

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

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

The number you have to find the sum of the digits of is significantly larger than 2⁶⁴. 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.

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?

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:)

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.

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.

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?

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.

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.

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

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.

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?