[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

[QUIZ] Reverse Divisible Numbers (#161

Matthew Moss

5/2/2008 3:28:00 PM

This is a fairly simple quiz this week, as I'm in the middle of
putting together a new website to replace the existing RQ2 website,
which was supposed to be temporary. Hopefully the new one should be in
place next week.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

The three rules of Ruby Quiz 2:

1. Please do not post any solutions or spoiler discussion for this
quiz until 48 hours have passed from the time on this message.

2. Support Ruby Quiz 2 by submitting ideas as often as you can! (A
permanent, new website is in the works for Ruby Quiz 2. Until then,
please visit the temporary website at

<http://matthew.moss.googlepages.co....

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem
helps everyone on Ruby Talk follow the discussion. Please reply to
the original quiz message, if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

Quiz #161
Reverse Divisible Numbers

This week's quiz is borrowed from Jon Galloway (http://ti...
5jvf37).
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
divisible 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.
35 Answers

Ken Bloom

5/2/2008 3:54:00 PM

0

On Fri, 02 May 2008 10:28:00 -0500, Matthew Moss wrote:
> Quiz #161
> Reverse Divisible Numbers
>
> This week's quiz is borrowed from Jon Galloway (http://ti...
> 5jvf37).
> 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
> divisible 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.

Here's what I've found:

1089 * 9 = 9801
2178 * 4 = 8712
10989 * 9 = 98901
21978 * 4 = 87912
109989 * 9 = 989901
219978 * 4 = 879912

real 0m55.234s
user 0m53.995s
sys 0m0.012s

--Ken

--
Ken (Chanoch) Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu...

Rob Biedenharn

5/2/2008 4:44:00 PM

0


On May 2, 2008, at 12:10 PM, Ken Bloom wrote:

> On Fri, 02 May 2008 10:28:00 -0500, Matthew Moss wrote:
>> Quiz #161
>> Reverse Divisible Numbers
>>
>> This week's quiz is borrowed from Jon Galloway
>> (http://tinyurl....).
>> 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
>> divisible 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.
>
> Here's what I've found:
>
> 1089 * 9 = 9801
> 2178 * 4 = 8712
> 10989 * 9 = 98901
> 21978 * 4 = 87912
> 109989 * 9 = 989901
> 219978 * 4 = 879912
>
> real 0m55.234s
> user 0m53.995s
> sys 0m0.012s
>
> --Ken
>
> --
> Ken (Chanoch) Bloom. PhD candidate. Linguistic Cognition Laboratory.
> Department of Computer Science. Illinois Institute of Technology.
> http://www.iit.edu...

2178 * 4 = 8712
1089 * 9 = 9801
21978 * 4 = 87912
10989 * 9 = 98901
219978 * 4 = 879912
109989 * 9 = 989901

real 0m13.113s
user 0m12.411s
sys 0m0.081s

While I find them in a slightly different order, I'm surprised by the
4x speedup. I wonder if there's a better way to post comparisons that
would negate machine differences and focus on algorithmic distinctions
without posting code?

-Rob

Rob Biedenharn http://agileconsult...
Rob@AgileConsultingLLC.com

Matthew Moss

5/2/2008 5:23:00 PM

0


> While I find them in a slightly different order, I'm surprised by the
> 4x speedup. I wonder if there's a better way to post comparisons that
> would negate machine differences and focus on algorithmic distinctions
> without posting code?


Change the upper limit. In addition to one million, try one thousand,
or even one billion. You could probably get a rough estimation of
whether an algorithm is O(n) or O(n^2) that way.

My impression is that everyone should be able to easily get an O(n)
solution. But there should be tricks to trim that down... whether it
will be a simple constant multiplier, or actually getting it down to,
say, O(lg n), I don't know.

Matthew Moss

5/2/2008 5:25:00 PM

0

> 1089 * 9 = 9801
> 2178 * 4 = 8712
> 10989 * 9 = 98901
> 21978 * 4 = 87912
> 109989 * 9 = 989901
> 219978 * 4 = 879912

One of the interesting things I found is that those are all divisible
by 9. I wonder if that is a property of all such numbers?

Shane Emmons

5/2/2008 5:27:00 PM

0

[Note: parts of this message were removed to make it a legal post.]

On Fri, May 2, 2008 at 12:44 PM, Rob Biedenharn <Rob@agileconsultingllc.com>
wrote:

>
> On May 2, 2008, at 12:10 PM, Ken Bloom wrote:
>
> On Fri, 02 May 2008 10:28:00 -0500, Matthew Moss wrote:
> >
> > > Quiz #161
> > > Reverse Divisible Numbers
> > >
> > > This week's quiz is borrowed from Jon Galloway
> > > (http://tinyurl....).
> > > 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
> > > divisible 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.
> > >
> >
> > Here's what I've found:
> >
> > 1089 * 9 = 9801
> > 2178 * 4 = 8712
> > 10989 * 9 = 98901
> > 21978 * 4 = 87912
> > 109989 * 9 = 989901
> > 219978 * 4 = 879912
> >
> > real 0m55.234s
> > user 0m53.995s
> > sys 0m0.012s
> >
> > --Ken
> >
> > --
> > Ken (Chanoch) Bloom. PhD candidate. Linguistic Cognition Laboratory.
> > Department of Computer Science. Illinois Institute of Technology.
> > http://www.iit.edu... <http://www.iit.edu/%7Ekb...
> >
>
> 2178 * 4 = 8712
> 1089 * 9 = 9801
> 21978 * 4 = 87912
> 10989 * 9 = 98901
> 219978 * 4 = 879912
> 109989 * 9 = 989901
>
> real 0m13.113s
> user 0m12.411s
> sys 0m0.081s
>
> While I find them in a slightly different order, I'm surprised by the 4x
> speedup. I wonder if there's a better way to post comparisons that would
> negate machine differences and focus on algorithmic distinctions without
> posting code?
>
> -Rob
>
> Rob Biedenharn http://agileconsult...
> Rob@AgileConsultingLLC.com
>
>
>
H:\personal\RubyQuiz>ptime quiz161.rb

ptime 1.0 for Win32, Freeware - http://www.pc-...
Copyright(C) 2002, Jem Berkes <jberkes@pc-tools.net>

=== quiz161.rb ===
8712
9801
87912
98901
879912
989901

Execution time: 7.691 s

--
Shane Emmons
E: semmons99@gmail.com

ThoML

5/2/2008 5:32:00 PM

0

> real 0m13.113s
> user 0m12.411s
> sys 0m0.081s
>
> While I find them in a slightly different order, I'm surprised by the
> 4x speedup.

Pah!

The maybe much too clever version:
$ time ruby19 q161b.rb
real 0m0.270s
user 0m0.110s
sys 0m0.100s

Or the naive version:
$ time ruby19 q161a.rb
real 0m2.864s
user 0m2.123s
sys 0m0.100s

Matthew Moss

5/2/2008 6:13:00 PM

0



On May 2, 12:25 pm, Matthew Moss <matthew.m...@gmail.com> wrote:
> > 1089 * 9 = 9801
> > 2178 * 4 = 8712
> > 10989 * 9 = 98901
> > 21978 * 4 = 87912
> > 109989 * 9 = 989901
> > 219978 * 4 = 879912
>
> One of the interesting things I found is that those are all divisible
> by 9. I wonder if that is a property of all such numbers?

Actually, I just did a quick-n-dirty proof to myself that this is
actually true.

While not all numbers divisible by 9 are reversible-divisible numbers
(e.g. 81), it is a necessary requirement (still holding to the rules
that the number is not a palindrome and does not end in zero) that the
number be divisible by 9.

So you could save some time by examining only every ninth number.

If anyone is interested in the reason, I'll try and write down my
proof.

Martin DeMello

5/2/2008 6:19:00 PM

0

On Fri, May 2, 2008 at 10:25 AM, Matthew Moss <matthew.moss@gmail.com> wrote:
> > 1089 * 9 = 9801
> > 2178 * 4 = 8712
> > 10989 * 9 = 98901
> > 21978 * 4 = 87912
> > 109989 * 9 = 989901
> > 219978 * 4 = 879912
>
> One of the interesting things I found is that those are all divisible
> by 9. I wonder if that is a property of all such numbers?

Let the numbers be x = a....c and y = c....a

then, if y divides x, so does (x-y)

x = 10^n a + 10b + c
y = 10^n c + 10 d + a

x - y = (a - c)(10^n-1) + 10 (b-d)

the first term obviously divides by 9

for the second term, note that b and d are reversals of each other. It
can be shown that their difference again divides by 9 (again splitting
off the first and last digit as above, or simply by induction on the
number of digits, which come to think of it I should have done from
the beginning)

martin

Shane Emmons

5/2/2008 6:56:00 PM

0

[Note: parts of this message were removed to make it a legal post.]

On Fri, May 2, 2008 at 2:18 PM, Martin DeMello <martindemello@gmail.com>
wrote:

> On Fri, May 2, 2008 at 10:25 AM, Matthew Moss <matthew.moss@gmail.com>
> wrote:
> > > 1089 * 9 = 9801
> > > 2178 * 4 = 8712
> > > 10989 * 9 = 98901
> > > 21978 * 4 = 87912
> > > 109989 * 9 = 989901
> > > 219978 * 4 = 879912
> >
> > One of the interesting things I found is that those are all divisible
> > by 9. I wonder if that is a property of all such numbers?
>
> Let the numbers be x = a....c and y = c....a
>
> then, if y divides x, so does (x-y)
>
> x = 10^n a + 10b + c
> y = 10^n c + 10 d + a
>
> x - y = (a - c)(10^n-1) + 10 (b-d)
>
> the first term obviously divides by 9
>
> for the second term, note that b and d are reversals of each other. It
> can be shown that their difference again divides by 9 (again splitting
> off the first and last digit as above, or simply by induction on the
> number of digits, which come to think of it I should have done from
> the beginning)
>
> martin
>
>
With that info, I was able to get the code to run under 1 sec.

=== c:\ruby-1.9.0\bin\ruby.exe quiz161.rb ===
8712
9801
87912
98901
879912
989901

Execution time: 0.969 s


--
Shane Emmons
E: semmons99@gmail.com

Ken Bloom

5/2/2008 7:29:00 PM

0

On Fri, 02 May 2008 11:44:21 -0500, Rob Biedenharn wrote:

> On May 2, 2008, at 12:10 PM, Ken Bloom wrote:
>
>> On Fri, 02 May 2008 10:28:00 -0500, Matthew Moss wrote:
>>> Quiz #161
>>> Reverse Divisible Numbers
>>>
>>> This week's quiz is borrowed from Jon Galloway
>>> (http://tinyurl....).
>>> 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
>>> divisible 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.
>>
>> Here's what I've found:
>>
>> 1089 * 9 = 9801
>> 2178 * 4 = 8712
>> 10989 * 9 = 98901
>> 21978 * 4 = 87912
>> 109989 * 9 = 989901
>> 219978 * 4 = 879912
>>
>> real 0m55.234s
>> user 0m53.995s
>> sys 0m0.012s
>>
>> --Ken
>>
>> --
>> Ken (Chanoch) Bloom. PhD candidate. Linguistic Cognition Laboratory.
>> Department of Computer Science. Illinois Institute of Technology.
>> http://www.iit.edu...
>
> 2178 * 4 = 8712
> 1089 * 9 = 9801
> 21978 * 4 = 87912
> 10989 * 9 = 98901
> 219978 * 4 = 879912
> 109989 * 9 = 989901
>
> real 0m13.113s
> user 0m12.411s
> sys 0m0.081s
>
> While I find them in a slightly different order, I'm surprised by the 4x
> speedup. I wonder if there's a better way to post comparisons that
> would negate machine differences and focus on algorithmic distinctions
> without posting code?

I did it in a *really* stupid way for my first pass. That's all.

--Ken

--
Ken (Chanoch) Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu...