## Code Puzzle #1 - Solution

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

The questions:

- (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?
- Write a program to find the answer. I use C#, but feel free to use any programming language you'd like.
- 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:

- We don't count numbers which are palindromes. Of course 42124 is divisible by 42124, but where's the fun in that?
- 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 109989In 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?

## # re: Code Puzzle #1 - Solution

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

## # re: Code Puzzle #1 - Solution

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

## # re: Code Puzzle #1 - Solution

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

## # re: Code Puzzle #1 - Solution

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

## # re: Code Puzzle #1 - Solution

@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.

## # a little help please

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

## # re: Code Puzzle #1 - Solution

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

## # re: Code Puzzle #1 - Solution

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

>>>

## # re: Code Puzzle #1 - Solution

@angel It would be pearl.