Project Euler 36: Find the sum of all numbers less than one million, which are palindromic in base 10 and base 2

Written by on 16 April 2011

Topics: Project Euler

In Problem 36 of Project Euler we are revisiting palindromic numbers. This time with we need to find numbers which are not only palindromic in base 10 but also in base two, meaning in a binary representation. The problem description reads

The decimal number, 585 = 10010010012 (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.

(Please note that the palindromic number, in either base, may not include leading zeros.)

We already treated palindromic numbers in problem 4 but to be honest I have learned quite a few tricks on how to construct numbers since then. I will take 3 approaches in this post. First I will do like in the solution to problem 4 by making string manipulation to reverse the number and compare it to the original number in both base 2 and 10.

The second step I will build a function which can reverse an integer in any base without converting it to a string.

The last step will be to generate palindromic numbers, so we only have to check if a number is palindromic in the other base.

Brute Force String Comparison

We need a function which can tell us if a number is a palindrome in either base 2 or base 10.  Once I figured out that the Convert.ToString has an option to take a base with it, it was rather easy to generalise the function to any base. What I later discovered was that the string conversion has to be in base 2,8, 10 or 16.

The function converts the integer to a string, copies the string into a char array which is reversed and converted back into a string. The two strings are then compared to see if they match. It takes a total of 4 lines of code in C#

private bool IsPalindromeString(int number, int b) {
    string numm = Convert.ToString(number,b);
    char[] arr = numm.ToCharArray();
    Array.Reverse(arr);
    return numm.Equals(new string(arr));
}

The main loop of the code has a little trick. Since the problem description explicitly states that there are no leading zeroes the last digit cannot be zero, which in base two means that only odd numbers can be palindromes.

The main loop looks like

const int limit = 1000000;
int result = 0;

for (int i = 1; i < limit; i += 2) {
    if (IsPalindromeString(i, 10) && IsPalindromeString(i, 2)) {
        result += i;
    }
}

The code takes 119 ms to come up with the result

The sum of palindromic numbers in base 2 and 10 are 872187
Solution took 119 ms

Brute Force Numeric Comparison

The first approach was similar to the solution of Problem 4 which used string based comparison. I have since then learned a few things and has figured out how to reverse a number so we can keep it all in integer operations.  I have only changed the isPalindrome function which once again takes the number as well as the base of comparison, but this time without limits to which base to choose. The C# code looks like

private bool IsPalindrome(int number, int b){
    int reversed = 0;
    int k = number;

    while (k > 0) {
        reversed = b * reversed + k % b;
        k /= b;
    }
    return number == reversed;
}

We have used the trick multiple times before where we chop of the last digit, only here we do it for an arbitrary base rather than base 10.  The main loop is not changed apart from the name of the IsPalindrome function,  so I will skip that in the post. The result of running this version is

The sum of palindromic numbers in base 2 and 10 are 872187
Solution took 29 ms

So we have chopped off a factor 4 by avoiding string manipulation in the solution.

Generating only Palindromic numbers

There are a million numbers below a million, but only a few of them are actually palindromic. However they have a structure such that we can construct them without missing some of them. The last solution I will present creates the palindromes in base 10 and then checks if the are palindromic in base 2. Thereby we limit the search space siginificantly.

The palindrome creator takes in an input number and a base as well as a boolean telling if the palindrome should have an even or odd number of digits.  It takes the input number, reverses it and appends it to the input number. If the result should have an odd number of digits, it chops off a digit of the reversed part.

It sounds very complicated, but it isn’t really that hard. Let me show you the code

private int createPalindrome(int input, int b, bool isOdd) {
    int n = input;
    int palin = input;
    if (isOdd) {
        n /= b;
    }

    while (n > 0) {
        palin = palin * b + (n % b);
        n /= b;
    }

    return palin;
}

The main function has to be altered somewhat as well.

const int limit = 1000000;
int result = 0;
int number;

for (int j = 0; j < 2; j++) {
    bool isOdd = (j % 2 == 0);
    int i = 1;
    while ((number = createPalindrome(i, 10, isOdd)) < limit) {
        if (IsPalindrome(number, 2)) {
            result += number;
        }
        i++;
    }
}

Instead of checking half a million numbers before we are now checking below 2000 numbers. A significant decrease in the computational demand. And it is pretty obvious from the running time that this is more efficient

The sum of palindromic numbers in base 2 and 10 are 872187
Solution took 0 ms

Wrapping up

In this post I presented three different solutions. Two based on brute force search but with different methods to check if the number is palindromic, both through string manipulation and purely numeric. The last method presented only generated numbers which were palindromic in base 10.

As usual the source code is available in it’s full length if you are interested.

Comments, questions or other solutions are as always very welcome.

11 Comments For This Post I'd Love to Hear Yours!

  1. jerry says:

    My obviously-not-working algorithm has found 18 numbers that are palindrome in both base with a sum of 286602. How many numbers am I missing?

  2. Kristian says:

    Hi Jerry

    According to a quick check of the program there is a total of 19 numbers, and I can see that you are missing the largest number.

    /Kristian

  3. jerry says:

    Thanks for answer. And I solved it! 🙂

    Problem was I didn’t take into account palindromes like 4444,555555. Only palindromes like 543345 (which I created with permutations).

    And by the way, I enjoy reading your explanations of Euler problems. Keep it up!

  4. Shiva says:

    Hi,

    Could you please list out the 19 palindromes. My program generated the following nos. and got the sum as 863178.

    1,3,5,7,9, 33, 99, 313, 585, 717, 7447, 15353, 32223, 39993, 53235, 53835, 73737 and 585585.

    couldn’t find the 19th palindrome 🙁

  5. Kristian says:

    Nope, I wont tell you what it is. But since you have a solution with 18 numbers and therefore only miss one you should be able to figure out the last one.

    /Kristian

    PS: The 18 you got are correct except for one typo.

  6. Shiva says:

    Thanks for the reply 🙂 .I solved it and got the missing palindrome :D.

    Encountered a bug in my base 10 palindrome checking code.9009 is the missing palindrome.

  7. Parvathi says:

    public class Test {

    public static void main(String args[]){
    Test t=new Test();
    System.out.println(“palindrome no’s are:”);
    for(int i=1;i0){
    s=s+(n%2);
    n=n/2;
    }
    return s;
    }

    public String base10(int n){
    String s=””;
    while(n>0){
    s=s+(n%10);
    n=n/10;
    }
    return s;
    }
    }

  8. Dhruvin says:

    #include
    #include
    double pal(double n,double base);
    double bin(double a);
    int main()
    {
    double x,sum=0;
    x=1;
    while(x0)
    {
    m=m*10+fmod(ncl,base);
    ncl=floor(ncl/10);
    }
    if(n==m)
    {
    return 1;
    }
    else
    {
    return 0;
    }
    }
    double bin(double a)
    {
    double q=0;
    double b=0,bcl=b;
    while(a>0)
    {
    bcl=b;
    b=b*10+fmod(a,2);
    if(bcl==b)
    {
    q++;
    }
    a=floor(a/2);
    }
    while(q>0)
    {
    b=b*10;
    q–;
    }
    return b;
    }

    Did everything I can but the last one is not going to be added.

  9. Hossein says:

    Hey ! i have tested my program many times but it’s still wrong 🙁
    can you help me ?!

    =====================================================================

    #include
    #include
    using namespace std ;
    int bin[17],tec[6],per ,c,q;
    unsigned long long sum ;
    bool check ,bincheck ;
    int main ()
    {
    int kaf , sar;
    cin>>kaf;
    cin>>sar;
    for (int i=kaf ; i<sar; i++)
    {
    per =i;
    c=0;

    for (int k=0 ; k=0 ; q–)
    {
    if (tec[q])
    {
    c=floor(q/2);
    break;
    }
    }

    check = true ;

    for (int m=0 ; m<=c;m++)
    {

    if (tec[m]!=tec[q-m])
    {
    check = false ;
    break ;
    }

    }

    if (check)
    {
    bincheck = true ;
    c=0;
    for (int k=0 ; k=0 ; q–)
    {
    if (bin[q])
    {
    c=floor(q/2);
    break;
    }

    }

    for (int j=0 ; j<=c ; j++)
    {
    if (bin[j]!=bin[q-j])
    {
    bincheck=false;
    break;
    }
    }
    if(bincheck)
    {
    sum+=i;
    cout<<i<<endl;
    }

    }

    }
    cout<<sum;
    }

    =====================================================================

  10. as teachers of mathematics we should try by all means of perfecting our pedagogical skills so as to enable our learner benefit and acquire the skills needed for one to survive in society. Many researches today are showing that , most teachers of mathematics are fond of just giving examples and exercise and this is wrong,therefore lets try to make use of problem solving approach.

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.