{"id":718,"date":"2012-09-07T15:22:06","date_gmt":"2012-09-07T19:22:06","guid":{"rendered":"http:\/\/www.joshho.com\/blog\/?p=718"},"modified":"2012-09-07T15:59:30","modified_gmt":"2012-09-07T19:59:30","slug":"project-euler-problem-69","status":"publish","type":"post","link":"https:\/\/www.joshho.com\/blog\/2012\/09\/07\/project-euler-problem-69\/","title":{"rendered":"Project Euler &#8211; Problem 69"},"content":{"rendered":"<p>Problem 69: Find the value of n &lt; 1,000,000 for which n\/\u03c6(n) is a maximum.<br \/>\n<!--more--><br \/>\nNote the following:<\/p>\n<p><center><\/p>\n<table border=\"1\">\n<tbody>\n<tr>\n<td>n<\/td>\n<td>\u03c6(n)<\/td>\n<td>n\/\u03c6(n)<\/td>\n<\/tr>\n<tr style=\"background-color: #e5eecc;\">\n<td>2<\/td>\n<td>1<\/td>\n<td>2<\/td>\n<\/tr>\n<tr>\n<td>&#8230;<\/td>\n<td>&#8230;<\/td>\n<td>&#8230;<\/td>\n<\/tr>\n<tr>\n<td>5<\/td>\n<td>4<\/td>\n<td>1.25<\/td>\n<\/tr>\n<tr style=\"background-color: #e5eecc;\">\n<td>6<\/td>\n<td>2<\/td>\n<td>3<\/td>\n<\/tr>\n<tr>\n<td>7<\/td>\n<td>6<\/td>\n<td>1.167<\/td>\n<\/tr>\n<tr>\n<td>&#8230;<\/td>\n<td>&#8230;<\/td>\n<td>&#8230;<\/td>\n<\/tr>\n<tr style=\"background-color: #e5eecc;\">\n<td>30<\/td>\n<td>8<\/td>\n<td>3.75<\/td>\n<\/tr>\n<tr>\n<td>&#8230;<\/td>\n<td>&#8230;<\/td>\n<td>&#8230;<\/td>\n<\/tr>\n<tr style=\"background-color: #e5eecc;\">\n<td>210<\/td>\n<td>48<\/td>\n<td>4.375<\/td>\n<\/tr>\n<tr>\n<td>&#8230;<\/td>\n<td>&#8230;<\/td>\n<td>&#8230;<\/td>\n<\/tr>\n<tr style=\"background-color: #e5eecc;\">\n<td>2310<\/td>\n<td>480<\/td>\n<td>4.8125<\/td>\n<\/tr>\n<tr>\n<td>&#8230;<\/td>\n<td>&#8230;<\/td>\n<td>&#8230;<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>&nbsp;<\/p>\n<p><\/center>The highlighted are the next maximum values of n\/\u03c6(n), as n approaches 10^7.<br \/>\nOne can note from this are the divisors that make up n:<br \/>\nie 2 = 2; 6 = 2&#215;3; 30 = 2x3x5; 210 = 2x3x5x7.. etc<\/p>\n<p>It then becomes trivial to deduce the maximum n\/\u03c6(n) where 1&lt;n&lt;10^7<\/p>\n<p><code><\/p>\n<pre lang=\"java\">\r\n\r\nclass runner\r\n{\t\r\n\tpublic static double findTotient(int nO){\r\n\t\tint n = nO;\r\n\t\tboolean[] result = new boolean[n];\r\n\t\tint i=2;\r\n\t\tdo{\r\n\t\t\tif(n % i == 0){\r\n\t\t\t\tn \/= i;\r\n\t\t\t\tresult[i] = true;\r\n\t\t\t}else{\r\n\t\t\t\tdo{\r\n\t\t\t\t\ti++;\r\n\t\t\t\t}while(i<primeSieve.length &#038;&#038; primeSieve[i]);\r\n\t\t\t}\r\n\t\t}while(n > 1);\r\n\t\t\r\n\t\tdouble calc = nO;\r\n\t\tfor(int k=0; k<result.length; k++){\r\n\t\t\tif(!result[k]) continue;\r\n\t\t\tcalc *= (1 - 1.0\/k);\r\n\t\t}\r\n\t\treturn calc;\r\n\t}\r\n\tpublic static boolean[] primeSieve(int limit){\r\n\t\tboolean[] arr = new boolean[limit];\r\n\t\tarr[0] = true; arr[1] = true;\r\n\r\n\t\tfor(int i=2; i<limit;i++){\r\n\t\t\tif(arr[i]){ continue; }\r\n\t\t\tint j=i+i;\r\n\t\t\twhile(j<arr.length){\r\n\t\t\t\tarr[j] = true;\r\n\t\t\t\tj+=i;\r\n\t\t\t}\r\n\t\t}\r\n\t\treturn arr;\r\n\t}\r\n\r\n\tstatic boolean[] primeSieve;\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 = 2311;\r\n\t\tprimeSieve = primeSieve(limit);\r\n\r\n\t\tdouble b1=0,b2=0;\r\n\t\tfor(int n=2;n<limit;n++){\r\n\t\t\tif(!primeSieve[n]){\r\n\t\t\t\t\/\/System.out.println(n+ \" \"+(n-1));\r\n\t\t\t}else{\t\t\t\t\r\n\t\t\t\tdouble calc = findTotient(n);\r\n\t\t\t\tcalc = n\/calc;\r\n\t\t\t\tif(calc > b2){ b2 = calc; b1=n;}\r\n\t\t\t\/\/System.out.println(n+\" \"+calc);\r\n\t\t\t}\r\n\t\t}\r\n\t\tSystem.out.println(b1+\" \"+b2);\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 69: Find the value of n &lt; 1,000,000 for which n\/\u03c6(n) is a maximum.<\/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-718","post","type-post","status-publish","format-standard","hentry","category-project-euler"],"_links":{"self":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/718","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=718"}],"version-history":[{"count":9,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/718\/revisions"}],"predecessor-version":[{"id":728,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/718\/revisions\/728"}],"wp:attachment":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/media?parent=718"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/categories?post=718"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/tags?post=718"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}