Comment by ashdnazg

I'm back to searching for numbers that are palindromes both in decimal and in binary. [0]

I had an insight the other day, that as I fix the n least (and most, it's a palindrome!) significant decimal digits, I also fix the remainder from division in 5^n. Let's call it R. Since I also fix by that point a bunch of least (and most) significant bits, I can subtract how much they contribute mod 5^n from R, to get the remainder from division in 5^n of the still unknown bit. The thing is, maybe it's not possible to get this specific remainder with the unknown bits, because they're too few.

So, I can prepare in advance a table of size 5^n (for one or more ns) which tells me how many bits from the middle of the palindrome I need, to get a remainder of <index mod 5^n>.

Then when I get to the aforementioned situation, all I need to do is to compare the number in the table to number of unknown bits. If the number in the table is bigger, I can prune the entire subtree.

From a little bit of testing, this seems to work, and it seems to complement my current lookup tables and not prune the same branches. It won't make a huge difference, but every little bit helps.

The important thing, though, is that I'm just happy there are still algorithmic improvements! For a long while I've been only doing engineering improvements such as more efficient tables and porting to CUDA, but since the problem is exponential, real breakthroughs have to come from a better algorithm, and I almost gave up on finding one.

[0] https://ashdnazg.github.io/articles/22/Finding-Really-Big-Pa...