{"id":626,"date":"2012-08-10T00:59:11","date_gmt":"2012-08-10T04:59:11","guid":{"rendered":"http:\/\/www.joshho.com\/blog\/?p=626"},"modified":"2012-09-07T16:03:02","modified_gmt":"2012-09-07T20:03:02","slug":"project-euler-problem-58","status":"publish","type":"post","link":"https:\/\/www.joshho.com\/blog\/2012\/08\/10\/project-euler-problem-58\/","title":{"rendered":"Project Euler – Problem 58"},"content":{"rendered":"

Problem 58:
\nStarting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed.<\/p>\n

<\/p>\n
37<\/b> 36 35 34 33 32 31<\/b>\r\n38 17<\/b> 16 15 14 13<\/b> 30\r\n39 18  5<\/b>  4  3<\/b> 12 29\r\n40 19  6  1  2 11 28\r\n41 20  7<\/b>  8  9 10 27\r\n42 21<\/b> 22 23 24 25 26\r\n43<\/b> 44 45 46 47 48 49<\/pre>\n
<\/center>
\n
\nIt is interesting to note that the odd squares lie along the bottom right diagonal, but what is more interesting is that 8 out of the 13 numbers lying along both diagonals are prime; that is, a ratio of 8\/13 = +\/-62%.<\/p>\n
If one complete new layer is wrapped around the spiral above, a square spiral with side length 9 will be formed. If this process is continued, what is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?<\/p>\n
<\/p>\n
\r\nimport java.math.BigInteger;\r\n\r\nclass runner\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 diff_p = 0; int prev = 0;\r\n\t\tint i=1;\r\n\r\n\t\tint numOfPrime = 0;\r\n\t\tdouble totalDiag = 0;\r\n\t\twhile(true){\r\n\t\t\tint difference = 2*diff_p;\/\/from 8*diff_p\/4\r\n\t\t\tfor(int j=1;j<5;j++){\r\n\t\t\t\tBigInteger x = new BigInteger(\"\"+(difference*j+prev));\r\n\t\t\t\tif(x.isProbablePrime(100)){\r\n\t\t\t\t\tnumOfPrime++;\r\n\t\t\t\t}\r\n\t\t\t\ttotalDiag++;\r\n\t\t\t}\r\n\t\t\tdouble cur = numOfPrime\/totalDiag;\r\n\t\t\tif(numOfPrime> 0 && cur < .1){\r\n\t\t\t\tbreak;\r\n\t\t\t}\r\n\r\n\t\t\tprev = i*i;\r\n\t\t\tdiff_p++;\r\n\t\t\ti+=2;\r\n\t\t}\r\n\r\n\t\tSystem.out.println(i);\r\n\t\tSystem.out.println(\"time:\"+(System.currentTimeMillis()-time));\r\n\t}\r\n}\r\n<\/pre>\n
<\/code>
\nNote: Got lazy and ended up using BigInteger for primality test.<\/p>\n","protected":false},"excerpt":{"rendered":"
Problem 58:
\nStarting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed.<\/p>\n
<\/p>\n
37<\/b> 36 35 34 33 32 31<\/b>\r\n38 17<\/b> 16 15 14 13<\/b> 30\r\n39 18  5<\/b>  4  3<\/b> 12 29\r\n40 19  6  1  2 11 28\r\n41 20  7<\/b>  8  9 10 27\r\n42 21<\/b> 22 23 24 25 26\r\n43<\/b> 44 45 46 47 48 49<\/pre>\n
<\/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\/626"}],"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=626"}],"version-history":[{"count":0,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/626\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/media?parent=626"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/categories?post=626"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/tags?post=626"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}