{"id":622,"date":"2012-08-09T17:36:05","date_gmt":"2012-08-09T21:36:05","guid":{"rendered":"http:\/\/www.joshho.com\/blog\/?p=622"},"modified":"2012-09-07T16:05:43","modified_gmt":"2012-09-07T20:05:43","slug":"project-euler-problem-57","status":"publish","type":"post","link":"https:\/\/www.joshho.com\/blog\/2012\/08\/09\/project-euler-problem-57\/","title":{"rendered":"Project Euler &#8211; Problem 57"},"content":{"rendered":"<p>Problem 57:<br \/>\nIt is possible to show that the square root of two can be expressed as an infinite continued fraction.<\/p>\n<p><center><\/p>\n<pre>sqrt(2) = 1 + 1\/(2 + 1\/(2 + 1\/(2 + ... ))) = 1.414213...<\/pre>\n<p><\/center><br \/>\n<!--more--><br \/>\nBy expanding this for the first four iterations, we get:<\/p>\n<pre>1 + 1\/2 = 3\/2 = 1.5\r\n1 + 1\/(2 + 1\/2) = 7\/5 = 1.4\r\n1 + 1\/(2 + 1\/(2 + 1\/2)) = 17\/12 = 1.41666...\r\n1 + 1\/(2 + 1\/(2 + 1\/(2 + 1\/2))) = 41\/29 = 1.41379...<\/pre>\n<p>The next three expansions are 99\/70, 239\/169, and 577\/408, but the eighth expansion, 1393\/985, is the first example where the number of digits in the numerator exceeds the number of digits in the denominator.<\/p>\n<p>In the first one-thousand expansions, how many fractions contain a numerator with more digits than denominator?<br \/>\n<code><\/p>\n<pre lang='java'>\r\nimport java.math.BigInteger;\r\n\r\npublic class Fraction {\r\n\tBigInteger n,d;\r\n\tpublic Fraction(int n, int d){\r\n\t\tthis.n= new BigInteger(\"\"+n);this.d=new BigInteger(\"\"+d);\r\n\t}\r\n\t\r\n\tpublic Fraction(BigInteger n, BigInteger d){\r\n\t\tthis.n=n; this.d=d;\r\n\t}\r\n\t\r\n\tpublic Fraction(int n, Fraction f){\r\n\t\tthis.n=new BigInteger(\"\"+n);\r\n\t\t\r\n\t\tthis.n = this.n.multiply(f.d);\r\n\t\tthis.d = f.n;\r\n\t}\r\n\t\r\n\tpublic Fraction addWholeNumber(int i){\r\n\t\treturn addWholeNumber(new BigInteger(\"\"+i));\r\n\t}\r\n\t\r\n\tpublic Fraction addWholeNumber(BigInteger x){\r\n\t\treturn new Fraction(this.n.add(d.multiply(x)), d);\r\n\t}\r\n\t\r\n\tpublic Fraction addDenominator(Fraction frac){\r\n\t\tif(frac.d.toString().length() == 1 && frac.d.toString().equals(\"1\")){\r\n\t\t\treturn addWholeNumber(frac.n);\r\n\t\t}else{\r\n\t\t\tFraction result = new Fraction(n.add(frac.d), d.add(frac.n));\r\n\t\t\tresult.simplify();\r\n\t\t\treturn result;\r\n\t\t}\r\n\t}\r\n\t\r\n\tpublic void simplify(){\r\n\t\t\/*for(int i=2; i<Math.sqrt(d); i++){\r\n\t\t\twhile(n%i==0 &#038;&#038; d%i==0){\r\n\t\t\t\tn\/=i;\r\n\t\t\t\td\/=i;\r\n\t\t\t}\r\n\t\t}*\/\r\n\t\tBigInteger a = n;\r\n\t\tBigInteger b = d;\r\n\t\twhile(true){\r\n\t\t\tif(a.toString().length() == 1 &#038;&#038; a.toString().equals(\"1\")){\r\n\t\t\t\tn.divide(b);\r\n\t\t\t\td.divide(b);\r\n\t\t\t\tbreak;\r\n\t\t\t}else if(b.toString().length() == 1 &#038;&#038; b.toString().equals(\"1\")){\r\n\t\t\t\tn.divide(a);\r\n\t\t\t\td.divide(a);\r\n\t\t\t\tbreak;\r\n\t\t\t}\r\n\t\t\t\t\r\n\t\t\tint comp = a.compareTo(b);\r\n\t\t\tif(comp > 0){\r\n\t\t\t\ta.subtract(b);\r\n\t\t\t}else if(comp < 0){\r\n\t\t\t\tb.subtract(a);\r\n\t\t\t}else{\r\n\t\t\t\tn=new BigInteger(\"1\");\r\n\t\t\t\td=new BigInteger(\"1\");\r\n\t\t\t\treturn;\r\n\t\t\t}\r\n\t\t}\r\n\t}\r\n\t\r\n\tpublic String toString(){\r\n\t\treturn n+\"\/\"+d;\r\n\t}\r\n}\r\n<\/pre>\n<p><\/code><br \/>\n<code><\/p>\n<pre lang='java'>\r\nclass runner\r\n{\t\r\n\r\n\tpublic static void main (String[] args) throws java.lang.Exception\r\n\t{\r\n\t\tlong time = System.currentTimeMillis();\r\n\r\n\t\tint c = 0;\r\n\t\tFraction previous = new Fraction(1,2);\r\n\t\tfor(int i=0;i<1000;i++){\r\n\t\t\tFraction current = new Fraction(1,previous.addWholeNumber(2));\r\n\t\t\tprevious = current;\r\n\t\t\t\r\n\t\t\tcurrent = current.addWholeNumber(1);\r\n\t\t\tif(current.n.toString().length() > current.d.toString().length())\r\n\t\t\t\tc++;\r\n\r\n\t\t\t\/\/System.out.println(current);\r\n\t\t\t\r\n\t\t}\r\n\t\tSystem.out.println(\"c:\"+c);\r\n\t\tSystem.out.println(\"time: \"+(System.currentTimeMillis() - time));\r\n\t}\r\n}\r\n<\/pre>\n<p><\/code><br \/>\nNote... just noticed addDenominator and simplify methods aren't used.. and thus un-tested methods as well :S<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem 57:<br \/>\nIt is possible to show that the square root of two can be expressed as an infinite continued fraction.<\/p>\n<p><center><\/p>\n<pre>sqrt(2) = 1 + 1\/(2 + 1\/(2 + 1\/(2 + ... ))) = 1.414213...<\/pre>\n<p><\/center><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[56],"tags":[],"_links":{"self":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/622"}],"collection":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/comments?post=622"}],"version-history":[{"count":0,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/622\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/media?parent=622"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/categories?post=622"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/tags?post=622"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}