I asked this question on cstheory a few months ago, but I didn't receive an answer, so I'm posting it here to see if there are original ideas from the "math world" to solve it. The original question asks about recognizing the language $L = \{N^2 \mid N \geq 1\}$ on a two counter machine, but I'll give here an equivalent formulation.

Suppose that you can write a program on a machine equipped with a single integer register $R$ and the following instruction set:

**Add $K$**: adds a constant $K \geq 0$ to the register;**Mul $K$**: multiplies the register by $K \geq 0$;**DJZ $lab$**: subtract one from the register, if the result is zero jump to label $lab$; otherwise continue with the next instruction;**Div $K, lab_0$,$lab_1$,...,$lab_{K-1}$**: divide the register by $K>0$, and place the quotient in the register (R = R div K); then jump to one of the $K$ labels according to the remainder (R mod K); the labels are not necessarily distinct;**Jump $lab$**: unconditional jump to label $lab$**Halt (ACCEPT|REJECT)**: stop the computation and ACCEPT or REJECT

Every instruction can have a label.

The question is:

If the register $R$ is initially loaded with an integer $M \geq 1$, can we build a program that ACCEPTs if and only if $M$ is a square (i.e. $M = N^2$)?

The problem originally appeared in:

Rich Schroeppel, "A Two counter Machine Cannot Calculate $2^N$" [1972]

(and perhaps has been solved, but I didn't find anything).

Note: in Schroeppel's paper the above model is called *More Powerful One Register Machine* (MP1RM) and is equivalent to a 2 counter machine.