{"id":261,"date":"2010-10-08T23:26:31","date_gmt":"2010-10-09T03:26:31","guid":{"rendered":"http:\/\/www.peteonsoftware.com\/?p=261"},"modified":"2024-03-02T16:19:59","modified_gmt":"2024-03-02T21:19:59","slug":"project-euler-problem-4","status":"publish","type":"post","link":"https:\/\/www.peteonsoftware.com\/index.php\/2010\/10\/08\/project-euler-problem-4\/","title":{"rendered":"Project Euler Problem 4"},"content":{"rendered":"<p><img decoding=\"async\" src=\"https:\/\/www.peteonsoftware.com\/images\/201010\/TACOCAT.jpg\" alt=\"TACOCAT is a palindrome!\" title=\"TACOCAT is a palindrome!\" style=\"float:left; margin:.5em;\" \/>Continuing on from <a href=\"https:\/\/www.peteonsoftware.com\/index.php\/category\/project-euler\/\">my previous adventures in Euler<\/a>, we now come to problem 4.  Problem 4 asks you to find the largest palindrome that is the product of two 3 digit numbers.<\/p>\n<p>My solution is brute force, and originally, I started two loops both at 999 and counted down, figuring the first palindrome found would be the largest.  I was wrong, however, and was required (sticking to brute force) to check all products for palindromes and just keep the largest.  The &#8220;count backwards&#8221; code returned &#8220;Using 995 and 583, the max palindrome is 580085&#8221;, which is incorrect. My correct code is as follows:<br \/>\n<br style=\"clear:both;\" \/><\/p>\n<pre>\r\nusing System;\r\n\r\nnamespace ProjectEuler\r\n{\r\n\t\/\/\/ &lt;summary&gt;\r\n\t\/\/\/ A palindromic number reads the same both ways. The largest\r\n\t\/\/\/ palindrome made from the product of two 2-digit numbers is \r\n\t\/\/\/  9009 = 91 x 99.\r\n\t\/\/\/ Find the largest palindrome made from the product of two 3-digit numbers.\r\n\t\/\/\/  http:\/\/projecteuler.net\/index.php?section=problems&id=43\r\n\t\/\/\/\r\n\t\/\/\/ The answer is 906609\r\n\t\/\/\/ &lt;\/summary&gt;\r\n\tpublic class Problem4\r\n\t{\r\n\t\tpublic static void Main(string[] args)\r\n\t\t{\r\n\t\t\tvar max = 0;\r\n\t\t\tvar theI = 0;\r\n\t\t\tvar theK = 0;\r\n\t\t\t\r\n\t\t\tfor (var i = 100; i &lt;= 999; i++)\r\n\t\t\t{\r\n\t\t\t\tfor (var k=100; k &lt;= 999; k++)\r\n\t\t\t\t{\r\n\t\t\t\t\tvar product = i * k;\r\n\t\t\t\t\tif (IsPalindrome(product) && product &gt; max)\r\n\t\t\t\t\t{\r\n\t\t\t\t\t\ttheI = i;\r\n\t\t\t\t\t\ttheK = k;\r\n\t\t\t\t\t\tmax = product;\r\n\t\t\t\t\t}\r\n\t\t\t\t}\r\n\t\t\t}\r\n\r\n\t\t\tConsole.WriteLine(\"Using {0} and {1}, the max palindrome is {2}\", theI, theK, max);\r\n\t\t}\r\n\r\n\t\tpublic static bool IsPalindrome(int number)\r\n\t\t{\r\n\t\t\tvar forward = number.ToString();\r\n\t\t\tvar reverse = forward.ToCharArray();\r\n\t\t\tArray.Reverse(reverse);\r\n\r\n\t\t\treturn forward == new string(reverse);\r\n\t\t}\r\n\t}\r\n}\r\n<\/pre>\n<p>That returns &#8220;Using 913 and 993, the max palindrome is 906609&#8221;.<\/p>\n<p>After you put in the correct answer on the Project Euler site, you are allowed to then view the forums to discuss your answers.  I found some interesting math inside that made other algorithms much more efficient.  Here is what I gleaned:<\/p>\n<p>A six digit palindrome would be in the format abccba.  If we take our real answer of 906609, that could also be written as 9(100000) + 0(10000) + 6(1000) + 6(100) + 0(10) + 9(1).  The same way, our generic answer can be written as 100000a+10000b+1000c+100c+10b+1a.  Simplified again, that is 100001a+10010b+1100c.  You can factor 11 out of that, leaving you with 11(9091a + 910b + 100c).  That means that the product would have to be easily divisible by 11 (saving you the lengthy &#8211; by comparison &#8211; palindrome check).  My original algorithm ran in 9.219022 seconds on my Mac Mini running Mono.  When I add in the &#8220;divide by 11 check&#8221; to short-circuit every palindrome comparison, the algorithm now runs in 1.63679 seconds.  That is a HECK of an improvement.  Math&#8230; I think this might just catch on! <\/p>\n","protected":false},"excerpt":{"rendered":"<p>Continuing on from my previous adventures in Euler, we now come to problem 4. Problem 4 asks you to find the largest palindrome that is the product of two 3 digit numbers. My solution is &hellip;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[36],"tags":[53,102],"class_list":["post-261","post","type-post","status-publish","format-standard","hentry","category-project-euler","tag-palindromes","tag-project-euler"],"_links":{"self":[{"href":"https:\/\/www.peteonsoftware.com\/index.php\/wp-json\/wp\/v2\/posts\/261","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.peteonsoftware.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.peteonsoftware.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.peteonsoftware.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.peteonsoftware.com\/index.php\/wp-json\/wp\/v2\/comments?post=261"}],"version-history":[{"count":0,"href":"https:\/\/www.peteonsoftware.com\/index.php\/wp-json\/wp\/v2\/posts\/261\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.peteonsoftware.com\/index.php\/wp-json\/wp\/v2\/media?parent=261"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.peteonsoftware.com\/index.php\/wp-json\/wp\/v2\/categories?post=261"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.peteonsoftware.com\/index.php\/wp-json\/wp\/v2\/tags?post=261"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}