Berarducci and Otero in "A Recursive Nonstandard Model of Normal Open Induction" (Journal of Symbolic Logic v61, 1996)
give a discretely ordered ring $R$ with recursive operations having the following properties:
- $R$ is integrally closed in its quotient field. (So elements with "rational" square roots are perfect squares.)
- The prime elements of $R$ are cofinal
- $R$ satisfies the induction axioms for quantifier-free formulas
In an earlier paper of Otero (Journal of Symbolic Logic, vol 55, 1990) Otero proves that every model of Open Induction extends to one in which Lagrange's Four-Square Theorem holds. Whether this can be done effectively I don't know.
As for the general question "What properties can a recursively presented discretely ordered ring share with $\mathbb{Z}$": Let's say that a discretely ordered ring $R$ is "diophantine correct" if it satisfies all universal sentences that hold in $\mathbb{Z}$. Assuming that the language of rings has signature $(+, -, \times , \le,0 ,1)$, diophantine correctness amounts to the requirement that any system of polynomial equations and inequalities that are solvable in $R$ is solvable in the standard integers. Incidentally, models of open induction satisfy a weaker property: Any system of equations solvable in some (at least one) model of open induction has a p-adic solution.
The question whether a nonstandard diophantine correct model of open induction can be effectively constructed was raised by Adamowic and Morales-Luna in "A Recursive Model for Arithmetic with Weak Induction", (Journal of Symbolic Logic v50, 1985). I believe that this question is still open. I also believe that the models constructed in the Otero-Berarducci paper are in fact diophantine correct, but the proof of this seems to bump up against open problems in number theory. This is all discussed in an article on diophantine correct open induction by Sidney Raffer in "Set theory, Arithmetic, Philosophy: Essays in Memory of Stanley Tennenbaum (edited by J. Kennedy and R. Kossak), Cambridge University Press. (To appear.)
This is a response to a question from the comments: It is too long to fit there.
Proof of the Euclidean Division Theorem from the axioms of Open Induction:
The problem is to show that if $A$ is a model of open induction and if $x,y$ are elements of $A$ with $y>0$ and $x \ge 0 $ then there are unique elements $r, q$ of $A$ such that $x=yq+r$ and $0 \le r < q$. (The statement actually holds for all $x$ and the proof for $x < 0 $ is similar.)
First show that for every $x\in A$ with $x\ge 0$, there is some $q\in A$ such that $yq\le x < y(q+1)$. (Suppose, by way of by contradiction, that $x \ge 0$ and there is no such $q$. Let $S$ be the subset of $A$ defined by the quantifier-free formula $\sigma(q): q \ge 0 \wedge yq\le x$. Show that $S$ contains 0 and is closed under successor. By induction $S$ contains every positive element of $A$. But this is impossible because $x+1$ cannot be in $S$.)
Next, given $y > 0$ and $x \ge 0 $ choose $q$ (as in Part 1) such that $yq \le x < y(q+1)$. Put $r=x-yq$. Using that fact that $A$ is discretely ordered it is follows easily that $r$ and $q$ are the unique elements of $A$ satisfying $x=yq+r$ and $0 \le r < q$.
