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