{"id":581,"date":"2012-08-07T01:24:09","date_gmt":"2012-08-07T05:24:09","guid":{"rendered":"http:\/\/www.joshho.com\/blog\/?p=581"},"modified":"2012-09-07T16:09:44","modified_gmt":"2012-09-07T20:09:44","slug":"project-euler-problem-45","status":"publish","type":"post","link":"https:\/\/www.joshho.com\/blog\/2012\/08\/07\/project-euler-problem-45\/","title":{"rendered":"Project Euler &#8211; Problem 45"},"content":{"rendered":"<p>Problem 45:<br \/>\nTriangle, pentagonal, and hexagonal numbers are generated by the following formulae:<\/p>\n<pre>Triangle\t \tTn=n(n+1)\/2\t \t1, 3, 6, 10, 15, ...\r\nPentagonal\t \tPn=n(3n1)\/2\t \t1, 5, 12, 22, 35, ...\r\nHexagonal\t \tHn=n(2n1)\t \t1, 6, 15, 28, 45, ...<\/pre>\n<p>It can be verified that T285 = P165 = H143 = 40755.<\/p>\n<p>Find the next triangle number that is also pentagonal and hexagonal.<br \/>\n<!--more--><br \/>\n<code><\/p>\n<pre lang='java'>\r\nimport java.math.BigInteger;\r\n\r\nclass runner\r\n{\r\n\tprivate static BigInteger getTriangle(int n){\r\n\t\tBigInteger x = new BigInteger(\"\"+n);\r\n\t\tx = x.multiply(new BigInteger(\"\"+(n+1)));\r\n\t\tx = x.divide(new BigInteger(\"2\"));\r\n\t\treturn x;\/\/n*(n+1)\/2;\r\n\t}\r\n\tprivate static BigInteger getPentagonal(int n){\r\n\t\tBigInteger x = new BigInteger(\"\"+n);\r\n\t\tx = x.multiply(new BigInteger(\"3\"));\r\n\t\tx = x.subtract(new BigInteger(\"1\"));\r\n\t\tx = x.multiply(new BigInteger(\"\"+n));\r\n\t\tx = x.divide(new BigInteger(\"2\"));\r\n\t\t\r\n\t\treturn x;\/\/n*(3*n-1)\/2;\r\n\t}\r\n\tprivate static BigInteger getHexagonal(int n){\r\n\t\tBigInteger x = new BigInteger(\"\"+n);\r\n\t\tx = x.multiply(new BigInteger(\"2\"));\r\n\t\tx = x.subtract(new BigInteger(\"1\"));\r\n\t\tx = x.multiply(new BigInteger(\"\"+n));\r\n\t\t\r\n\t\treturn x;\/\/n*(2*n-1);\r\n\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 ti = 285+1;\r\n\t\tint pi = 165;\r\n\t\tint hi = 143;\r\n\t\t\r\n\t\tBigInteger pval = getPentagonal(pi);\r\n\t\tBigInteger hval = getHexagonal(hi);\r\n\t\tBigInteger tval = new BigInteger(\"0\");\r\n\t\twhile(true){\r\n\t\t\ttval = getTriangle(ti);\r\n\t\t\t\r\n\t\t\twhile(tval.compareTo(pval) > 0){\r\n\t\t\t\tpi++;\r\n\t\t\t\tpval = getPentagonal(pi);\r\n\t\t\t}\r\n\t\t\t\r\n\t\t\twhile(tval.compareTo(hval) > 0){\r\n\t\t\t\thi++;\r\n\t\t\t\thval = getHexagonal(hi);\r\n\t\t\t}\r\n\t\t\t\r\n\t\t\tif(pval.compareTo(tval) == 0 && hval.compareTo(tval) == 0){\r\n\t\t\t\tbreak;\r\n\t\t\t}\r\n\t\t\tti++;\r\n\t\t}\r\n\t\t\r\n\t\t\r\n\t\tSystem.out.println(\"tval: \"+tval);\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: You can remove the entirety of Triangle Numbers due to the fact that the set of Hexagonal numbers contains Triangle numbers. Rewriting the above code without triangles brings down the execution time from 171ms to 111ms.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem 45:<br \/>\nTriangle, pentagonal, and hexagonal numbers are generated by the following formulae:<\/p>\n<pre>Triangle\t \tTn=n(n+1)\/2\t \t1, 3, 6, 10, 15, ...\r\nPentagonal\t \tPn=n(3n1)\/2\t \t1, 5, 12, 22, 35, ...\r\nHexagonal\t \tHn=n(2n1)\t \t1, 6, 15, 28, 45, ...<\/pre>\n<p>It can be verified that T285 = P165 = H143 = 40755.<\/p>\n<p>Find the next triangle number that is also pentagonal and hexagonal.<\/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-581","post","type-post","status-publish","format-standard","hentry","category-project-euler"],"_links":{"self":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/581","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=581"}],"version-history":[{"count":6,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/581\/revisions"}],"predecessor-version":[{"id":756,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/581\/revisions\/756"}],"wp:attachment":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/media?parent=581"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/categories?post=581"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/tags?post=581"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}