関数の問題

質問

関数gは任意の非負整数mに関して以下の性質を持ちます。
g(2m)=g(g(m))
g(2m+1)=g(2m)+1

例えば、もしg(0)=0なら、g(k)は任意の非負整数ｋに対して非負整数の値を返します。（これは数学的帰納法で証明できます）
しかしながら、もしg(0)=１とすると、関数ｇは矛盾をはらむのでg(0)は１に等しくならないことが分かります。（これも比較的簡単に証明できます）
また同様に任意の非負整数ｋに対して、g(0)=2^k としたり、g(0)=2^k + 2 としたりすると、矛盾を導きます。
それでは、どのような非負整数にg(0)が等しければ、関数gは矛盾をはらまずに任意の非負整数ｋに対してg(k)が非負整数の値を返すでしょうか。
もし何かそのようなg(0)の値に決まった性質があったら教えてください。

回答No.1

muturajcp

非負整数mに対して
g(2m)=g(g(m))
g(2m+1)=g(2m)+1
とする

g(0)=1
と仮定すると
1=g(0)=g(g(0))=g(1)=g(0)+1=2
となって矛盾するからg(0)≠1

自然数kに対して
g(0)=2^k
と仮定する
g(1)=g(0)+1=2^k+1
だから
n=1のときg(2^{n-1})=2^k+1が成り立つ
ある自然数nに対してg(2^{n-1})=2^k+1を仮定すると
g(0)=2^kは偶数だから
g(2^n)=g(g(2^{n-1})=g(2^k+1)=g(2^k)+1=g(g(0))+1=g(0)+1=2^k+1
だから
任意の自然数nに対してg(2^{n-1})=2^k+1が成り立つから
n=k+1のときも成り立つから
g(2^k)=2^k+1
2^k=g(0)=g(g(0))=g(2^k)=2^k+1
となって矛盾するからg(0)≠2^k

自然数k≧3に対して
g(0)=2^k-2
と仮定する
g(1)=g(0)+1=2^k-1
g(2)=g(g(1))=g(2^k-1)=g(2^k-2)+1=g(g(0))+1=g(0)+1=2^k-1
g(3)=g(2)+1=2^k
だから
n=1のときg(2^{n-1})=2^k-1が成り立つ
ある自然数nに対してg(2^{n-1})=2^k-1を仮定すると
g(2^n)=g(g(2^{n-1})=g(2^k-1)=g(2^k-2)+1=g(g(0))+1=g(0)+1=2^k-1
だから
任意の自然数nに対してg(2^{n-1})=2^k-1が成り立つから
n=k+1のときも成り立つから
g(2^k)=2^k-1
n=1のときg(2^{n+1}-1)=2^kが成り立つ
ある自然数nに対してg(2^{n+1}-1)=2^kを仮定すると
g(2^{n+2}-1)=g(2^{n+2}-2)+1=g(g(2^{n+1}-1))+1=g(2^k)+1=2^k
だから
任意の自然数nに対してg(2^{n+1}-1)=2^kが成り立つから
n=k-2のときも成り立つから
g(2^{k-1}-1)=2^k
2^k-2=g(0)=g(g(0))=g(2^k-2)=g(g(2^{k-1}-1))=g(2^k)=2^k-1
となって矛盾するからg(0)≠2^k-2

g(0)の値として不可能な値は
{2^k}_{整数k≧0},{(2^k)-2}_{整数k≧2}

g(0)の値として可能な値は
0,3,5,7,9,10,12,…

g(0)=3
のとき
g(1)=g(0)+1=4
g(3)=g(g(0))=g(0)=3
g(2)=g(3)-1=2
k=1のときg(2^k)=2
ある自然数kに対してg(2^k)=2を仮定すると
g(2^{k+1})=g(g(2^k))=g(2)=2
だから
任意の自然数kに対して
g(2^k)=2
だから
g(2^k+1)=g(2^k)+1=3

非負整数m=Σ_{k=0～j}(a_k)2^k
の2進表示の全桁の和をs(m)=Σ_{k=0～j}(a_k)
とする
ある自然数nより小さい非負整数mに対して
s(m)が偶数のときg(m)=3
s(m)とmが奇数のときg(m)=4
s(m)が奇数mが偶数のときg(m)=2
となっていると仮定する

s(n)が偶数のとき
nが奇数のとき
n-1が偶数だから
s(n-1)は奇数だから
g(n-1)=2
g(n)=g(n-1)+1=3

s(n)とnが奇数のとき
s(n-1)は偶数だから
g(n-1)=3
g(n)=g(n-1)+1=4

s(n)が奇数
nが偶数のとき
n=(2^k)m
となる自然数k,奇数mが存在する
s(m)=s(n)が奇数だから
g(m)=4
g(2m)=g(g(m))=g(4)=2
k=1のときg((2^k)m)=2
あるkに対してg((2^k)m)=2を仮定すると
g(2^{k+1}m)=g(g((2^k)m))=g(2)=2
任意のkに対してg((2^k)m)=2
g(n)=g((2^k)m)=2
∴
g(0)=3のとき
自然数nの2進表示の全桁の和をs(n)とすると
s(n)が偶数のときg(n)=3=g(0)
s(n)とnが奇数のときg(n)=4=g(0)+1
s(n)が奇数nが偶数のときg(n)=2=g(0)-1
となる