Problem 064

[skyfex]

Hey

I'm having some problems with problem 64.. My application generates the correct fractions, and gives me a correct result for N<=13, but I can't get a correct answer for N<=10000.

I'm just wondering.. there's no limit on a_n is there? In all the examples a_n<10, but I assume that's not supposed to be a limit in other numbers.

http://projecteuler.net/index.php?secti ... lems&id=64

[skyfex]

I think I should review my fraction-generating code.

For others having problems here: Calculating the root as float, evaluating the fraction and calculating the difference could reveal some bugs.

Edit: Yup.. that did the trick. Found a very silly error.

[tiny]

I have two questions about this problem:
I tried to solve it in python and pascal and got several wrong answers.
For N < 500 all went well but when N > 500 there came differences and finally then answer for the problem was wrong.
Here are the questions

1. The period stops when some integer part is twice the first integer in the representation; is it possible that some integer becomes greater then twice the first integer?
e.g. =[66;(1,1,....,150,6,6,132)]

2. Could it be that differant answers come from different floating point types?
In pascal real and extended gave different answers

[Ikcelaks]

A common theme with problems at this site is that precision issues can be eliminated entirely by avoiding floating point representations. Sometimes this makes the algorithm more difficult, but the solution is more solid.

[tiny]

Okay I can follow that.
But where can I start?
The Sqrt is not an integer number.

[Ikcelaks]

How much of that square-root do you actually need to calculate? The problem text gives an excellent primer in a technique that should avoid any precision issues.

[nZifnab]

I'm sorry, I just don't think I quite understand what the question is asking =\ (Or how it's getting some of it's values).

I really just need some clarification, not a solution.

So here's what I don't quite get...Where the problem states:

For example, let us consider √23:
√23 = 4 + √23 - 4


First of all, why 4? Wouldn't it also be true to say something like:
√23 = 72 + √23 - 72 = 72 + ( 1 / ( 1 / ( √23 - 72 ) ) )
(Note: 72 was chosen arbitrarily, just as '4' seems to have been?)

Next...and this probably says more about me being a programmer doing math problems, than about me being a mathematician doing programming problems...but how does:
1 / ( √23 - 4 )
Simplify into:
1 + ( √23 - 3 ) / 7

And how was that particular expansion arrived at in the context of this problem?


Sorry if my questions seem to be stupid to you guys I've completed all problems prior to this one without too much trouble, but the wording/math on this one is confusing me.

[TripleM]

The square root of 23 is 4.795831... does that give you a clue as to where the 4 came from

As for getting rid of a square root on the bottom of a fraction, that's called rationalising the denominator, and is done by multiplying top and bottom by a certain something so that no square roots are left on the bottom.. googling should give you more details.

[nZifnab]

The square root of 23 is 4.795831... does that give you a clue as to where the 4 came from

As for getting rid of a square root on the bottom of a fraction, that's called rationalising the denominator, and is done by multiplying top and bottom by a certain something so that no square roots are left on the bottom.. googling should give you more details.

Thanks Triple These should give me the answers I was looking for, but is there something in the problem that should have tipped me off that the '4' came from the number before the decimal point? I don't know how I would have known that...Anyway, thanks a lot I should be able to do the problem now =p

[daniel.is.fischer]

The problem statement begins "All square roots are periodic when written as continued fractions".
So to solve the problem, you must know what a continued fraction is.
Then it is clear why [radic]23 = 4 + ([radic]23 - 4). The other things should be clear then, too.

[Smaug]

I have a problem with the step given as finding a₁ - how does one arrive at [frac](√23+3),2[/frac] = 3 + [frac]√23-3,2[/frac] rather than, for example, 4 + [frac](√23-5),2[/frac] (since Floor(√23) = 4)?

[TripleM]

I think you mean the step to find a₂ (a₁ was already found as 1 before that calculation).

[frac]√23+3,2[/frac] = 3.8979.. which has an integer part of 3.

[Smaug]

Ah, thanks! I understand now!

[bilbow]

Well, in my case I had same problem, but I found out the cause was, that during testing, I forgot in my code a limit that terminates the calculation after calculating first 10 coefficients, discarding these fractions completely (so they were neither odd or even). So check the results. Some of the square root fractions have period over 200...

[AArmada]

I'm having some difficulty with this one, can someone post the period lengths of some of the longer ones? Every one of mine ive checked (~20 digits long period) has been correct, so I'm assuming I'm missing some long ones.

[Svartskägg]

9993: 94
9994: 70
9995: 4
9996: 4
9997: 59

[explorerchess]

Dear Project Euler,

For this particular problem 064, I think you should add a little more explanation about the "continued fraction expansion". Normally (at least until the problem 64 I am now at) the problem describes the concept, the new concept a little prior to ask for the question. In that problem, certainly there is a text and a example but I feel it was not enough and example goes with undocumented shortcuts. Try to read it yourself having in mind you don't know the "continued fraction expansion" for the square root... It's not what you wrote that will help to understand. Vital infomation are missing for the reader who was not aware of the theory.

With humility, I think you should have wrote something similar to what can be found on Wikipedia here: http://en.wikipedia.org/wiki/Methods_of ... _expansion

NOW I SEE. Now we see the theory with the M, D and A.

Because again, from your example, someone not aware of the theory, would not understand where the first "4" is coming from in your example. And if, like me, by any chance, he "guessed" and "figured" it's from the closest smaller integer of the square root of the starting number, then, on the following terms, definitively he won't be able to "guess" or "figure" again where the 1, 3, 1, 8, etc. terms are coming from, from where the decision to use these was taken.

...or maybe it's just me who is not good enough also. I feel that you don't have to explain basic things like "what is a odd number", but for something like that, I think the theory should have been described more to show where the terms are coming from. Lucky I am, Wikipédia described it and I was able to understand finally.

Thanks for the problems and for your site. It's very nice.

Denis Bisson.

[hk]

The theory is described on the web on several pages.
You need only use a search engine to find it.
So please use the theory available.
Project Euler doesn't intend to be a textbook.

[explorerchess]

>You need only use a search engine to find it.

Dear Hk,

Yes? That's what I wrote? I did a quick search and yes I realized and learnt something I didn't know, yes. (by the way, the third hit was someone online showing the resolution of that 064 problem on projecteuler!).

My humble point was just a suggestion. So far the previous problems introduced the "meat" before the actual problem. That one was the first one I had the impression where all the necessary info was not inside the problem. And because it has so much terms but no explanation around where some choices of multiplicator were taken, I had the impression it was because I did not understand something. But after a little search on the web, yes, I figured and understood. So since initially I had printed the problem and tried to work on it (without Internet access) from time to time, lose a few time on that, etc., once I realized the fact that not all the info was in the problem that's why I suggest to maybe add a few lines so someone else would not lose the same time as me.

But that's fine. From now on I will not assume the problems does expose all the basic theory to be solved and it's normal to sometimes have to search somewhere else. That's fine.

From your comment I got the idea now.

Denis Bisson.

[TheEvil]

I think problem descriptions should not contain everything. For a later problem, which had more than 1000 solutions, I spent 9 months to find out, that I don't know some obvious thing. With that knowledge, I could solve the latest problem in less than 90 minutes (I didn't wake up for the start), and got 20 points. The aim of this site is that, you have to learn a lot of things, and you will have fun.