algorithm - 欧拉计划 #36 的更好解决方案？

Question

欧拉计划 problem 36状态:

The decimal number, 585 = 1001001001 (binary), is palindromic in both bases.

Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.

(Please note that the palindromic number, in either base, may not include leading zeros.)

已经有一个solution对此堆栈溢出，但我想要一个更有效的解决方案。

例如，由于回文不能有前导 0，因此不需要检查偶数，只需要检查二进制最后一位为 1 的奇数。这个简单的观察已经加速了蛮力“检查每个数字范围”乘以 2。

但我想比这更聪明。理想情况下，我想要一种算法，其运行时间与总和中的数字数量成正比。我认为没有比这更好的了。但也许这是不可能的。例如，我们能否生成所有小于一百万的回文小数，时间与满足该性质的小数数成正比？ (我认为答案是肯定的)。

解决这个回文和问题的最有效算法是什么？我想考虑由 N 参数化的运行时:数字范围的大小(在本例中为 100 万)， D:范围内的十进制回文集，B:范围内的二进制回文集。我希望运行时间为 o(N) + O( |D 与 B| 相交)，否则为 O(min(|D|, |B|))

注意:binary的序列和 decimal回文是众所周知的。

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

. . .十进制回文 < 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

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

这不是 O(|D 与 B| 相交) :( 只有 32 个数字最多为 10¹⁰ 在两个基数中都是回文。我没有看到任何只允许构建的模式那些。

¹ 如果N 有d 位(以b 为基数)，则回文数不超过N介于最多 d-1 位的回文数和最多 d 位的回文数之间(包括两个限制)。有 (b-1)*b^(k-1) 个数字恰好有 k 个数字(在基数 b 中)，其中 (b-1)*b^(floor((k-1)/2))) 是回文。求和给出最多 k 位的基数-b 回文数为 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，其中一个因子以所考虑的基数的倍数为界。