# Bases and palindromes

Published on 2011-07-30Since getting to level 1, I've been doing Euler problems in order of difficulty instead of in the order they're presented on the site. The next one up was problem 36, which asks,

The decimal number, 585 = 1001001001

_{2}(binary), is palindromic in both bases.

Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.

As the problem asks that only the numbers 1-1,000,000 be evaluated, individually testing each one wasn't out of the question. But you can instantly halve the pool of numbers to be tried by realizing that any binary palindrome must start and end with 1's, that is, binary palindromes are necessarily odd. The algorithm need only consider odd numbers, and only numbers beginning with an odd digit in their base-10 representation, at that. The set of odd, base-10 palindromes under one million is considerably smaller than the set of binary palindromes, so only members of the former set should be evaluated to see if they are members of the latter, as well.

using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Problem036 { class Program { static void Main(string[] args) { int total = 0; for (int i = 1; i < 1000000; i += 2) // only odd nums will be binary palindromes { if ((i.ToString()[0] - 48) % 2 == 0) // skips nums beginning with an even digit continue; if (isPalindrome(i) && isBinaryPalindrome(i)) total += i; } Console.WriteLine(total); } private static bool isBinaryPalindrome(int i) { int reverseI = Convert.ToInt32(new string(Convert.ToString(i, 2).Reverse().ToArray()), 2); if (i == reverseI) return true; else return false; } private static bool isPalindrome(int i) { int reverseI = Int32.Parse(new string(i.ToString().Reverse().ToArray())); if (i == reverseI) return true; else return false; } } }