Let’s first try generating all base-\(10\) palindromes under \(N\). Note that we can enumerate all palindromes that are \(d\) digits long using an arbitrary \(\lceil d/2 \rceil\)-length number, either append its digits in reverse for an even-length palindrome, or all except the last digit for an odd-length palindrome. We can thus enumerate palindromes in increasing value until it exceeds \(N\).

There are at most \(O(\sqrt N)\) such palindromes, and we can test whether they’re a palindrome in base-\(A\) in \(O(\log_A N)\) time each, thus the problem is solved in \(O(\sqrt N \log_A N)\) time, which should be fast enough.