{"id":596,"date":"2012-08-07T13:31:35","date_gmt":"2012-08-07T17:31:35","guid":{"rendered":"http:\/\/www.joshho.com\/blog\/?p=596"},"modified":"2012-09-07T16:09:02","modified_gmt":"2012-09-07T20:09:02","slug":"project-euler-problem-49","status":"publish","type":"post","link":"https:\/\/www.joshho.com\/blog\/2012\/08\/07\/project-euler-problem-49\/","title":{"rendered":"Project Euler &#8211; Problem 49"},"content":{"rendered":"<p>Problem 49:<br \/>\nThe arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.<\/p>\n<p>There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.<\/p>\n<p>What 12-digit number do you form by concatenating the three terms in this sequence?<br \/>\n<!--more--><br \/>\n<code><\/p>\n<pre lang='java'>\r\nimport java.util.Collections;\r\nimport java.util.LinkedHashSet;\r\nimport java.util.Vector;\r\n\r\nclass runner\r\n{\r\n\tpublic static boolean isPrime(int n){\r\n\t\tif(primes.contains(n)) return true;\r\n\t\tdouble limit = Math.sqrt(n);\r\n\t\tfor(int p: primes){\r\n\t\t\tif(p > limit) break;\r\n\t\t\tif(n % p == 0) return false;\r\n\t\t}\r\n\t\tprimes.add(n);\r\n\t\treturn true;\r\n\t}\r\n\r\n\t\/\/Concept from Steinhaus\u2013Johnson\u2013Trotter\r\n\tpublic static void permute(String obj, Vector<String> arr){\r\n\t\tif(arr.size() == 0){\r\n\t\t\tarr.add(obj); \r\n\t\t\treturn;\r\n\t\t}\r\n\t\tVector<String> result = new Vector<String>();\r\n\r\n\t\tfor(String str: arr){\r\n\t\t\tfor(int i=0;i<str.length();i++){\r\n\t\t\t\tString pre = (i==0) ? \"\" : str.substring(0,i);\r\n\t\t\t\tString x = pre+obj+str.substring(i);\r\n\t\t\t\tresult.add(x);\r\n\t\t\t}\r\n\t\t\tString x = str.substring(0,str.length())+obj;\r\n\t\t\tresult.add(x);\r\n\t\t}\r\n\r\n\t\tarr.clear();\r\n\t\tarr.addAll(result);\r\n\t}\r\n\r\n\tstatic Vector<Integer> primes = new Vector<Integer>();\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\tprimes.add(2);\r\n\t\tfor(int i=3; i<=9999; i++){\r\n\t\t\tisPrime(i);\/\/populate prime array\r\n\t\t}\r\n\r\n\t\tfor(int n : primes){\r\n\t\t\tString cur = \"\"+n;\r\n\t\t\tif(cur.length() != 4) continue;\r\n\t\t\tVector<String> permutations = new Vector<String>();\r\n\t\t\tfor(int i=0;i<cur.length();i++){\r\n\t\t\t\tpermute(cur.substring(i,i+1), permutations);\r\n\t\t\t}\r\n\t\t\tCollections.sort(permutations);\r\n\t\t\tLinkedHashSet<Integer> permuteAndPrimeSet = new LinkedHashSet<Integer>();\r\n\t\t\tfor(String str : permutations){\r\n\t\t\t\tint i = Integer.valueOf(str);\r\n\t\t\t\tif(i\/1000 == 0 || i < n) continue;\r\n\t\t\t\tif(primes.contains(i)) permuteAndPrimeSet.add(i);\r\n\t\t\t}\r\n\t\t\tif(permuteAndPrimeSet.size() < 3) continue;\r\n\t\t\t\/\/[1013, 1031, 1103, 1301, 3011]\r\n\t\t\tObject[] permuteAndPrime = permuteAndPrimeSet.toArray();\r\n\t\t\t\r\n\t\t\tfor(int j=1; j<permuteAndPrime.length-1; j++){\r\n\t\t\t\tint diff = (Integer) permuteAndPrime[j] - (Integer) permuteAndPrime[0];\r\n\t\t\t\tfor(int k=j+1; k<permuteAndPrime.length; k++){\r\n\t\t\t\t\tif(((Integer) permuteAndPrime[k] - (Integer) permuteAndPrime[j]) == diff){\r\n\t\t\t\t\t\tSystem.out.println(permuteAndPrime[0] + \" \" + permuteAndPrime[j] + \" \" + permuteAndPrime[k] + \" diff: \"+diff);\r\n\t\t\t\t\t}\r\n\t\t\t\t}\r\n\t\t\t}\r\n\t\t}\r\n\r\n\r\n\t\tSystem.out.println(\"time: \"+(System.currentTimeMillis() - time));\r\n\t}\r\n}\r\n<\/pre>\n<p><\/code><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem 49:<br \/>\nThe arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.<\/p>\n<p>There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.<\/p>\n<p>What 12-digit number do you form by concatenating the three terms in this sequence?<\/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\/596"}],"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=596"}],"version-history":[{"count":0,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/596\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/media?parent=596"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/categories?post=596"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/tags?post=596"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}