[qaxpbods] Hilbert curve integer coordinates

an order N+1 Hilbert curve concatenates 4 copies of order N.  therefore, one can draw an order N curve, then seamlessly continue the curve into an order N+1 with the same step size, and so forth.  in this way, the curve can be continued indefinitely.  (previously, a roller coaster.)

assume a step size of 1 and that the curve starts at the origin.  given as input an index, i.e., a positive integer length from the start of this infinite Hilbert curve, compute the integer coordinates of that index.  note that N, the order of the curve, is not given as input.  it is not just a simple matter of internally computing N from the index then computing coordinates of an order N curve because we want order N to always coincide with the first quarter of N+1.  the standard method of drawing Hilbert curves does not do this.  easiest solution might be to compute the smallest even N containing the index, because the first 1/16 of an order N+2 curve is congruent to and in the same orientation as an order N.

compute the inverse: from non-negative integer coordinates to index.

also consider higher dimensional Hilbert curves.  according to this page, there are many possible definitions of a Hilbert curve of dimension 3 or higher.

the link above also seems to suggest that there are many opportunities for optimization in computing this mapping and its inverse.  the computation does a lot of bit manipulation, so consider implementing it in hardware, e.g., Bluespec.  at what point, if ever, would hardware performance exceed software?

given that all nonnegative integers therefore can be mapped nicely to 2D lattice points in a quarter plane, consider the primes.  a quick internet search finds others have plotted primes along a Hilbert curve.  unlike in the Ulam spiral, there are disappointingly no obvious patterns.  density is high near the origin, and points get sparser further away, thinning out at the rate given by the prime number theorem.

are there integer sequences which look surprisingly nice when plotted on a Hilbert curve?