{"id":616,"date":"2012-08-09T15:00:10","date_gmt":"2012-08-09T19:00:10","guid":{"rendered":"http:\/\/www.joshho.com\/blog\/?p=616"},"modified":"2012-09-07T16:07:30","modified_gmt":"2012-09-07T20:07:30","slug":"project-euler-problem-55","status":"publish","type":"post","link":"https:\/\/www.joshho.com\/blog\/2012\/08\/09\/project-euler-problem-55\/","title":{"rendered":"Project Euler &#8211; Problem 55"},"content":{"rendered":"<p>Problem 55:<br \/>\nA Lychrel number is a natural number which cannot form a palindrome through the iterative process of repeatedly reversing its base 10 digits and adding the resulting numbers.<\/p>\n<p>Assume that after 50 steps of running the above iterative process, the number is deemed Lychrel&#8230;<\/p>\n<p>How many Lychrel numbers are there below ten-thousand?<br \/>\n<!--more--><br \/>\n<code><\/p>\n<pre lang='java'>\r\npackage runner;\r\n\r\nimport java.math.BigInteger;\r\n\r\nclass runner\r\n{\t\r\n\tpublic static boolean isPalindrome(String s){\r\n\t\tfor(int j=0;j<s.length()\/2;j++){\r\n\t\t\tif(s.charAt(j) != s.charAt(s.length()-j-1))\r\n\t\t\t\treturn false;\r\n\t\t}\r\n\t\treturn true;\r\n\t}\r\n\t\r\n\tpublic static String reverse(String s){\r\n\t\tStringBuffer x = new StringBuffer();\r\n\t\tfor(int j=s.length()-1;j>-1;j--){\r\n\t\t\tx.append(s.charAt(j));\r\n\t\t}\r\n\t\treturn x.toString();\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\t\t\r\n\t\tboolean[] isLychrel = new boolean[10000];\r\n\t\t\r\n\t\tfor(int n=0;n<isLychrel.length;n++){\r\n\t\t\tif(isLychrel[n]) continue;\r\n\t\t\tString current = \"\"+n;\r\n\t\t\t\r\n\t\t\tint[] removal = new int[50]; \r\n\t\t\tboolean foundPalin = false;\r\n\t\t\t\r\n\t\t\tBigInteger sum = new BigInteger(current);\r\n\t\t\tString sumString = sum.toString();\r\n\t\t\tint k=0;\r\n\t\t\tfor(int i=0;i<50;i++){\r\n\t\t\t\tif(sumString.length() < 5){\r\n\t\t\t\t\tremoval[k++] = sum.intValue();\r\n\t\t\t\t}\r\n\t\t\t\t\r\n\t\t\t\tString reverseSumStr = reverse(sumString);\r\n\t\t\t\tBigInteger reverseSum = new BigInteger(reverseSumStr);\r\n\t\t\t\t\r\n\t\t\t\tif(reverseSumStr.length() < 5){\r\n\t\t\t\t\t\/\/This check is needed to remove issues like 10->01 (where 01 !->10)\r\n\t\t\t\t\tif(reverseSum.toString().length() == sumString.length())\r\n\t\t\t\t\t\tremoval[k++] = reverseSum.intValue();\r\n\t\t\t\t}\r\n\t\t\t\t\r\n\t\t\t\tsum = sum.add(reverseSum);\r\n\t\t\t\tsumString = sum.toString();\r\n\t\t\t\tif(isPalindrome(sumString)){\r\n\t\t\t\t\tfoundPalin = true;\r\n\t\t\t\t\tbreak;\r\n\t\t\t\t}\r\n\t\t\t}\r\n\t\t\t\r\n\t\t\tif(foundPalin){\r\n\t\t\t\tfor(int i=0;i<removal.length;i++){\r\n\t\t\t\t\tisLychrel[removal[i]] = true;\r\n\t\t\t\t}\r\n\t\t\t}\r\n\t\t}\r\n\t\t\r\n\t\tint c = 0;\r\n\t\tfor(int n=1;n<isLychrel.length;n++){\r\n\t\t\tif(!isLychrel[n]) c++;\r\n\t\t}\r\n\t\tSystem.out.println(\"c:\"+c);\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 55:<br \/>\nA Lychrel number is a natural number which cannot form a palindrome through the iterative process of repeatedly reversing its base 10 digits and adding the resulting numbers.<\/p>\n<p>Assume that after 50 steps of running the above iterative process, the number is deemed Lychrel&#8230;<\/p>\n<p>How many Lychrel numbers are there below ten-thousand?<\/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\/616"}],"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=616"}],"version-history":[{"count":0,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/616\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/media?parent=616"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/categories?post=616"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/tags?post=616"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}