{"id":663,"date":"2012-08-18T11:52:21","date_gmt":"2012-08-18T15:52:21","guid":{"rendered":"http:\/\/www.joshho.com\/blog\/?p=663"},"modified":"2012-09-07T16:01:03","modified_gmt":"2012-09-07T20:01:03","slug":"project-euler-problem-64","status":"publish","type":"post","link":"https:\/\/www.joshho.com\/blog\/2012\/08\/18\/project-euler-problem-64\/","title":{"rendered":"Project Euler &#8211; Problem 64"},"content":{"rendered":"<p>Problem 64:<br \/>\nThe first ten continued fraction representations of (irrational) square roots are:<br \/>\n<!--more--><br \/>\nsqrt(2)=[1;(2)], period=1<br \/>\nsqrt(3)=[1;(1,2)], period=2<br \/>\nsqrt(5)=[2;(4)], period=1<br \/>\nsqrt(6)=[2;(2,4)], period=2<br \/>\nsqrt(7)=[2;(1,1,1,4)], period=4<br \/>\nsqrt(8)=[2;(1,4)], period=2<br \/>\nsqrt(10)=[3;(6)], period=1<br \/>\nsqrt(11)=[3;(3,6)], period=2<br \/>\nsqrt(12)= [3;(2,6)], period=2<br \/>\nsqrt(13)=[3;(1,1,1,1,6)], period=5<\/p>\n<p>Exactly four continued fractions, for N <= 13, have an odd period.\n\nHow many continued fractions for N <= 10000 have an odd period?\n<code><\/p>\n<pre lang='java'>\r\n\r\nclass runner\r\n{\t\r\n\tprivate static int find(int[][] found, int m, int d, int a){\r\n\t\tint c=0;\r\n\t\tfor(int[] x : found){\r\n\t\t\tif(x[0] == m && x[1] == d && x[2] == a) return c;\r\n\t\t\telse if(x[0] == 0 && x[1] == 0 && x[2] == 0) return -1;\r\n\t\t\tc++;\r\n\t\t}\r\n\t\treturn -1;\r\n\t}\r\n\tprivate static int count(int S){\r\n\t\tif(Math.floor(Math.sqrt(S)) == Math.sqrt(S)) return 0;\/\/period is 0.\r\n\t\t\r\n\t\tint m = 0, d=1, a0 = (int) Math.floor(Math.sqrt(S)), a=a0;\r\n\t\tint k = 0;\r\n\t\tint[][] found = new int[2*S+1][3];\r\n\t\twhile(true){\r\n\t\t\tint f = find(found, m,d,a);\r\n\t\t\tif(f > -1) return k-f;\r\n\t\t\t\r\n\t\t\tfound[k][0] = m ; found[k][1] = d; found[k++][2] = a;\r\n\t\t\tm = d*a-m;\r\n\t\t\td = (S-m*m)\/d;\r\n\t\t\ta = (int)(Math.floor((a0+m)\/d));\r\n\t\t}\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\t\t\r\n\t\tint odd=0;\r\n\t\tfor(int i=2; i<10000; i++){\r\n\t\t\tif(count(i)%2 == 1) odd++;\r\n\t\t\t\/\/System.out.println(i+\" \"+count(i));\r\n\t\t}\r\n\t\tSystem.out.println(\"odd:\"+odd);\r\n\t\tSystem.out.println(\"time: \"+(System.currentTimeMillis() - time));\r\n\t}\r\n}\r\n<\/pre>\n<p><\/code><br \/>\nNotes: http:\/\/en.wikipedia.org\/wiki\/Periodic_continued_fraction<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem 64:<br \/>\nThe first ten continued fraction representations of (irrational) square roots are:<\/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\/663"}],"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=663"}],"version-history":[{"count":0,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/663\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/media?parent=663"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/categories?post=663"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/tags?post=663"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}