# Project Euler #57: Square root convergents

# Project Euler #57: Square root convergents

kitchent + 0 comments This problem is trivial. No need for the use of

`fractions`

. Just feed`a, b`

with a function returning`a + b + b, a + b`

, and begin with`1, 1`

. Compare the`len`

of`str(a)`

and`str(b)`

. Done. Took less than a minute.

Crafter_Artisan + 0 comments "Each fraction is built from the one before by a simple rule: add top and bottom to get new bottom, add top and twice bottom to get new top. That sequence converges to the square root of 2." --- John Derbyshire,

*Prime Obsession*(Note that you'll have to modify this procedure slightly if you don't store each old bottom, or denominator, when replacing it with the next one.)

venidici + 1 comment Is there any limitation on memory? I can pass my test in my own computer. but test #4 and #5 get wrong answer there. Thanks a lot.

Piyushgrwl + 1 comment Were you able to sort out the problem. My code is also showing wrong answer for test #4 and #5. Any suggestions would be helpful. Thanks!!

hashirama + 0 comments [deleted]

SaurabhBhagat123 + 0 comments All testcases showing success but 4th and 5th test cases terminated due to timeout.

negromano + 0 comments If anyone is having issues with case 7, remember to consider that n includes iteration n itself.

chenjiexjtu + 0 comments from fractions import Fraction n = int(input().strip()) dec = [0,Fraction(1,2)] for i in range(2,n+1): temp1 = Fraction(1,2+dec[i-1]) dec.append(temp1) temp2 = Fraction(1,1) temp3 = temp2+temp1 nume = temp3.numerator deno = temp3.denominator if len(str(nume))>len(str(deno)): print(i)

It seems a little easy, attached codes for your kind reference.

ErikTillema + 1 comment I'm using F# and BigIntegers for this problem. Initially got a TLE on test case 4 and 5. Locally for n=10^4 my solution would run for about 8 seconds. So to get my solution accepted, I precalculated everything and used that. But that's not very satisfying. Did anybody solve this problem in a .NET language or Java, without precalculation? Did I miss any cleverness to avoid using BigIntegers and huge numbers? Any hint would be appreciated. Thanks!

xie1995 + 0 comments I did it with BigInteger through Scala's BigInt wrapper.

What I did to get TLEs from cases 4 and 5 was to convert the BigInteger into a string, forcing calculation for all the digits, rather than only calculating the number of digits. It's only necessary to find a sufficiently accurate base-10 logarithm for the BigInteger.

tomy_495 + 0 comments It seems very easy to solve using "fractions" class of python and yes it is! but I am getting TLE for TC 4 and 5.......any suggestions to optimize it? Thank You!

gunnar0744 + 1 comment Has some done this in c also ? Please let me know as I am able to pass testcases 1 ,6,7 but not others ?

abhiranjan + 1 comment Yes, a lot of people had done it in C.

Best of luck!gurparkashsohi + 0 comments I'm having the same problem. Passing only 1, 6, 7. What did you do?

viswanadh_534 + 1 comment Can anybody help me how to add two numbers that are stored in strings and assign the result to another string ?

shashank21jHackerRank AdminChallenge Author + 0 comments Why not integer array?

meanwhile pick a language where you can deal with BIgInteger :)

Sort 12 Discussions, By:

Please Login in order to post a comment