Collatz Problem - nn

vi

r1d*

なるほど。さすがです。私も以下のような『あとから消す』バージョンもあったけど、同じ長さだったので、投稿したのは『出力しない』バージョンの方。

qzYo^R=@0%2?@0*3+1:@0/2
^[q111@z/^1$
jdGZZ

検索＆削除のところは、pla さん流に

d/^1$

とやれば、あと 2B は稼げたんだな。検索 wrap をはさんでの d の動き、勉強になった。

C

C はトップの 59B 組は、みな、main() の第二引数(char** argv)が指すアドレスが、実行の度に異なることを利用した "(rand)" 解で、ロジックそのものは、64B と同じだった。私は、"(rand)" はやる気がないので、トップタイでよしとする。
ところで、２点ほど。
まず、なんで、argv の指し先アドレスは毎回異なるんだろう？値を調べてみると 0xbf...... というスタック系のアドレス値だ。毎回、上位のほうのビットから異なっている。スタックはプロセスごとの仮想アドレス空間で、同じ位置に配置されないのかな？
次に、argv の値だが、アドレスなのでワード境界にアラインされることは想像がつく。調べてみたところ、16 進で、最下位は常に 4 になるようだ。実際には、int として扱うため、最上位ビットが立っているからマイナスの値となり、以下の値の集合となる。

-16*n-12

今回の問題の場合、3, 11, 27 という正の奇数がほしいので、' ~ ' で補数を取ってやると、

16*n+11

という値の集合となる。3, 11, 27 は、4*n-1 系の数なので、いや、8*n+3 系の数なので、これは、8*n+11 系と同じだから、27 より大きい 8 の倍数で、16 では割り切れないもので mod を取ってやれば良い。そのような数の最小のものは、40 で、mod 40 を行えば、以下のような集合が得られる。

(16*n+11)%40  ==> 3, 11, 19, 27, 35

あとは、運を天にまかせて確率の問題となるが、確率は、元のアドレス値がランダムになる仮定のもと、1/5 * 1/5 * 1/5 で、125 回に 1 回となる。
トップのnot さんの解は、まさにこの通りだ。他の方々は、別の除数を使っている。

~argv % 40 ==> 3, 11, 19, 27, 35                で、確率 1/125
~argv % 28 ==> 3, 7, 11, 15, 19, 23, 27         で、確率 1/343
~argv % 36 ==> 3, 7, 11, 15, 19, 23, 27, 31, 35 で、確率 1/729
-argv % 29 ==> 0, 1, 2, 3, ...               28 で、確率 1/24389 !!

現実には、分布がもっと偏っていて確率が高いのだろうか？？？
私も、過去には、js などで、random はやっているので、批判するつもりは毛頭無いけど、私は、やる気がおきないなぁ。