Лучшее решение для проекта Эйлера № 36?

Задача 36 проекта Эйлера гласит:

Десятичное число 585 = 1001001001 (двоичное) равно палиндромные в обеих базах.

Найдите сумму всех чисел, меньших одного миллиона, которые являются палиндромными по основанию 10 и основанию 2.

(Обратите внимание, что палиндромное число в любой системе оснований может не включать ведущие нули.)

Уже существует решение по переполнению стека, но мне нужно более эффективное решение .

Например, поскольку палиндром не может иметь ведущих нулей, не нужно проверять четные числа, только нечетные числа, для которых последний бит в двоичном формате равен 1. Это простое наблюдение уже ускоряет "грубую силу" проверки каждого числа в диапазон "в 2 раза.

Но я хотел бы быть умнее этого.В идеале мне нужен алгоритм, время работы которого пропорционально количеству чисел в сумме. Я не думаю, что можно сделать лучше, чем это. Но, может быть, это невозможно. Можем ли мы, например, сгенерировать все палиндромные десятичные числа меньше одного миллиона за время, пропорциональное количеству десятичных чисел, удовлетворяющих этому свойству? (Думаю, да).

Какой алгоритм является наиболее эффективным для решения этой проблемы суммы палиндрома? Я хотел бы рассмотреть время выполнения, параметризованное N: размер диапазона чисел (в данном случае 1 миллион), D: набор десятичных палиндромов в диапазоне, а B: набор двоичных палиндромов в диапазоне. Я надеюсь на время выполнения, равное o (N) + O (| D, пересекающееся с B |), или, в противном случае, O (min (| D |, | B |))

Примечание: Последовательности двоичных и десятичных палиндромов хорошо известны.

например. бинарные палиндромы

. . .decimal палиндромы

палиндромы в обоих основания: 0, 1, 3, 5, 7, 9, 33, 99

Двоичные представления 33 и 99 равны 10001 и 1100011 соответственно. Следующее число, которое в обоих случаях является палиндромом, - 585 = 1001001001 .