项目Euler#36的更好解决方案？

Question

项目欧拉问题36指出:

十进制数,585 = 1001001001(二进制),在两个碱基中都是回文.

求出所有数字的总和,小于一百万,在基数10和基数2中是回文.

(请注意,任何一个碱基中的回文数字可能不包括前导零.)

堆栈溢出已经有了解决方案,但我想要一个更有效的解决方案.

例如,由于回文不能有前导0,所以不需要检查偶数,只有二进制的最后一位为1的奇数.这个简单的观察已经加速了蛮力"检查范围内的每个数字" 2倍.

但我想比这更聪明.理想情况下,我想要一个算法,其运行时间与总和中的数字数成正比.我认为不可能做得更好.但也许这是不可能的.例如,我们可以生成与满足该属性的十进制数的比例小于一百万的所有回文十进制数吗？(我认为答案是肯定的).

解决这个回文和问题最有效的算法是什么？我想考虑由N参数化的运行时间:数字范围的大小(在这种情况下为1百万),D:范围内的十进制回文的集合,以及B:范围内的二元回文的集合.我希望运行时为o(N)+ O(| D与B |相交),或者失败,O(min(| D |,| B |))

注意:二元和十进制回文序列是众所周知的.

例如二元回文<100:0,1,3,5,7,9,15,17,21,27,31,33,45,51,63,65,73,85,93,99

...decimal palindromes <100:0,1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99,

两个碱基中的回文:0,1,3,5,7,9,33,99

33和99的二进制表示分别是10001和1100011.下一个是两者的回文数字是585 = 1001001001.

Answer 1

b长度为基数的回文数2*k为(b-1)*b^(k-1)，长度为回文数的数也是2*k-1。因此，在任何基数中不超过的回文数N为 O(sqrt(N))\xc2\xb9。因此，如果您N在一个基数中生成所有回文（不超过 ），并检查它们在另一基数中是否也是回文，则您有一个 O(sqrt(N)*log(N)) 算法（对数因子来自回文检查）。这是o(N)，但我还不知道它是否也是O(|D intersect B|)。

\n\n

^{这不是 O(|D intersect B|) :( 10 10}以内只有 32 个数字在两个基数中都是回文。我没有看到任何模式允许仅构造这些数字。

\n\n

\xc2\xb9 如果N有d数字（以 为基数b），则不超过的回文数N介于最多d-1位数的回文数和最多d位数的回文数之间（包括两个限制）。有些(b-1)*b^(k-1)数字具有精确的k数字（以基数为基数b），其中(b-1)*b^(floor((k-1)/2)))是回文。b求和给出最多k位数为2*(b^(k/2)-1)（如果k是偶数）或(b-1)*b^((k-1)/2) + 2*(b^((k-1)/2)-1)（如果是奇数）的基本回文数k。因此，给定或取一个因子2*b，最多包含 d 位数字的回文数为b^(d/2)。因此，不超过的回文数N大致为N^0.5，其中一个因子以所考虑的基数的倍数为界。

\n