Better Solution to Project Euler #36?

Question

Project Euler problem 36 states:

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.)

There is already a solution to this on stack overflow, but I want a more efficient solution.

For example, since the palindrome cannot have leading 0's, no even numbers need to be checked, only odd numbers for which the last bit in binary is a 1. This simple observation already speeds up the brute force "check every number in the range" by a factor of 2.

But I would like to be more clever than that. Ideally, I would like an algorithm with running time proportional to the number of numbers in the sum. I don't think it's possible to do better than that. But maybe that is not possible. Could we for example, generate all palindromic decimal numbers less than one million in time proportional to the number of decimal numbers satisfying that property? (I think the answer is yes).

What is the most efficient algorithm to solve this palindrome sum problem? I would like to consider run-times parameterized by N: the size of the range of numbers (in this case 1 million), D: the set of decimal palindromes in the range, and B: the set of binary palindromes in the range. I hope for a run-time that is o(N) + O( |D intersect B| ), or failing that, O(min(|D|, |B|))

Note: The sequences of binary and decimal palindromes are well known.

e.g. binary palindromes < 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,

palindromes in both bases: 0, 1, 3, 5, 7, 9, 33, 99

The binary representations of 33 and 99 are 10001 and 1100011 respectively. The next number which is a palindrome in both is 585 = 1001001001.

Answer 1

The number of palindromes in base b of length 2*k is (b-1)*b^(k-1), as is the number of palindromes of length 2*k-1. So the number of palindromes not exceeding N in any base is O(sqrt(N))¹. So if you generate all palindromes (not exceeding N) in one base and check if they are also palindromes in the other base, you have an O(sqrt(N)*log(N)) algorithm (the log factor comes from the palindrome check). That's o(N), but I don't know yet if it's also O(|D intersect B|).

It's not O(|D intersect B|) :( There are only 32 numbers up to 10¹⁰ which are palindromic in both bases. I don't see any pattern that would allow constructing only those.

¹ If N has d digits (in base b), the number of palindromes not exceeding N is between the number of palindromes having at most d-1 digits and the number of palindromes having at most d digits (both limits inclusive). There are (b-1)*b^(k-1) numbers having exactly k digits (in base b), of which (b-1)*b^(floor((k-1)/2))) are palindromes. Summing gives the number of base-b palindromes with at most k digits as either 2*(b^(k/2)-1) (if k is even) or (b-1)*b^((k-1)/2) + 2*(b^((k-1)/2)-1) (if k is odd). Hence, give or take a factor of 2*b, the number of palindromes with at most d digits is b^(d/2). Thus the number of palindromes not exceeding N is roughly N^0.5, with a factor bounded by a multiple of the base considered.