```On Sun, May 4, 2008 at 10:36 AM, Marcelo <marcelo.magallon / gmail.com> wrote:

>  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

```