16519：条件を満たす関数fを見つけよ...

問題16519・・・http://d.hatena.ne.jp/turuhashi/searchdiary?of=10&word=%2A%5B%A1%D8%CC%E4%C2%EA%B2%F2%B7%E8%A1%D9%5D より 引用 Orz〜

自然数の集合{1,2,3,4,・・}をNで表す。
関数ｆが全てのn∈Nに対し、f(1)=1,f(2n)=f(n)かつf(2n+1)=f(2n)+1を
満たすとする。f(n)を表すきれいで単純で長くても1文で書ける
アルゴリズムを見つけよ。

解答

・わたしの...

f(n)=[(n-1)/2+1]

でいけてるんじゃないかいなぁ ^^...?

↑

ダメでした ^^; Orz...

↓

・鍵コメT様からの鮮やかなもの Orz〜

f(4)=f(2)=f(1)=1のはずですが，
f(n)=[(n-1)/2+1]だと，f(4)=2になってしまいますね．

f(n)は，(nを2で割った余り)+f(nを2で割った商)
となるので，これは「nを2進法で表した時の数字1の個数」を表しています．

*なるほど!!...気づけなかった...^^;

「n-(n!の素因数2の個数)」という答え方もあります．

*これ面白いけど...なぜそう言えるのかわからず...^^;...

[スモークマン]

＞0:34amの鍵コメT様へ ^^
そっかぁ...^^;
別解の方は俄かにゃわからない...^^;;
紹介させていただきまっす〜m(_ _)m〜v