[seqfan] when a map is a cyclic permutation

[hv at crypt.org]

Hi all, I've been looking at certain Turing machine analogues, and have
found that a pair of them turn out, in effect, to be applying the
following maps over sets of length-m binary strings:

A) 0^{m} -> 1^{m-1}0
   00^{k}1x -> 1^{k}0x0
   10^{k}1x -> x01^{k}1
   10^{m-1} -> 1^{m}

B) 0^{m} -> 1^{m-1}0
   00^{k}1x -> x01^{k}0
   1x10^{k} -> x01^{k}1
   10^{m-1} -> 1^{m}

(In which "1^{k}" means k repetitions of the digit 1, with k >= 0, and "x"
stands for an arbitrary binary substring, of length >= 0, such that the
whole string is length m.)

These maps clearly act as a permutation of the length-m binary strings,
and for my analysis I care whether that is a cyclic permutation.

By way of example, iterating (B) with m=5 starting from 11111 gives the
following cycle:
  11111 11101 11001 10001 00001 01110 11000 01111
  11100 10111 01101 10100 00111 11010 10011 00101
  01010 01000 00000 11110 11011 10101 01001 00100
  00010 00110 10010 00011 10110 01011 01100 10000

Empirically, I've found that they both have the same behaviour, and
are cyclic over length-m binary strings when m is in { 2, 3, 5, 6, 11,
14, 15, 17, 27, 29 }; Superseeker notes that this looks very like those
m for which 2^{m+1} + 3 is prime - see A057732.

Can anyone see why that should be so? Or even prove it?

Looking at all the cycle lengths for those m that do not yield a single
cycle does not suggest anything related to factorisation, they look
pretty random:
  m=3: 8
  m=4: 6, 5, 2, 2, 1
  m=5: 32
  m=6: 64
  m=7: 20, 20, 19, 18, 17, 16, 15, 2, 1
  m=8: 106, 97, 28, 23, 2
  m=9: 82, 81, 78, 77, 74, 22
  m=10: 438, 437, 146, 2, 1

Hugo