備忘録：2進法の問題（偽コラッツ、フィボナッチ）

注)以下の問題をコラッツ(奇数の場合は3倍して1を足すのがコラッツ)と勘違いした人がいたので、将来検索するために偽コラッツと書きましたが、コラッツとは関係ありません。

これ、こんな力技で解かなあかんの？
なんかなんとかならんかね pic.twitter.com/4p6eHAQsaW

— 鴨川を徘徊する魔女 (@Kamohai_) 2024年4月23日

整数に対して，奇数ならばその数から1を引き，偶数ならばその数を2で割る，という操作を繰り返し，1になったら終了する．
516〜520の中で，10回で1となる整数の個数はいくつか？

に対して，

これは地道にやる以外に方法はないと気づくのが重要なんですね。

とか言ってる人がいて，それに対して正しく

これただのシフト演算と1引くだけの操作ですよ！

と突っ込んでいる人がいてわろた。ただのシフト演算と1引くだけの操作なので

10桁の2進数で先頭以外の1の個数が0個（ 個），
9桁の2進数で先頭以外の1の個数が1個（ 個），
8桁の2進数で先頭以外の1の個数が2個（ 個），
7桁の2進数で先頭以外の1の個数が3個（ 個），，
6桁の2進数で先頭以外の1の個数が4個（ 個），

のものが10回で1となる整数となる（合計55個）。516〜520は9桁の2進数となることに着目すると
512+4=516，512+8=520
の2つのみが題意を満たす．

10回の操作で1となる整数は 1+8+21+20+5=55 個となるが，これって良く考えると，1桁減らすのに0の場合だと1回，1の場合だと2回で合計10回操作するということなので、
「10段の階段を1段または2段登って登りきる総数」
と一致することがわかり，これが と求まることがわかる．

このパスカルの三角形とフィボナッチ数列の関係である

は割りと有名な公式で，例えば

mathlog.info

などにある．