# Reverse Divisible Numbers (#161) **URL:** \ **Category:** Ruby\ **Created:** [May 8, 2008, 8:34pm UTC](https://www.ruby-forum.com/t/reverse-divisible-numbers-161/137084 "2008-05-08T20:34:22Z")\ **Posts on this page:** 2\ **Page:** 1
**Author:** ![mansfiem](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/fbc32d/32.png) [@mansfiem](https://www.ruby-forum.com/u/mansfiem)\ **Post date:** [May 8, 2008, 8:34pm UTC](https://www.ruby-forum.com/t/reverse-divisible-numbers-161/137084/1 "2008-05-08T20:34:22Z")
NOTE: I haven’t updated the current (temporary) website, as I’m just about done with the first rev of a new (temporary) website. The new website is still not quite where I want it to be, but far more maintainable than the current. I have a bit more to do today to make it presentable, and I’ll provide the new url either later today, or tomorrow morning. On to the 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 here. ``` 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 Q., 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 few alternative 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. ---
**Author:** ![mansfiem](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/fbc32d/32.png) [@mansfiem](https://www.ruby-forum.com/u/mansfiem)\ **Post date:** [May 9, 2008, 5:25am UTC](https://www.ruby-forum.com/t/reverse-divisible-numbers-161/137084/2 "2008-05-09T05:25:37Z")
> 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. They may be incomplete (although I’m not so sure this is true for marcelo’s approach) but at least they find some numbers in finite time.