161 Reverse Divisible Numbers

Description

This week’s quiz is borrowed from Jon Galloway. Don’t read the comments or solution there without trying this first!

Your task is to write a bit of Ruby code that will find and report all integers that are divisible by their reverse. For example, 9801 is divisble by 1089.

Your script should accept a single, optional argument to specify the upper limit of your search. If not provided, the default should be one million.

There are two extra rules for finding these “reverse divisible” numbers:

  1. Don’t count palindromes; they are obviously reverse-divisible.

  2. Don’t count numbers ending with zero. Reversing such numbers forces you to drop leading zeros on the divisor, and that’s not as much fun.

Summary

The heart of this week’s quiz is two very simple problems: how to reverse a number, and how to determine whether one number is divisible by another. Robert’s implementation was the shortest at about five lines of code, which we’ll look at first.

limit = (ARGV.shift or 1_000_000).to_i

The first line of Robert’s solution (shown here with one minor change, to provide the default as specified in the quiz description) is an easy way to get a single argument, or provide a default if no argument is available, and convert it to an integer. Most folks had something similar to this, yet in experimentation as I began writing this summary, it falls down when an argument is provided but cannot be converted to an integer. In such a case, method to_i simply returns zero.

That doesn’t really hurt anyone here; the scripts provided will just never execute their loops and provide no output; the only exception I noticed was Sandro’s explicit check to see if to_i returned zero. Now, we generally don’t worry that much about error checking during Ruby Quiz, but I began to wonder if it was really that difficult to get argument input correct without bringing in an argument processing module.

The following will assign an integer value to limit, either the program argument or the default, or will throw an exception if the program argument is not convertible to an integer:

limit = Integer(ARGV.shift || 1_000_000)

Strangely, here is what I actually tried first; I believed should be the same, but it doesn’t even compile:

limit = Integer(ARGV.shift or 1_000_000)

I’m assuming that this is some sort of operator precedence issue, but I don’t understand the problem. (Comments and explanations welcome.)

Back to the quiz… here’s the rest of Robert’s solution:

21.upto limit do |n|
  r = n.to_s.reverse.to_i
  n % r == 0 and n % 10 != 0 and r != n and puts n
end  

Aside from the curious choice of 21 as a starting point, this is a straightforward loop counting up to the limit, checking each number in turn.

First, the number is reversed. Most everyone had the same process for reversing a number: convert to string, reverse the string, convert back to integer. It makes sense and, in the case of Ruby, is probably the fastest.

Robert next performs three checks. First (from left to right), a check is made to see if the remainder of division would be zero; this implies r divides n. Second, a check to see if the remainder of division by ten would not be zero; this enforces an extra rule of the quiz, that numbers not end in zero. Third, to enforce the other extra rule, Robert ensures that the number and its reverse are not equal (i.e. they are not palindromes).

Finally, if all those conditions hold, the short-circuited and operators then ensure puts n is evaluated. It’s an interesting technique, though not one I’ve like myself. For me, it mixes “acting” with “observing” more than necessary; I much would prefer:

  puts n if (n % r == 0 and n % 10 != 0 and r != n)

But that’s mostly personal taste.

The rest of the discussion was primarily spent on two things: speed and a fewalternative methods. Because the problem was rather simple, output and performance results were posted to the discussion within an hour of the quiz itself. Straightforward solutions were O(n) solutions, which meant that performance differences were a matter of the equipment involved (i.e. hardware and, to a lesser degree, operating system and Ruby build).

It was immediately apparent, though, that there should be some ways to reduce the set of numbers examined. For an upper limit of one million, there are only six reverse divisible numbers to be found:

8712
9801
87912
98901
879912
989901

It was pretty apparent that all of these numbers are divisible by nine, and an informal proof showed that any reverse divisible number had to be also divisible by nine. That immediately reduced the search set by nearly an order of magnitude, and the posted timings reflected this. Still, even with the domain reduced by an order of magnitude, that is far more numbers to check than actually satisfy the problem.

Marcelo, Thomas and Harry began to examine the visual patterns of the numbers, noting that there were arrangements of 8712 and 9801 (and their reverses) that repeated themselves in larger numbers. Their solutions reflect this approach, yet they admit to being incomplete solutions: they don’t find every reverse divisible number.

But they are extremely fast at not finding every number! Such solutions beg to me to work further on analyzing the patterns and determining properties of these reverse divisible numbers. If I don’t put out a quiz tomorrow, you’ll know where I am.


Wednesday, February 04, 2009