Thanks for the reference. A000695 doesn't (directly) reference squared polynomials over GF(2), but I'm sure that some/many of the A000695 references do. A significant use of "perfect shuffle"/"interleave" is so-called "Z-order" or "Morton order" code which maps 2-dimensional integral coordinates into 1-dimensional coordinates by interleaving the bits of the x and y coordinates. The inverse of this function produces a space-filling "curve". http://en.wikipedia.org/wiki/Z-order_curve I wonder if anything interesting happens by mapping the coordinates of Gaussian integers into normal integers by interleaving the bits of the real and imaginary coordinates. At 10:15 PM 6/7/2012, Marc LeBrun wrote:
="Henry Baker" <hbaker1@pipeline.com> Aha! So squaring p(x) (mod 2) "spreads" the bits, sending each bit a[k]x^k -> a[k]x^2k; p(x)^2=p(x^2).
A000695[k], the Moser-de Bruijn sequence, with many interesting properties.
For example you can map a pair of integers x,y to a single integer z via z = a[x] + 2 a[y] then you can interleave another integer w via a[w] + 2 a[z] and so on...