Let’s consider the highly analytical algorithm of deciding whether a number is prime or not.

How does the brain do that in the current view of HTM theory?

I learn the procedures, the checks and the transformations I have to make on numbers, then I can easily apply the algorithm to any number, including numbers I’ve never seen before.

The numbers don’t come into the brain sparse-encoded in a special way specifically for this problem, they come in encoded the way I’ve learned numbers in kindergarten.

What would it take to make a HTM capable of solving such a problem under these constraints?

I think performing the prime number algorithm is a really high-level task for any brain-like architecture. Just consider the notion of an arbitrary number, the notion of division, of zero remainder division, involved in the algorithm we employ in order to ascertain the status of primeness. Then there’s the memory aspect, whether it be a good internal short-term memory or some means of storing it externally (with motor output). HTM, and the typical DL architecture as well, primarily deals with something along the lines of intuition, which should perhaps be regarded as something antipodal to the performing of analytical algorithms.