[QUIZ] Reverse Divisible Numbers (#161)

[Shane Emmons]

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

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

Here's my attempt:
class Integer
def divisible_by_reverse?
return false unless self % 9 == 0
return false if self % 10 == 0
reverse = self.to_s.reverse
return false if self.to_s.eql?(reverse)
return self % reverse.to_i == 0
end
end

max = ARGV[0] ? ARGV[0].to_i : 1_000_000
1.upto(max) { |n| puts n if n.divisible_by_reverse? }

 

[ThoML]

Hi,

Here are two most likely non-working non-solutions that rely on
unproven assumptions. (They work for the defined range though.
Anyway, I've got a cold and will go to bed now.


------------------------ version 1

# 1089 and 2178 (= 1089 * 2) are the only 4-digit numbers that are
# reverse divisible. "Stretch" these numbers (use 10, 89 and 21, 78
as
# prefix/suffix) by keeping it reverse divisble.
#
# As Harry Kakueiki and Marcelo pointed out, this solutions misses
certain
# numbers. Shame on me.
def rdn(limit = 1_000_000)
digits = limit.to_s.size
nums = {'10' => '89', '21' => '78'}
part = ['', *(0..digits).to_a.inject([]) {|a, e|
a << ('9' * (e + 1)) << ('0' * (e + 1))
}]
part = part.sort_by {|e| e.size}

rv = {}
0.upto(digits - 5) do |d|
is = d - 4
nums.each do |prefix, suffix|
next if (prefix + suffix).to_i > limit
part.each do |p|
next if p.size < is
b = [prefix, p, suffix].join
a = b.to_i
if a < limit and !rv.has_key?(a)
b.reverse!
b = b.to_i
if b % a == 0
nums[a] = a
rv[a] = b
end
end
end
end
end
return rv
end


if __FILE__ == $0
limit = (ARGV[0] || 1_000_000).to_i
nums = rdn(limit).sort_by {|a, b| b}
nums.each do |a, b|
puts "#{b} = #{a} * #{b / a}"
end
puts "Found #{nums.size} numbers"
end



------------------------ version 2

# Assumptions:
# - The start value is 8712
# - Any number can be divided by 99 (3**2 * 11)
# - The last digit has to be 1 or 2
def rdn(limit)
rv = []
8712.step((limit || 1_000_000).to_i, 99) do |i|
r = i % 10
next if r != 1 and r != 2
j = i.to_s.reverse.to_i
d, r = i.divmod(j)
if r == 0 and d > 1
v = [j, d, i]
puts "%s * %s = %d" % v
rv << v
end
end
return rv
end

if __FILE__ == $0
limit = ARGV[0] || 1_000_000
nums = rdn(limit)
puts "Found #{nums.size} numbers"
end

 

[Robert Klemme]

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
$

robert@fussel /cygdrive/c/Temp
$ cat quiz-161.rb
#!/bin/env ruby

limit = (ARGV.shift or raise "No limit given!").to_i

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

robert@fussel /cygdrive/c/Temp
$

Cheers

robert

 

[Marcelo]

The only reason why I don't post the solution yet is because I'm
stuck on a proof that the method is correct :-(

The proof I'm stuck on is that numbers with this property are divisible
by 9 and 11. Martin DeMello already suggested how to prove that it's
divisible by 9, the part I'm stuck on is that it's also divisible by
11.

The other part of the proof is a bit more complicated actually...

If x divides into x reversed, then x divided by 99 is a palindrome
composed solely of 1s and 0s. I can see why, I just can't figure out a
proof.

The program that uses those two properties follows:

------------------------------ >8 ------------------------------
#!/usr/bin/env ruby

MAX = ARGV[0] ? ARGV[0].to_i : 1_000_000

N = 2**(Math::log10(MAX/99).ceil)-1
(3..N).map { |i| i.to_s(2).to_i*99 }.select { |i| i % 10 != 0}.each do |n|
[n, 2*n].each do |n|
next if n > MAX
m = n.to_s.reverse.to_i
next if m == n
puts "#{n} #{m}" if m % n == 0
end
end
------------------------------ 8< ------------------------------

In order to get the number divided by 99 I'm looking for a binary
representation that has one less than number of digits the upper limit
has.

For example, 1_000_000 has seven digits; 1_000_000/99 has 5 digits.
2**5 also has 5 digits (in binary), so the number I'm looking for is
2**5-1, which in binary is 1111. This gives me an upper bound for
highest reverse-divisible number less than 1_000_000 such that when
divided by 99 is all 1s and 0s, namely:

109989 / 99 = 1111

What I'm doing effectibly is search among 11, 100, 101, 110, 111, 1000,
1001, 1010, 1011, 1100, 1101 and 1111 as quotiens for x/99 where x is
a candidate to being a reverse divible number.

The 2*n in there came out of the observation that if x is reverse
divisible, 2*n might also be. Because of the way the search space is
constructed, if n is reverse divisible, then 2*n also is. I only need
to check to see if 2*n is still less than MAX.

And all of this came out of the original brute force version, to which
I started to add conditions to trim the search space. After that I
output the factors for the found numbers and began noticing some
patterns there. Many of these numbers are divisible by 1089, too, so
instead of stepping by 9 I could step by 1089 which allowed me to
explore a bigger set in a reasonable time. And that's where I noticed
this:

1089/99 = 11
10989/99 = 111
109989/99 = 1111
1099989/99 = 11111
10891089/99 = 110011
10999989/99 = 111111
108901089/99 = 1100011
109999989/99 = 1111111
1089001089/99 = 11000011
1098910989/99 = 11100111
1099999989/99 = 11111111
10890001089/99 = 110000011
10989010989/99 = 111000111
10999999989/99 = 111111111
108900001089/99 = 1100000011
108910891089/99 = 1100110011
109890010989/99 = 1110000111
109989109989/99 = 1111001111
109999999989/99 = 1111111111
1089000001089/99 = 11000000011
1089109891089/99 = 11001110011
1098900010989/99 = 11100000111
1099890109989/99 = 11110001111
1099999999989/99 = 11111111111

With MAX = 1_000_000_000_000_000_000 this is the list I get (174
numbers, ~ 1s on my PC):

1089 9801
2178 8712
10989 98901
21978 87912
109989 989901
219978 879912
1099989 9899901
2199978 8799912
10891089 98019801
21782178 87128712
10999989 98999901
21999978 87999912
108901089 980109801
217802178 871208712
109999989 989999901
219999978 879999912
1089001089 9801009801
2178002178 8712008712
1098910989 9890198901
2197821978 8791287912
1099999989 9899999901
2199999978 8799999912
10890001089 98010009801
21780002178 87120008712
10989010989 98901098901
21978021978 87912087912
10999999989 98999999901
21999999978 87999999912
108900001089 980100009801
217800002178 871200008712
108910891089 980198019801
217821782178 871287128712
109890010989 989010098901
219780021978 879120087912
109989109989 989901989901
219978219978 879912879912
109999999989 989999999901
219999999978 879999999912
1089000001089 9801000009801
2178000002178 8712000008712
1089109891089 9801989019801
2178219782178 8712879128712
1098900010989 9890100098901
2197800021978 8791200087912
1099890109989 9899010989901
2199780219978 8799120879912
1099999999989 9899999999901
2199999999978 8799999999912
10890000001089 98010000009801
21780000002178 87120000008712
10890108901089 98010980109801
21780217802178 87120871208712
10891099891089 98019899019801
21782199782178 87128799128712
10989000010989 98901000098901
21978000021978 87912000087912
10989108910989 98901980198901
21978217821978 87912871287912
10998900109989 98990100989901
21997800219978 87991200879912
10999891099989 98999019899901
21999782199978 87999128799912
10999999999989 98999999999901
21999999999978 87999999999912
108900000001089 980100000009801
217800000002178 871200000008712
108901098901089 980109890109801
217802197802178 871208791208712
108910999891089 980198999019801
217821999782178 871287999128712
109890000010989 989010000098901
219780000021978 879120000087912
109891098910989 989019890198901
219782197821978 879128791287912
109989000109989 989901000989901
219978000219978 879912000879912
109998901099989 989990109899901
219997802199978 879991208799912
109999999999989 989999999999901
219999999999978 879999999999912
1089000000001089 9801000000009801
2178000000002178 8712000000008712
1089001089001089 9801009801009801
2178002178002178 8712008712008712
1089010998901089 9801098990109801
2178021997802178 8712087991208712
1089108910891089 9801980198019801
2178217821782178 8712871287128712
1089109999891089 9801989999019801
2178219999782178 8712879999128712
1098900000010989 9890100000098901
2197800000021978 8791200000087912
1098901089010989 9890109801098901
2197802178021978 8791208712087912
1098910998910989 9890198990198901
2197821997821978 8791287991287912
1099890000109989 9899010000989901
2199780000219978 8799120000879912
1099891089109989 9899019801989901
2199782178219978 8799128712879912
1099989001099989 9899901009899901
2199978002199978 8799912008799912
1099998910999989 9899990198999901
2199997821999978 8799991287999912
1099999999999989 9899999999999901
2199999999999978 8799999999999912
10890000000001089 98010000000009801
21780000000002178 87120000000008712
10890010989001089 98010098901009801
21780021978002178 87120087912008712
10890109998901089 98010989990109801
21780219997802178 87120879991208712
10891089010891089 98019801098019801
21782178021782178 87128712087128712
10891099999891089 98019899999019801
21782199999782178 87128799999128712
10989000000010989 98901000000098901
21978000000021978 87912000000087912
10989010989010989 98901098901098901
21978021978021978 87912087912087912
10989109998910989 98901989990198901
21978219997821978 87912879991287912
10998900000109989 98990100000989901
21997800000219978 87991200000879912
10998910989109989 98990198901989901
21997821978219978 87991287912879912
10999890001099989 98999010009899901
21999780002199978 87999120008799912
10999989010999989 98999901098999901
21999978021999978 87999912087999912
10999999999999989 98999999999999901
21999999999999978 87999999999999912
108900000000001089 980100000000009801
217800000000002178 871200000000008712
108900010890001089 980100098010009801
217800021780002178 871200087120008712
108900109989001089 980100989901009801
217800219978002178 871200879912008712
108901089108901089 980109801980109801
217802178217802178 871208712871208712
108901099998901089 980109899990109801
217802199997802178 871208799991208712
108910890010891089 980198010098019801
217821780021782178 871287120087128712
108910989109891089 980198901989019801
217821978219782178 871287912879128712
108910999999891089 980198999999019801
217821999999782178 871287999999128712
109890000000010989 989010000000098901
219780000000021978 879120000000087912
109890010890010989 989010098010098901
219780021780021978 879120087120087912
109890109989010989 989010989901098901
219780219978021978 879120879912087912
109891089108910989 989019801980198901
219782178217821978 879128712871287912
109891099998910989 989019899990198901
219782199997821978 879128799991287912
109989000000109989 989901000000989901
219978000000219978 879912000000879912
109989010890109989 989901098010989901
219978021780219978 879912087120879912
109989109989109989 989901989901989901
219978219978219978 879912879912879912
109998900001099989 989990100009899901
219997800002199978 879991200008799912
109998910891099989 989990198019899901
219997821782199978 879991287128799912
109999890010999989 989999010098999901
219999780021999978 879999120087999912
109999989109999989 989999901989999901
219999978219999978 879999912879999912
109999999999999989 989999999999999901
219999999999999978 879999999999999912

Marcelo

 

[Ken Bloom]

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.com/home>.

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

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.

Everyone's posted benchmarks, but nobody's posted code yet. It's been
more than 48 hours, so I guess I'll start.

MAX=1_000_000

#we want pairs of reverse,num where num.to_s==reverse.to_s.reverse and
#num*multiplier == reverse for some integer multiplier where
#multiplier >= 2
#
#if multiplier is a fraction, then we would swap num and reverse to get an
#integer, so we'll do it in one direction only
#
#if multiplier is 1, then num is a palindrome
#
#if the most significant digit of num > 4 then all num*multiplier
#have more digits than reverse has, so we need not check those

DIGITS=(Math.log10(MAX)).to_i
ranges=(0..DIGITS).collect{ |digits| 10**digits ... 5*10**digits}
ranges[-1]=ranges[-1].begin..MAX if MAX < ranges[-1].end

ranges.each do |range|
range.each do |num|
ns=num.to_s
reverse=ns.reverse.to_i
next if num==reverse
next if ns[-1,1]=='0'
next unless (reverse/num)*num==reverse
puts "#{num} * #{reverse/num} = #{reverse}"
end
end

 

[Sandro Paganotti]

Here's mine:

MAXNUM = (( ARGV[0].to_i == 0 ) ? 1000000 : ARGV[0].to_i)

numbers = (0...MAXNUM).to_a
divs = Array.new

t = Time.now

MAXNUM.downto(0) do |n|
nts = n.to_s
next if numbers[n].nil? or
((nts[-1]-48) == 0) or
(nts[0]-48) < (nts[-1]-48)*2 or
nts == nts.reverse

if n % (v = nts.reverse.to_i) == 0
divs << [n,v]
numbers.delete(v)
end
end

puts "Benchmark = #{Time.now - t} secondi"
puts divs.inspect

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.com/home>.

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

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.

Everyone's posted benchmarks, but nobody's posted code yet. It's been
more than 48 hours, so I guess I'll start.

MAX=1_000_000

#we want pairs of reverse,num where num.to_s==reverse.to_s.reverse and
#num*multiplier == reverse for some integer multiplier where
#multiplier >= 2
#
#if multiplier is a fraction, then we would swap num and reverse to get an
#integer, so we'll do it in one direction only
#
#if multiplier is 1, then num is a palindrome
#
#if the most significant digit of num > 4 then all num*multiplier
#have more digits than reverse has, so we need not check those

DIGITS=(Math.log10(MAX)).to_i
ranges=(0..DIGITS).collect{ |digits| 10**digits ... 5*10**digits}
ranges[-1]=ranges[-1].begin..MAX if MAX < ranges[-1].end

ranges.each do |range|
range.each do |num|
ns=num.to_s
reverse=ns.reverse.to_i
next if num==reverse
next if ns[-1,1]=='0'
next unless (reverse/num)*num==reverse
puts "#{num} * #{reverse/num} = #{reverse}"
end
end

 

[ThoML]

divisible by 9 and 11.

An observation: it seems that any reverse divisble number (we found so
far) can be "derived" from 1089 somehow. 1089 is 11 * 99.

 

[Marcelo]

An observation: it seems that any reverse divisble number (we found so
far) can be "derived" from 1089 somehow. 1089 is 11 * 99.

Some counter-examples:

10989 98901
108901098901089 980109890109801
217802197802178 871208791208712
108910999891089 980198999019801
217821999782178 871287999128712
109890000010989 989010000098901
219780000021978 879120000087912
109891098910989 989019890198901
219782197821978 879128791287912
109998901099989 989990109899901
219997802199978 879991208799912
109999999999989 989999999999901
219999999999978 879999999999912

Marcelo

 

[ThoML]

Some counter-examples:

I didn't mean "derive" in a mathematical sense. I rather had something
like the following in mind (I assume you can see a certain regularity)
and I suspected that one could define some sort of productions rules
to get from one number to the next (not necessarily the next in line
but to one or more number(s) below so that no number is left out)
without actually doing the maths (just a guess but this is okay for me
when I'm sick in bed):

$ ruby19 s_marcelo.rb 10_000_000_000_000_000 |grep 10
1089 -- 9801
10989 -- 98901
109989 -- 989901
1099989 -- 9899901
10891089 -- 98019801
10999989 -- 98999901
108901089 -- 980109801
109999989 -- 989999901
1089001089 -- 9801009801
1098910989 -- 9890198901
1099999989 -- 9899999901
10890001089 -- 98010009801
10989010989 -- 98901098901
10999999989 -- 98999999901
108900001089 -- 980100009801
108910891089 -- 980198019801
109890010989 -- 989010098901
109989109989 -- 989901989901
109999999989 -- 989999999901
1089000001089 -- 9801000009801
1089109891089 -- 9801989019801
1098900010989 -- 9890100098901
1099890109989 -- 9899010989901
1099999999989 -- 9899999999901
10890000001089 -- 98010000009801
10890108901089 -- 98010980109801
10891099891089 -- 98019899019801
10989000010989 -- 98901000098901
10989108910989 -- 98901980198901
10998900109989 -- 98990100989901
10999891099989 -- 98999019899901
10999999999989 -- 98999999999901
108900000001089 -- 980100000009801
108901098901089 -- 980109890109801
108910999891089 -- 980198999019801
109890000010989 -- 989010000098901
109891098910989 -- 989019890198901
109989000109989 -- 989901000989901
109998901099989 -- 989990109899901
109999999999989 -- 989999999999901
1089000000001089 -- 9801000000009801
1089001089001089 -- 9801009801009801
1089010998901089 -- 9801098990109801
1089108910891089 -- 9801980198019801
1089109999891089 -- 9801989999019801
1098900000010989 -- 9890100000098901
1098901089010989 -- 9890109801098901
1098910998910989 -- 9890198990198901
1099890000109989 -- 9899010000989901
1099891089109989 -- 9899019801989901
1099989001099989 -- 9899901009899901
1099998910999989 -- 9899990198999901
1099999999999989 -- 9899999999999901

If this worked, the values with the prefix 21 would then derive from
2178 which is 1089 * 2.

 

[Harry Kakueki]

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.

Here is my solution.
It generates numbers based on patterns and selects the numbers from
that list that are divisible by their reverse.
It will not work to infinity because the patterns are not complete.
I wish I had more time to clean up the code and make better patterns.

But it seems to work well with fairly large numbers and it is very fast.

###########
def revs(res,ul = 1000000)
arr = []
res.each {|y| arr << y if y % y.to_s.reverse.to_i == 0 and y.to_s !=
y.to_s.reverse}
return arr.uniq.sort.select {|x| x < ul}
end

ul = ARGV[0].to_i
res = []
arr3 = ["__87___9__12","__871287__12","__98___9__01","__980198__01"]
arr5 = ["__87___91287___9__12","__871287___91287__12","87128712___087128712",
"__98___90198___9__01","__980198___90198__01","98019801___098019801"]

arr7 = ["__87___9__12___0__87___9__12","__87___91287___91287___9__12",
"__98___9__01___0__98___9__01","__98___90198___90198___9__01"]

arr9 = ["__87__12___0__87___9__12___0__87__12",
"__98__01___0__98___9__01___0__98__01"]
arr11 = ["__87___9__12___0__87___9__12___0__87___9__12",
"__98___9__01___0__98___9__01___0__98___9__01"]

arr3.each do |x|
(0..ul.to_s.length).each do |y|
(0..ul.to_s.length).each do |z|
res << x.unpack("@0a4" + "@4a4"*z + "@8a4").join.to_i
end
end
end

arr5.each do |x|
(0..ul.to_s.length).each do |y|
res << x.unpack("@0a4" + "@4a4" + "@8a4"*y + "@12a4" + "@16a4").join.to_i
(0..ul.to_s.length).each do |z|
res << x.unpack("@0a4" + "@4a4"*y + "@8a4"*z + "@12a4" * y +
"@16a4").join.to_i
end
end
end

arr7.each do |x|
(0..ul.to_s.length).each do |y|
(0..ul.to_s.length).each do |z|
res << x.unpack("@0a4" + "@4a4"*y + "@8a4" + "@12a4"*z + "@16a4" +
"@20a4"*y + "@24a4").join.to_i
end
end
end

arr9.each do |x|
(0..ul.to_s.length).each do |y|
(0..ul.to_s.length).each do |z|
res << x.unpack("@0a4"+"@4a4"+"@8a4"*y+"@12a4"+"@16a4"*z+"@20a4"+"@24a4"*y+"@28a4"+"@32a4").join.to_i
end
end
end

arr11.each do |x|
(0..ul.to_s.length).each do |y|
(0..ul.to_s.length).each do |z|
res << x.unpack("@0a4"+"@4a4"*y+"@8a4"+"@12a4"*z+"@16a4"+"@20a4"*z+"@24a4"+"@28a4"*z+"@32a4"+"@36a4"*y+"@40a4").join.to_i
end
end
end


t = Time.now
outs = revs(res,ul) if ul > 0
outs = revs(res) if ul == 0
puts outs
puts
puts "#{Time.now - t} seconds"
###################

ruby rq161.rb
8712
9801
87912
98901
879912
989901

0.005498 seconds



ruby rq161.rb 100_000_000
8712
9801
87912
98901
879912
989901
8799912
9899901
87128712
87999912
98019801
98999901

0.040202 seconds



Harry

 

[ThoML]

Ok, I had some free time. The enclosed solution still finds less
numbers than marcelo's elegant solution but it is slightly faster.

For 100_000_000_000_000_000_000_000

marcelo: 572 numbers, 1m28s
my enclosed solution: 550 numbers, 0m1.583s

Unless you want to find 550 reverse divisible numbers really fast
there is no real reason to use the enclosed version due to the
imperfect rules set. Anyway, here it is:


def rdn(limit = 1_000_000)
rules = [
lambda {|t, th, a, b|
t.sub(/^(#{th}#{a}9*)#{b}/, "\\19#{b}")
},
lambda {|t, th, a, b|
t.sub(/^(#{th}0*)/, '\\10')
},
lambda {|t, th, a, b|
t.gsub(/#{b}(0*)#{a}/, "#{b}\\10#{a}")
},
lambda {|t, th, a, b|
t.sub(/^(#{th})(#{th})$/, "\\1#{a}#{b}\\1")
},
lambda {|t, th, a, b|
z = th[/0+$/]
th = th[0, th.size - z.size] if z
t.sub(/^(#{th}#{z})(#{z}#{th})$/, "\\1#{a}#{b}#{a}#{b}\
\2")
},
lambda {|t, th, a, b|
th ? ["#{a}#{b}0", th, th, "0#{a}#{b}"].join : t
},
lambda {|t, th, a, b|
th ? ["#{a}#{b}", th, th, "#{a}#{b}"].join : t
},
lambda {|t, th, a, b| [t, t].join},
]

half = {
'1089' => lambda {|t| t[0, t.size / 2][/^(109*890*)*/]},
'2178' => lambda {|t| t[0, t.size / 2][/^(219*780*)*/]},
}

digits = limit.to_s.size

out = {1089 => 9801, 2178 => 8712}

axioms = [
['1089'],
['2178']
]

axioms.each do |nums|
nums0 = nums[0]
nums0pre, nums0post = nums0.scan(/../)
makehalf = half[nums0]
cache = Hash.new do |h, n|
nh = makehalf.call(n)
rules.each do |rule|
n1 = rule.call(n, nh, nums0pre, nums0post)
n1i = n1.to_i
if n1 != n and !out.has_key?(n1i) and n1.size < digits
m1i = n1.reverse.to_i
if m1i < limit
nums << n1
if m1i % n1i == 0
out[n1i] = m1i
val = true
end
end
end
end
h[n] = false
end
begin
found = false
nums.each {|n| found ||= cache[n]}
end while found
end
return out
end


if __FILE__ == $0
limit = (ARGV[0] || 1_000_000).to_i
nums = rdn(limit).sort_by {|a, b| b}
nums.each do |n1i, m1i|
puts "#{m1i} = #{n1i} * #{m1i / n1i}"
end
puts "Found #{nums.size} numbers"
end

 

[Matthew Moss]

Forgot to send in my own solution: summary coming shortly.



class Integer
def divides?(n)
(n % self).zero?
end

def reverse
self.to_s.reverse.to_i
end
end

def count(lower, upper, incr)
raise "Require lower <= upper" if lower > upper
raise "Require incr > 0" unless incr > 0

while lower <= upper do
yield lower
lower += incr
end
end

limit = (ARGV[0] || 1_000_000).to_i

count(0, limit, 9) do |i|
next if 10.divides?(i)

ir = i.reverse
next unless ir < i

puts "#{i} == #{ir} * #{i / ir}" if ir.divides?(i)
end

 

[Marcelo]

def count(lower, upper, incr)
raise "Require lower <= upper" if lower > upper
raise "Require incr > 0" unless incr > 0

while lower <= upper do
yield lower
lower += incr
end
end

Isn't that Numeric#step (ignoring exceptions)?

Thanks for reminding us that readability is important!

Marcelo

 

[Matthew Moss]

def count(lower, upper, incr)

Isn't that Numeric#step (ignoring exceptions)?

Why, yes, it would appear to be so... Learn something every day, I do.
=)

 

[Harry Kakueki]

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.

Now *I think* the patterns are complete so it is a complete solution.
Let me know if you notice some numbers are missing.

#######

def revs(res,ul=1000000)
res.select{|x| x % x.to_s.reverse.to_i == 0 and x.to_s !=
x.to_s.reverse and x < ul.to_i}.uniq.sort
end

ulim = (ARGV[0] or 1_000_000).to_i
res = []
arr = [[{"0"=>"_","1"=>"9","2"=>"12","3"=>"87","4"=>"0"},"87","12"],
[{"0"=>"_","1"=>"9","2"=>"01","3"=>"98","4"=>"0"},"98","01"]]

t = Time.now
arr.each do |q|
(0..5**((ulim-1).to_s.length - 4)-1).each do |x|
str = x.to_s(5).rjust((ulim-1).to_s.length -
4,"0").split(//).map{|x| q[0][x]}.join
res << (q[1] + str + q[2]).to_i
end
end

outs = revs(res,ulim)
puts outs
puts
puts "#{Time.now - t} seconds"

###############

ruby quiz161.rb
8712
9801
87912
98901
879912
989901

0.001758 seconds


ruby quiz161.rb 1_000_000_000
8712
9801
87912
98901
879912
989901
8799912
9899901
87128712
87999912
98019801
98999901
871208712
879999912
980109801
989999901

0.235533 seconds


Harry