The 3x+ 1 Conjugacy Map
Daniel J. Bernstein, Jeffrey C. Lagarias · Canadian Journal of Mathematics · 1996
Abstract The 3x+1 mapTand the shift mapSare defined byT(x)= (3x+ 1)/2 forxodd,T(x) = x/2forxeven, whileS(x)= (x− 1)/2 forxodd,S(x) = x/2forxeven. The 3x+ 1 conjugacy map Φ on the 2-adic integersZ2conjugatesStoT, i.e.,Φ oSo Φ-1=T.The map Φ mod2ninduces a permutation ΦnonZ/2nZ. We study the cycle structure of Φn. In particular we show that it has order2n− 4forn ≥6. We also count 1-cycles of Φnfornup to 1000; the results suggest that Φ has exactly two odd fixed points. The results generalize to theax+ bmap, whereabis odd.