この問題は、単に2と10の両方の基数で回文数になるかを調べるという単純な方法でも十分速いです。自然数nの回文数の判定はO(logn)の計算量なので、NまででO(NlogN)の計算量です。
回文数を生成するほうが速いです。10進で回文数を生成して、2進で回文数か判定します。生成にはO(N0.5)かかって、かつ回文数はO(N0.5)個あるので、全体ではO(N0.5logN)となります。
回文数の生成には分割統治法を使うと、速くてメモリも少なくて済みます。例えば、1234321なら、1200021と343に分けて考えます。これでO(N0.5)になります。
マージを使うとO(N0.5)になります。基数10と基数2の回文数を同様に生成します。基数2のほうは大きめにとっておきます。その際、昇順にソートされて生成します。上の例だと、1200021のほうを外側のループにすればうまくソートされます。ソートされているとマージが使えて、両方で一致するものを列挙するだけです。
PyPyで1016までが1分以内に入りました。
10^ 6 => 0.020sec 10^ 8 => 0.053sec 10^10 => 0.107sec 10^12 => 0.469sec 10^14 => 4.614sec 10^16 => 53.286sec
