Code Puzzle #1 - Solution

If you haven't read the puzzle, you can read more about it on my previous post.

The questions:

    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?

A few 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.

We had some great feedback and answers in the comments - of course some of the answers were better than mine.

My Solution:

1. 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?

ANSWER: 6

8712 is divisible by 2178
9801 is divisible by 1089
87912 is divisible by 21978
98901 is divisible by 10989
879912 is divisible by 219978
989901 is divisible by 109989

In case you're curious, there are 6 more between 1 million and 100 million:

8799912 is divisible by 2199978
9899901 is divisible by 1099989
87128712 is divisible by 21782178
87999912 is divisible by 21999978
98019801 is divisible by 10891089
98999901 is divisible by 10999989

2. Write a program to find the answer. I use C#, but feel free to use any programming language you'd like.

Here's my solution; there were some other solutions in the comments that gave the same results.

 

using System;

public class NeverOddOrEven
{
    public static void Main()
    {
        for(int i=1;i<1000000;i++)
        {
            if(i % 10 != 0) //Ignore numbers which end in 0
            {
                int reversed = int.Parse((ReverseUsingCharArrayInline(i.ToString())));
                if(i != reversed && i % reversed == 0) //Ignore palindromes
                    Console.WriteLine("{0} is divisible by {1}", i, reversed);
            }
        }
        Console.WriteLine("Done");
        Console.ReadLine();
    }
    
    //via http://weblogs.asp.net/justin_rogers/archive/2004/06/10/153175.aspx
    private static string ReverseUsingCharArrayInline(string input) {
        char[] reversed = new char[input.Length];
        for(int i = 0, j = reversed.Length - 1; i <= j; i++, j--) {
            reversed[i] = input[j];
            reversed[j] = input[i];
        }
        return new String(reversed);
    }
}

I'm not sure how to grade this question - I'd say it's a pass / fail, but that's just because some of the solutions were better than mine (grin). Alexander Neumer gave the fastest solution, since it does the reverse function numerically rather than converting to strings:

While n > 0
      rev = rev * 10 + (n Mod 10)
      n = n \ 10
  End While

Hmm, I guess I might have tried that if I hadn't made an incorrect assumption about the .NET framework...

3. If you use .NET, you may run into a limitation in the framework that's a little surprising. What is the limitation?

I planned to bang this out in a few lines by converting the int to a string, reversing the string, and converting to int:

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

 Not blazing fast, but it gets the job done. That is, it would if the string class had a Reverse() method. Doh! Justin Rogers had a great comparison of functions which reverse strings a while ago; some of his commenters dug into unsafe code and made it much faster. Mike Mestemaker informed me that VB.NET has a strReverse() function that works well, but Alexander Neumer's solution kept it simple by staying away from strings altogether.

Thanks for playing! We're still waiting on our resident mathematician to explain the interesting patterns in the result; anyone else want to jump in?

9 Comments

  • Another interesting property of those numbers is that they all are divisible by 9.

  • Just wanted to point out a small 'error' in the otherwise very nice function Reverse(Integer).

    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

    Try calling the Reverse function with the number 581. the result will not be whats expected.

    This is becouse 58 / 10 does not return 5, but instead is rounder up to 6.

    One solution is to change the line to:
    n = Math.floor(n \ 10)

    I liked the puzzle btw :)


  • Fun puzzle!

    I had to write it in Ruby, as that's the language I'm trying to gain proficiency in.

    It doesn't run fast, but it was fast to code :).

    #!/usr/bin/env ruby

    class Integer
    def reverse
    r = "#{self}".reverse
    return nil if r =~ /^0/ or r.to_i == self
    return r.to_i
    end
    end

    biggest = 1000000

    (1 .. biggest).each do |n|
    if n.reverse
    puts n if n % n.reverse == 0
    end
    end

  • Shouldn't you be getting results like 100 is divisible by 001?

  • @Helen - Take a look at the puzzle rules. I didn't include them since I don't consider 001 a valid number. I'm sure James Bond might take issue with that.

  • hi your website is very nice i want a little sorry the solution for this puzzle
    "I live in water,if you cut my head iam at your door,if you cut my tail iam a fruit , if you cut both then iam with you"

    please send me the solution for this

  • @angel - The answer is a pearl. http://dan.hersam.com/riddles.html

  • From the Python command prompt:

    >>> for n in xrange(1000000):
    ... if n%10==0: continue
    ... r=int(str(n)[::-1])
    ... if n==r: continue
    ... if n%r==0: print n
    ...
    8712
    9801
    87912
    98901
    879912
    989901
    >>>

  • @angel It would be pearl.

Comments have been disabled for this content.