Code Puzzle #1 - What numbers under one million are divisible by their reverse?

The other day I got stuck waiting in a slow line at the store all hopped up on espresso and breakbeat, so I started trying to think of numbers which are evenly divisible by their reverse. Example: If 721 were divisble by 127, I'd have a match. Yes, I'm aware this is not normal behavior.

I quickly convinced myself that there were no numbers like that under 1000, but I was sure there had to be some higher numbers like that. Seemed like a pretty simple thing to figure out with a few lines of code, which I did once I got home. As I recently discussed with Phil, I think that sort of thing is a lot more interesting as a quiz then a boring post with a block of code, so here it is.

I'm giving this quiz a difficulty rating of: Easy Peasy

First, some simple ground rules:

  1. We don't count numbers which are palindromes. Of course 42124 is divisible by 42124, but where's the fun in that?
  2. We don't count numbers which end in 0, since their reverse will drop the zero and that's not what I'm looking for. If we didn't have that rule, we'd have to deal with things like 2000 -> 0002, which only works because we'd drop the leading zeros. Lame.

Now, the quiz:

  1. (Answer this first) Take a guess - how many numbers do you think there are between 1 and 1 million that are divisible by their reverse. Any? Fifty? A thousand?
  2. Write a program to find the answer. I use C#, but feel free to use any programming language you'd like.
  3. If you use .NET, you may run into a limitation in the framework that's a little surprising.1 What is the limitation?

I made a tactical error on my recent SQL Puzzle by posting the answer immediately after the question, assuming people would still take the quiz. I was shown the error of my ways by friends who said they weren't going to bother figuring it out when the answer was right there... No honor system this time - I'll post my solution 24(ish) hours from now.

UPDATE: See my solution and recap here.

1Don't worry, you shouldn't have any problem finding some code to work around this.

12 Comments

  • Don't know if you're doing this, but make sure you moderate comments posting an answer, then unmod them right before you post your solution.

    My initial guess is zero. Off to code now.

  • Actually, its 6:
    8712
    9801
    87912
    98901
    879912
    989901

    My program is not very optimised - but nevertheless fast enough ;-)

    Function Reverse(ByVal n As Integer) As Integer
    Dim rev As Integer = 0
    While n > 0
    rev = rev * 10 + (n Mod 10)
    n = n \ 10
    End While
    Return rev
    End Function

    Sub Main()
    Dim I As Integer
    For I = 1 To 999999
    Dim J As Integer = Reverse(I)
    If I J And I Mod 10 0 And I Mod J = 0 Then Console.WriteLine(I)
    Next
    Console.ReadLine()
    End Sub

  • Yes, six, but what an interesting six!

  • I coded the answer in C#, but I can't get the limitation you allude to. What is it?

  • Sorry, should have said click my link to see my solution (in VB.NET).

  • I initially tried to reverse the numbers by converting them to strings and reversing them:
    j=(int)i.ToString().Reverse();

    That doesn't work.

  • In vb.net, reversing the string this way does work:

    j=cint(strReverse(cstr(i))

    But, the first commenter's numeric Reverse function runs much faster:

    Function Reverse(ByVal n As Integer) As Integer
    Dim rev As Integer = 0
    While n > 0
    rev = rev * 10 + (n Mod 10)
    n = n \ 10
    End While
    Return rev
    End Function

    359ms vs. 1450ms for the full scan.

  • Yeah, all divisors are either 4 or 9...now we just need to get the haack-man to give us a proof.

  • A theorem would be "All non-trivial numbers divisible by their reverse, will also be divisible by 9."

    Let's call that the "Haack Theorem". Maybe I can prove that later.

  • Another theorem would be "Where non-trivial number is Y, and is evenly divisible by it's reverse X, X has to be multiplied by either 4 or 9 to get Y."

    Y = Y.Reverse *(4 || 9) // though I don't see a pattern offhand to see what dictates it being either 4 or 9, but it seems to always be one or the other.

  • static void Reversable(int a, int b)
    {
    if (a > b)
    Reversable(b, a);
    else
    {
    string s = a.ToString();
    int j = s.Length - 1;
    //check for leading 0
    if (s[j] != '0')
    {
    char[] c = new char[10];
    int i = 0;
    do
    {
    c[i] = s[j - i];
    } while (++i <= j);
    i = (int)Convert.ToInt64(new string(c));
    //check for palindromes (a != i)
    if ((a % i == 0) && (a != i))
    Console.WriteLine(a);
    }
    if (a == b)
    return;
    Reversable(a + 1, b);
    }
    }

  • From Vinh Doan in my company:
    Public Sub r(ByVal x As Integer, ByVal y As Integer)

    Do

    Dim s As String = StrReverse(x.ToString())

    If (Not s.StartsWith("0") AndAlso Not (x = CInt(s)) AndAlso x Mod CInt(s) = 0) Then Console.WriteLine(x)

    x += 1

    Loop Until (x > y)

    End Sub

Comments have been disabled for this content.