{"id":638,"date":"2012-08-15T23:22:49","date_gmt":"2012-08-16T03:22:49","guid":{"rendered":"http:\/\/www.joshho.com\/blog\/?p=638"},"modified":"2012-09-07T16:02:00","modified_gmt":"2012-09-07T20:02:00","slug":"project-euler-problem-60","status":"publish","type":"post","link":"https:\/\/www.joshho.com\/blog\/2012\/08\/15\/project-euler-problem-60\/","title":{"rendered":"Project Euler &#8211; Problem 60"},"content":{"rendered":"<p>Problem 60:<br \/>\nThe primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime.<br \/>\n<!--more--><br \/>\nFor example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property.<\/p>\n<p>Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.<\/p>\n<p><code><\/p>\n<pre lang='java'>\r\nimport java.math.BigInteger;\r\nimport java.util.Vector;\r\n\r\nclass runner2\r\n{\t\r\n\t\/\/3 [11 13 17 19 23 29 31 37 41 43 47 53]\r\n\t\/\/11 [13 17 23 29 31 37 41 43 47 53]\r\n\tprivate static Vector<BigInteger> parseSet(Vector<BigInteger> currentSet, int currentCount) {\r\n\t\tif(currentSet.size() <= 1) return currentSet;\r\n\r\n\t\tVector<BigInteger> result = new Vector<BigInteger>();\r\n\t\tint biggestSize = 0;\r\n\t\tfor(int i=0; i<currentSet.size()-1 ;i++){\r\n\t\t\tVector<BigInteger> subSet = new Vector<BigInteger>();\t\t\t\r\n\t\t\tfor(int j=i+1; j<currentSet.size() ;j++){\r\n\t\t\t\tBigInteger bij = new BigInteger(currentSet.get(i).toString() + currentSet.get(j).toString());\r\n\t\t\t\tBigInteger bji = new BigInteger(currentSet.get(j).toString() + currentSet.get(i).toString());\r\n\r\n\t\t\t\tif(!bij.isProbablePrime(100) || !bji.isProbablePrime(100)) continue;\r\n\r\n\t\t\t\tsubSet.add(currentSet.get(j));\r\n\t\t\t}\r\n\t\t\t\/\/Requires at least (3 + filter + \"i\" on first pass) elements.\r\n\t\t\t\/\/Before passing in the residual set.\r\n\t\t\tif(subSet.size() < currentCount-1) continue;\r\n\t\t\t\/\/Parse the Subset...\r\n\t\t\tsubSet = parseSet(subSet, currentCount-1);\r\n\r\n\t\t\t\/\/Again we need to check the size of the subset to ensure we have enough values to return\r\n\t\t\tif(subSet.size() < currentCount-1) continue;\/\/ignore... unfortunately\r\n\r\n\t\t\tif(biggestSize < subSet.size()){\r\n\t\t\t\tbiggestSize = subSet.size();\r\n\t\t\t\tsubSet.add(currentSet.get(i));\r\n\t\t\t\tresult = subSet;\r\n\t\t\t}\r\n\t\t}\r\n\t\treturn result;\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\r\n\t\tint limit = 5;\r\n\r\n\t\tfor(int i=3;i<50;i++){\/\/1000000\r\n\t\t\tBigInteger bi = new BigInteger(\"\"+i);\r\n\t\t\tif(!bi.isProbablePrime(100)) continue;\r\n\r\n\t\t\tVector<BigInteger> validOnes = new Vector<BigInteger>(500);\r\n\t\t\tfor(int j=i+1; j<10000; j++){\/\/1000000\r\n\t\t\t\tBigInteger bj = new BigInteger(\"\"+j);\r\n\t\t\t\tif(!bj.isProbablePrime(100)) continue;\r\n\r\n\t\t\t\tString ij = \"\"+i+j, ji = \"\"+j+i;\r\n\t\t\t\tBigInteger bij = new BigInteger(ij), bji = new BigInteger(ji);\r\n\t\t\t\tif(!bij.isProbablePrime(100) || !bji.isProbablePrime(100)) continue;\r\n\r\n\t\t\t\tvalidOnes.add(bj);\r\n\t\t\t}\r\n\r\n\t\t\tif(validOnes.size() < limit) continue;\/\/Requires at least five elements\r\n\t\t\t\/\/Begin cyclical parsing..\r\n\t\t\tVector<BigInteger> result = parseSet(validOnes, limit-1);\r\n\t\t\tif(result.size() == limit-1){\r\n\t\t\t\tint sum = 0;\r\n\t\t\t\tresult.add(bi);\r\n\t\t\t\tfor(BigInteger a : result){\r\n\t\t\t\t\tsum += a.intValue();\r\n\t\t\t\t\tSystem.out.println(a);\r\n\t\t\t\t}\r\n\t\t\t\tSystem.out.println(\"sum: \"+sum);\r\n\t\t\t\tbreak;\r\n\t\t\t}\r\n\t\t}\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: Unfortunately, the solution didn&#8217;t come to me quickly (took 3-4 days), which is why &#8220;parseSet&#8221; is a pretty ugly mess.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem 60:<br \/>\nThe primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. <\/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\/638"}],"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=638"}],"version-history":[{"count":0,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/638\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/media?parent=638"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/categories?post=638"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/tags?post=638"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}