コードを短くするのって楽しいですよね？(9)

続々、神の領域。

3進数について考えていこう。いま、末尾にTをつけた数字は3進数で表現された数値を意味するものとする。

たとえば、1111T=27+9+3+1 = 40である。また、bitはbinary digitの略であることから、ここでは3進数の1桁をtit(ternary digit)と書くことにする。

各titは、を表現しているが、これは、3をn回掛け合わせたものであり、(素因数分解して2を含まないわけだから)明らかに奇数である。奇数に奇数を足すと偶数になる。よって、各titに1が増えると都度、偶奇が反転(逆転)する。たとえば、1Tは奇数であり、11Tは偶数、111T奇数、1111Tは偶数という具合である。また、10101010Tは、1があるtitが4つあるので偶数、という具合である。

また、2のtitは、偶奇には影響を及ぼさない。なぜなら、2のtitはを意味していて、これは2の倍数だから、これを加算しても元の数と偶奇は変わらないからである。例) 111Tは奇数。2111Tも奇数。212121Tも奇数。etc..

3で割ることは、titの右シフトに相当する。bit shiftならぬ、tit shiftである。また、最下位のtitをtit0と呼ぶことにする。

いま「n/=3」のようにtit shiftしていきながら、nが0になったときループを抜けることを考える。「各titに1が増えると都度、偶奇が逆転する」ことを思い出すと、各titに1が減るとき偶奇が反転するので、tit0が1の状態でtit shiftすると、偶奇が反転する。

例) 10101T:奇数 →(tit shift)→ 1010T:偶数

よって、偶奇はコントロールできる。たとえば、11111Tならば、右にtit shiftしていけば、奇数→偶数→奇数→偶数→奇数というように遷移するし、10101Tなら右tif shiftによって、奇数→偶数→偶数→奇数→奇数というように遷移する。

要するに、N回目右tit shift後に偶数にしたいなら、tit 0〜tit N(下から数えてN番目のtit)までの1であるtitの数も偶数にすることだ。(これは、tit Nを、決定するときに、その下位titであるtit 0〜tit N-1の1の数を考慮しながら決定していけば良い。)

かくして、

main(n){for(n=getchar()&1?'xxxx':120;n/=3;)puts(n&1?"no":"yes");} 

という形が得られた。我々に残された課題は、この「xxxx」の部分を調整し、許容される文字コードにする作業だけだ。(つづく)