Choose any infinite sequence of binary numbers {0,1,0,0,...} and map the natural numbers to it. For any number not divisible by 2 or 3, go left if it maps to 0 and right if it maps to 1.
Doesn't this property still hold? That is, it's nothing to do with prime numbers and something to do with the quotient of {2,3}.
All prime numbers above 6 are of the form 6n + 1 or 6n + 5, everything else is a factor of 2 or 3. If you make a choice that occurs on primes then no choice will be made for the 6n + 2/3/4 cells. This gives a well defined pattern since this is setup so those no choice cells are the ones that could go outside the bounds.
You could also create a shape with 30 sides and a similar pattern since all primes above 30 (235) are of the form 30n + 1, 30n + 7, 30n + 11, 30n + 13, 30n + 17, 30n + 19, 30n + 23 or 30n + 29. Everything else is divisible by 2, 3 or 5.
In fact you can do this sort of thing with any set of factors. There will be regular gaps in primality. Set the starting point so that those gaps in primality only change the direction on the inward sides and you'll confine all numbers within some larger shape.
I guess the generalization here is choose a set {primes}, create a shape (I believe that would be called a prime lattice or something?) w/ Product({primes}) sides and all primes > Product({primes}) are of the form {Product({primes}) + Set_of_Primes/{primes} mod Product({primes})}. I'm not sure how to get the inductive proof that these moves converge within the lattice for all {primes}.
You can avoid HN's * = italics by using spaces (2 * 3 * 5) or escaping the * with \ (2\*3\*5 gives 2*3*5).