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

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.

Published Wednesday, November 8, 2006 12:19 AM by Jon Galloway

Comments

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

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.

Wednesday, November 8, 2006 4:38 AM by jayson knight

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

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

Wednesday, November 8, 2006 6:36 AM by Alexander Neumer

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

Yes, six, but what an interesting six!

Wednesday, November 8, 2006 9:49 AM by Ian Horwill

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

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

Wednesday, November 8, 2006 9:50 AM by Jesse Hansen

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

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

Wednesday, November 8, 2006 11:43 AM by Ian Horwill

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

I initially tried to reverse the numbers by converting them to strings and reversing them:

j=(int)i.ToString().Reverse();

That doesn't work.

Wednesday, November 8, 2006 11:55 AM by Jon Galloway

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

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.

Wednesday, November 8, 2006 12:33 PM by Mike Mestemaker

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

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

Wednesday, November 8, 2006 3:28 PM by jayson knight

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

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.

Thursday, November 9, 2006 5:04 PM by Haacked

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

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.

Thursday, November 9, 2006 5:38 PM by jayson knight

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

       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);

           }

       }

Friday, August 24, 2007 3:46 PM by rtbailey

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

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

Friday, August 24, 2007 3:47 PM by rtbailey