{"id":500,"date":"2012-08-02T10:07:43","date_gmt":"2012-08-02T14:07:43","guid":{"rendered":"http:\/\/www.joshho.com\/blog\/?p=500"},"modified":"2012-09-07T16:14:15","modified_gmt":"2012-09-07T20:14:15","slug":"project-euler-problem-26","status":"publish","type":"post","link":"https:\/\/www.joshho.com\/blog\/2012\/08\/02\/project-euler-problem-26\/","title":{"rendered":"Project Euler &#8211; Problem 26"},"content":{"rendered":"<p>Problem 26: Find the value of d < 1000 for which 1\/d contains the longest recurring cycle in its decimal fraction part.\n<!--more--><\/p>\n<p>Wrote a brute force one which took a little over an hour to complete&#8230; much to my embarrassment (not posted).<br \/>\nThen, reading up on decimal expansion on wikipedia, refactored my original code to this.<\/p>\n<p><code><\/p>\n<pre lang=\"java\">\r\nimport java.util.Vector;\r\n\r\nclass runner\r\n{\r\n\tprivate static int findRecurringLength(int d){\r\n\t\tif( d<= 1) return 0;\r\n\t\tint n = 1; int div = 0;\r\n\t\tint result_length = 0;\r\n\r\n\t\twhile( true ){\r\n\t\t\tint z = 1;\r\n\t\t\twhile( n < d ){\r\n\t\t\t\tn *= 10;\r\n\t\t\t\tz++;\r\n\t\t\t}\r\n\r\n\t\t\tdiv = n \/ d;\r\n\t\t\tint divdigits = numOfDigits(div);\r\n\t\t\tfor(int i=divdigits+1;i<z;i++){\r\n\t\t\t\tresult_length++;\r\n\t\t\t}\r\n\t\t\tresult_length++;\r\n\t\t\tn = n%d;\r\n\r\n\t\t\tif(n <= 1){\r\n\t\t\t\tbreak;\r\n\t\t\t}\r\n\t\t}\r\n\t\tSystem.out.println(d+\" \"+result_length);\r\n\t\treturn result_length;\r\n\t}\r\n\r\n\tprivate static int numOfDigits(int d){\r\n\t\tint z = 0;\r\n\t\twhile(d>0){\r\n\t\t\td\/=10;\r\n\t\t\tz++;\r\n\t\t}\r\n\t\treturn z;\r\n\t}\r\n\r\n\tstatic Vector<Integer> primestorage = new Vector<Integer>(); \r\n\r\n\tprivate static boolean isPrime(int n){ \r\n\t\tdouble sqr = Math.sqrt(n)+1;\r\n\t\tfor(int i=0; i<primestorage.size(); i++){\r\n\t\t\tif(primestorage.get(i) >= sqr) break;\r\n\t\t\tif(n % primestorage.get(i) == 0) return false;\r\n\t\t}\r\n\t\tprimestorage.add(n);\r\n\t\treturn true;\r\n\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\t\tprimestorage.add(2);\r\n\t\t\r\n\t\tint l = 0, llen = 0;\r\n\t\tfor(int d=2;d<1000;d++){\r\n\t\t\tif(!isPrime(d)) continue;\r\n\t\t\tint len = findRecurringLength(d);\/\/2*d due to 1. len(period) <= d-1; 2. We need double the period to verify it.\r\n\t\t\tif(llen < len){\r\n\t\t\t\tllen = len; l=d;\r\n\t\t\t}\r\n\t\t}\r\n\t\tSystem.out.println(l+\" len:\"+llen);\r\n\r\n\t\tSystem.out.println(\"time: \"+(System.currentTimeMillis() - time));\r\n\t}\r\n}\r\n<\/pre>\n<p><\/code><br \/>\nNote: This solves the question, but it operates under the assumption that primes will generate the largest number.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem 26: Find the value of d < 1000 for which 1\/d contains the longest recurring cycle in its decimal fraction part.\n\n<\/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\/500"}],"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=500"}],"version-history":[{"count":0,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/500\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/media?parent=500"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/categories?post=500"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/tags?post=500"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}