{"id":577,"date":"2012-08-07T00:45:38","date_gmt":"2012-08-07T04:45:38","guid":{"rendered":"http:\/\/www.joshho.com\/blog\/?p=577"},"modified":"2012-09-07T16:09:50","modified_gmt":"2012-09-07T20:09:50","slug":"project-euler-problem-44","status":"publish","type":"post","link":"https:\/\/www.joshho.com\/blog\/2012\/08\/07\/project-euler-problem-44\/","title":{"rendered":"Project Euler &#8211; Problem 44"},"content":{"rendered":"<p>Problem 44: Pentagonal numbers are generated by the formula, Pn=n(3*n-1)\/2. The first ten pentagonal numbers are:<\/p>\n<p><center><\/p>\n<pre>1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...<\/pre>\n<p><\/center><\/p>\n<p>It can be seen that P4 + P7 = 22 + 70 = 92 = P8. However, their difference, 70 &#8211; 22 = 48, is not pentagonal.<\/p>\n<p>Find the pair of pentagonal numbers, Pj and Pk, for which their sum and difference is pentagonal and D = |Pk &#8211; Pj| is minimised; what is the value of D?<br \/>\n<!--more--><br \/>\n<code><\/p>\n<pre lang='java'>\r\nimport java.util.Collections;\r\nimport java.util.SortedSet;\r\nimport java.util.TreeSet;\r\nimport java.util.Vector;\r\n\r\nclass runner\r\n{\r\n\tprivate static int makepentagonal(int n){\r\n\t\tint y = n*(3*n-1)\/2;\r\n\t\tif(storage.contains(y)) return y;\r\n\t\tstorage.add(y);\r\n\t\treturn y;\r\n\t}\r\n\tprivate static boolean accept(int x, int y){\r\n\t\tint sum = x+y;\r\n\t\tif(storage.size() == 0){\r\n\t\t\tmakepentagonal(1);\r\n\t\t}\r\n\t\twhile(sum > storage.last()){\r\n\t\t\tmakepentagonal(storage.size()+1);\r\n\t\t}\r\n\r\n\t\t\r\n\t\tif(!storage.contains(sum)) return false;\r\n\t\tif(!storage.contains(x-y)) return false;\r\n\t\treturn true;\r\n\t}\r\n\r\n\tstatic TreeSet<Integer> storage = new TreeSet<Integer>();\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 d = -1;\r\n\t\tint x = 1;\r\n\t\touterLoop:\r\n\t\twhile(true){\r\n\t\t\tint px = makepentagonal(x);\r\n\t\t\tSortedSet<Integer> headset = storage.headSet(px);\r\n\t\t\tVector<Integer> lazy = new Vector<Integer>();\r\n\t\t\tfor(int py : headset){\/\/Get around java.util.ConcurrentModificationException\r\n\t\t\t\tlazy.add(py);\r\n\t\t\t}\r\n\t\t\tfor(int py: lazy){\r\n\t\t\t\tif(accept(px,py)){\r\n\t\t\t\t\td = px-py;\r\n\t\t\t\t\tbreak outerLoop;\r\n\t\t\t\t}\r\n\t\t\t}\r\n\t\t\tx++;\r\n\t\t}\r\n\t\tSystem.out.println(\"D:\"+d);\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: Using TreeSet for storage vs Vector sped up the execution time significantly (950ms vs 110seconds)<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem 44: Pentagonal numbers are generated by the formula, Pn=n(3*n-1)\/2. The first ten pentagonal numbers are:<\/p>\n<p><center><\/p>\n<pre>1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...<\/pre>\n<p><\/center><\/p>\n<p>It can be seen that P4 + P7 = 22 + 70 = 92 = P8. However, their difference, 70 &#8211; 22 = 48, is not pentagonal.<\/p>\n<p>Find the pair of pentagonal numbers, Pj and Pk, for which their sum and difference is pentagonal and D = |Pk &#8211; Pj| is minimised; what is the value of D?<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[56],"tags":[],"class_list":["post-577","post","type-post","status-publish","format-standard","hentry","category-project-euler"],"_links":{"self":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/577","targetHints":{"allow":["GET"]}}],"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=577"}],"version-history":[{"count":4,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/577\/revisions"}],"predecessor-version":[{"id":757,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/577\/revisions\/757"}],"wp:attachment":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/media?parent=577"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/categories?post=577"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/tags?post=577"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}