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 Q. 2:
-
Please do not post any solutions or spoiler discussion for this
quiz until 48 hours have passed from the time on this message.
-
Support Ruby Q. 2 by submitting ideas as often as you can! (A
permanent, new website is in the works for Ruby Q. 2. Until then,
please visit the temporary website at
http://matthew.moss.googlepages.com/home.
-
Enjoy!
Suggestion: A [QUIZ] in the subject of emails about the problem
helps everyone on Ruby T. 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://tinyurl.com/
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:
- Don’t count palindromes; they are obviously reverse-divisible.
- 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.
On Fri, 02 May 2008 10:28:00 -0500, Matthew M. wrote:
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:
- 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
On May 2, 2008, at 12:10 PM, Ken B. wrote:
integers that are divisible by their reverse. For example, 9801 is
- Don’t count palindromes; they are obviously reverse-divisible. 2.
109989 * 9 = 989901
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/
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 B. http://agileconsultingllc.com
[email protected]
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.
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?
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
On Fri, May 2, 2008 at 12:44 PM, Rob B.
[email protected]
wrote:
Don’t read the comments or solution there without trying this first!
There are two extra rules for finding these “reverse divisible”
1089 * 9 = 9801
–Ken
10989 * 9 = 98901
posting code?
-Rob
Rob B. http://agileconsultingllc.com
[email protected]
H:\personal\RubyQuiz>ptime quiz161.rb
ptime 1.0 for Win32, Freeware - http://www.pc-tools.net/
Copyright(C) 2002, Jem B. [email protected]
=== quiz161.rb ===
8712
9801
87912
98901
879912
989901
Execution time: 7.691 s
On Fri, May 2, 2008 at 10:25 AM, Matthew M. [email protected]
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
On May 2, 12:25 pm, Matthew M. [email protected] 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.
On Fri, 02 May 2008 11:44:21 -0500, Rob B. wrote:
Your task is to write a bit of Ruby code that will find and report all
21978 * 4 = 87912
Ken (Chanoch) Bloom. PhD candidate. Linguistic Cognition Laboratory.
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
On Fri, May 2, 2008 at 2:18 PM, Martin DeMello [email protected]
wrote:
by 9. I wonder if that is a property of all such numbers?
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
On Fri, 02 May 2008 13:18:37 -0500, Martin DeMello wrote:
by 9. I wonder if that is a property of all such numbers?
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
I think this may fall into the category of a spoiler.
–Ken
Here’s mine at the moment:
real 0m0.338s
user 0m0.315s
sys 0m0.008s
(MacbookPro 2.33GHz Core2 Duo)
On May 2, 2:40 pm, Ken B. [email protected] wrote:
One of the interesting things I found is that those are all divisible
I think this may fall into the category of a spoiler.
Perhaps… though for most folks, they’ll still have to write the Ruby
code to test any particular integer in that subset. It may run faster,
but there’s still code to be written…
Though, while running my code up to 100,000,000, I’m beginning to
notice other very distinct patterns that would greatly limit the
subset to examine much more than what the current discussion
describes. That may be too much of a spoiler, so I won’t go into it
now.
But this solution is not finding
Yes, much-too-clever version 1 doesn’t scale. Anyway, I still suspect
though you could use some interesting shortcuts.
On Fri, May 2, 2008 at 11:35 AM, ThoML [email protected] wrote:
$ time ruby19 q161b.rb
real 0m0.270s
user 0m0.110s
sys 0m0.100s
$ time reverse_divisible 2_000_000
n=1089 m=9801
n=2178 m=8712
n=10989 m=98901
n=21978 m=87912
n=109989 m=989901
n=219978 m=879912
n=1099989 m=9899901
real 0m0.026s
user 0m0.008s
sys 0m0.020s
But this solution is not finding 21782178 
Marcelo
you could use some interesting shortcuts.
I probably don’t have the time to prove my mtc2 works correctly. So I
simply ask if somebody can verify this or gets different results
(well, this is not the proper way to find a solution I know but …):
For 10000000000000000, I get
$ time ruby19 q161b.rb 10000000000000000
Found 78 numbers
real 0m0.932s
user 0m0.781s
sys 0m0.090s
$ time ruby19 q161b.rb 1000000000000000000000000
Found 274 numbers
real 0m6.740s
user 0m6.319s
sys 0m0.110s
Did I miss a number?
On 02.05.2008 18:44, Rob B. wrote:
On May 2, 2008, at 12:10 PM, Ken B. wrote:
On Fri, 02 May 2008 10:28:00 -0500, Matthew M. wrote:
user 0m53.995s
1089 * 9 = 9801
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?
My pretty straightforward solution:
robert@fussel /cygdrive/c/Temp
$ time ./quiz-161.rb 1_000
real 0m0.591s
user 0m0.045s
sys 0m0.170s
robert@fussel /cygdrive/c/Temp
$ time ./quiz-161.rb 1_000_000
8712
9801
87912
98901
879912
989901
real 0m3.981s
user 0m3.764s
sys 0m0.108s
robert@fussel /cygdrive/c/Temp
$ time ./quiz-161.rb 10_000_000
8712
9801
87912
98901
879912
989901
8799912
9899901
real 0m38.022s
user 0m37.530s
sys 0m0.155s
robert@fussel /cygdrive/c/Temp
$ time ./quiz-161.rb 100_000_000
8712
9801
87912
98901
879912
989901
8799912
9899901
87128712
87999912
98019801
98999901
real 6m21.099s
user 6m19.639s
sys 0m0.108s
robert@fussel /cygdrive/c/Temp
$ wc quiz-161.rb
8 36 173 quiz-161.rb
robert@fussel /cygdrive/c/Temp
$
Cheers
robert
On Sun, May 4, 2008 at 6:22 AM, Harry K. [email protected]
wrote:
ruby q161.rb 10000000000000000
84 numbers
I’ve got 106 in that range:
$ time ./reverse_divisible 10_000_000_000_000_000
106
real 0m1.457s
user 0m1.364s
sys 0m0.092s
The only reason why I don’t post the solution yet is because I’m stuck
on a proof that the method is correct
Marcelo
On Sat, May 3, 2008 at 4:15 PM, ThoML [email protected] wrote:
you could use some interesting shortcuts.
$ time ruby19 q161b.rb 10000000000000000
Found 78 numbers
Did I miss a number?
So far I have
ruby q161.rb 10000000000000000
84 numbers
I am not sure yet whether or not I am missing some numbers.
You seem to be missing at least six.
Harry