Problem 65:<\/p>\n
The square root of 2 can be written as an infinite continued fraction.<\/p>\n
sqrt(2) = 1+1\/(2+(1\/(2+1\/(2+1\/…))))
\n
\nThe infinite continued fraction can be written, 2 = [1;(2)], (2) indicates that 2 repeats ad infinitum. In a similar way, 23 = [4;(1,3,1,8)].<\/p>\n
It turns out that the sequence of partial values of continued fractions for square roots provide the best rational approximations.
\nLet us consider the convergents for 2.<\/p>\n
1+(1\/2) = 3\/2
\n1+(1\/(2+1\/2)) = 7\/5
\n1+(1\/(2+1\/(2+1\/2)) = 17\/12
\n1+(1\/(2+1\/(2+1\/(2+1\/2))) = 41\/29<\/p>\n
Hence the sequence of the first ten convergents for 2 are:<\/p>\n
1, 3\/2, 7\/5, 17\/12, 41\/29, 99\/70, 239\/169, 577\/408, 1393\/985, 3363\/2378, …<\/p>\n
What is most surprising is that the important mathematical constant,
\ne = [2; 1,2,1, 1,4,1, 1,6,1 , … , 1,2k,1, …].<\/p>\n
The first ten terms in the sequence of convergents for e are:<\/p>\n
2, 3, 8\/3, 11\/4, 19\/7, 87\/32, 106\/39, 193\/71, 1264\/465, 1457\/536, …
\nThe sum of digits in the numerator of the 10th convergent is 1+4+5+7=17.<\/p>\n
Find the sum of digits in the numerator of the 100th convergent of the continued fraction for e. <\/code><\/p>\n <\/code> Problem 65:<\/p>\n The square root of 2 can be written as an infinite continued fraction.<\/p>\n sqrt(2) = 1+1\/(2+(1\/(2+1\/(2+1\/…))))<\/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\/666"}],"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=666"}],"version-history":[{"count":0,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/666\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/media?parent=666"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/categories?post=666"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/tags?post=666"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\n<\/p>\n\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\tif(d == 0){\r\n\t\t\tthis.n= BigInteger.ZERO;this.d=BigInteger.ZERO;\r\n\t\t}else{\r\n\t\t\tthis.n= new BigInteger(\"\"+n);this.d=new BigInteger(\"\"+d);\r\n\t\t}\r\n\t}\r\n\t\r\n\tpublic Fraction(int n, BigInteger d){\r\n\t\tthis.n= new BigInteger(\"\"+n);this.d=d;\r\n\t}\r\n \r\n\tpublic Fraction(BigInteger n, BigInteger d){\r\n\t\tthis.n=n; this.d=d;\r\n\t}\r\n \r\n\tpublic Fraction(int n, Fraction f){\r\n\t\tthis.n=new BigInteger(\"\"+n);\r\n \r\n\t\tthis.n = this.n.multiply(f.d);\r\n\t\tthis.d = f.n;\r\n\t}\r\n \r\n\tpublic Fraction addWholeNumber(int i){\r\n\t\treturn addWholeNumber(new BigInteger(\"\"+i));\r\n\t}\r\n \r\n\tpublic Fraction addWholeNumber(BigInteger x){\r\n\t\tif(d.equals(BigInteger.ZERO))\r\n\t\t\treturn new Fraction(x, BigInteger.ONE);\r\n\t\treturn new Fraction(this.n.add(d.multiply(x)), d);\r\n\t}\r\n \r\n\tpublic String toString(){\r\n\t\treturn n+\"\/\"+d;\r\n\t}\r\n}\r\n<\/pre>\n<\/p>\n\r\n\r\n\r\nclass runner\r\n{\t\r\n\tprivate static int e_series(int i){\r\n\t\tif(i==1) return 0;\r\n\t\tint r = (i-2)%3;\r\n\t\tif(r == 0 || r == 2) return 1;\r\n\t\treturn 2*(i\/3);\r\n\t}\r\n\tpublic static Fraction e_converge(int max){\r\n\t\tif(max == 0) return new Fraction(2,1);\r\n\t\treturn e_converge_aux(1,max).addWholeNumber(2);\r\n\t}\r\n\tpublic static Fraction e_converge_aux(int count, int max){\r\n\t\tFraction result = new Fraction(1, e_series(count+1));\r\n\t\tif(count < max){\r\n\t\t\tresult = new Fraction(1, e_converge_aux(count+1, max));\r\n\t\t}\r\n\t\tresult = result.addWholeNumber(e_series(count));\r\n\r\n\t\treturn result;\r\n\t}\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\tFraction frac = e_converge(100-1);\r\n\t\tint sum = 0;\r\n\t\tfor(char y : frac.n.toString().toCharArray()){\r\n\t\t\tsum += y;\r\n\t\t}\r\n\t\tsum -= frac.n.toString().length()*48;\r\n\t\tSystem.out.println(sum);\r\n\t\t\r\n\t\tSystem.out.println(\"time: \"+(System.currentTimeMillis() - time));\r\n\t}\r\n}\r\n<\/pre>\n
\nNote: I did not consider f(0) = 2, which is why it's simply appended into the code.<\/p>\n","protected":false},"excerpt":{"rendered":"