{"id":602,"date":"2012-08-08T16:17:37","date_gmt":"2012-08-08T20:17:37","guid":{"rendered":"http:\/\/www.joshho.com\/blog\/?p=602"},"modified":"2012-09-07T16:08:32","modified_gmt":"2012-09-07T20:08:32","slug":"project-euler-problem-51","status":"publish","type":"post","link":"https:\/\/www.joshho.com\/blog\/2012\/08\/08\/project-euler-problem-51\/","title":{"rendered":"Project Euler &#8211; Problem 51"},"content":{"rendered":"<p>Problem 51:<br \/>\nBy replacing the 1st digit of *3, it turns out that six of the nine possible values: 13, 23, 43, 53, 73, and 83, are all prime.<\/p>\n<p>By replacing the 3rd and 4th digits of 56**3 with the same digit, this 5-digit number is the first example having seven primes among the ten generated numbers, yielding the family: 56003, 56113, 56333, 56443, 56663, 56773, and 56993. Consequently 56003, being the first member of this family, is the smallest prime with this property.<\/p>\n<p>Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime value family.<br \/>\n<!--more--><br \/>\n<code><\/p>\n<pre lang='java'>\r\nimport java.util.HashSet;\r\n\r\nclass runner\r\n{\r\n\t\/* \r\n\t * Sieve to determine composite\/prime numbers\r\n\t * My attempt at optimizing mainly is made up of checking values of \r\n\t *    n*n, n*n+2*n, .. length \r\n\t * This reduces the execution time for arr.length=1mil from 30ms to 16ms.\r\n\t *\/\r\n\tprivate static int sieveArray(boolean[] arr){\r\n\t\tarr[0]=true;arr[1]=true;\r\n\t\tint c=2;\r\n\t\tfor(int j = 4; j < arr.length; j+=2){\r\n\t\t\tarr[j] = true;\r\n\t\t\tc++;\r\n\t\t}\r\n\t\t\r\n\t\tfor(int i=3;i<Math.sqrt(arr.length);i+=2){\r\n\t\t\tif(arr[i]) continue;\r\n\t\t\tint ii = 2 * i;\r\n\t\t\tfor(int j = i*i; j < arr.length; j+=ii){\r\n\t\t\t\tif(arr[j]) continue;\r\n\t\t\t\tarr[j] = true;\r\n\t\t\t\tc++;\r\n\t\t\t}\r\n\t\t}\r\n\t\treturn arr.length - c;\r\n\t}\r\n\t\/\/private static int[] convertArr(int n, boolean[] arr2){\r\n\tprivate static HashSet<String> convertArr(int n, boolean[] arr2){\r\n\t\t\/\/int[] arr = new int[n];\r\n\t\tHashSet<String> arr = new HashSet<String>();\r\n\t\t\/\/int k=0;\r\n\t\tfor(int i=0;i<arr2.length;i++){\r\n\t\t\tif(!arr2[i]){\r\n\t\t\t\t\/\/arr[k++] = i;\r\n\t\t\t\tarr.add(i+\"\");\r\n\t\t\t}\r\n\t\t}\r\n\t\treturn arr;\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\r\n\t\tboolean[] primesieve = new boolean[1000000];\/\/000\r\n\t\tint numOfPrimes = sieveArray(primesieve);\r\n\t\tSystem.out.println(\"sieveArray time: \"+(System.currentTimeMillis() - time));\r\n\t\t\r\n\t\t\/\/Used HashSet to exploit the log(n) \"contains\" check speed.\r\n\t\tHashSet<String> primes = convertArr(numOfPrimes, primesieve);\r\n\t\tSystem.out.println(\"convertArr time: \"+(System.currentTimeMillis() - time));\r\n\t\t\r\n\t\tprimesieve = null;\r\n\t\tSystem.gc();\r\n\t\t\r\n\t\tint lfamily = 0;\r\n\t\tString lp = \"9999999999\";\r\n\t\tfor(String p: primes){\/\/For Each Prime\t\t\t\r\n\t\t\tfor(int i=0;i<10;i++){\/\/iterate from 0..9\r\n\t\t\t\tint family = 1;\r\n\t\t\t\t\r\n\t\t\t\tfor(int j=1;j<10;j++){\/\/Push 0+1... 0+9 [1..9] \r\n\t\t\t\t\tchar newChar = (char)(48+((i+j)%10));\r\n\t\t\t\t\t\r\n\t\t\t\t\tboolean found = false;\r\n\t\t\t\t\tStringBuffer check = new StringBuffer();\r\n\t\t\t\t\t\r\n\t\t\t\t\tfor(int k=0;k<p.length();k++){\/\/For Each Character in String\r\n\t\t\t\t\t\tif(p.charAt(k) == i+48){\r\n\t\t\t\t\t\t\tcheck.append(newChar);\r\n\t\t\t\t\t\t\tfound = true;\r\n\t\t\t\t\t\t}else{\r\n\t\t\t\t\t\t\tcheck.append(p.charAt(k));\r\n\t\t\t\t\t\t}\r\n\t\t\t\t\t}\r\n\t\t\t\t\t\r\n\t\t\t\t\tif(found &#038;&#038; primes.contains(check.toString())){\r\n\t\t\t\t\t\tfamily++;\r\n\t\t\t\t\t}\r\n\t\t\t\t}\r\n\t\t\t\t\r\n\t\t\t\tif(family > lfamily){\r\n\t\t\t\t\tlfamily = family;\r\n\t\t\t\t\tlp=p;\r\n\t\t\t\t}else if(family == lfamily){\r\n\t\t\t\t\tif(p.compareTo(lp) < 0){\r\n\t\t\t\t\t\tlp = p;\r\n\t\t\t\t\t}\r\n\t\t\t\t}\r\n\t\t\t}\r\n\t\t}\r\n\t\tSystem.out.println(\"lp:\"+lp+\" len:\"+lfamily);\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 51:<br \/>\nBy replacing the 1st digit of *3, it turns out that six of the nine possible values: 13, 23, 43, 53, 73, and 83, are all prime.<\/p>\n<p>By replacing the 3rd and 4th digits of 56**3 with the same digit, this 5-digit number is the first example having seven primes among the ten generated numbers, yielding the family: 56003, 56113, 56333, 56443, 56663, 56773, and 56993. Consequently 56003, being the first member of this family, is the smallest prime with this property.<\/p>\n<p>Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime value family.<\/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-602","post","type-post","status-publish","format-standard","hentry","category-project-euler"],"_links":{"self":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/602","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=602"}],"version-history":[{"count":4,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/602\/revisions"}],"predecessor-version":[{"id":749,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/602\/revisions\/749"}],"wp:attachment":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/media?parent=602"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/categories?post=602"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/tags?post=602"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}