平成２５年10月２7日

[流れ星]

　　　　　第２９８回数学的な応募解答

　　　　　　＜解答募集期間：９月29日〜10月27日＞

［２進法］

ＮＯ１「uchinyan」 09/29 15時10分受信 更新10/27

n! を素因巣分解したときの素因数 2 の指数というのは，

1 〜 n の中に 2 の因数がいくつあるかということ，に注意すれば，要するに，

f(n) は，n を 2 で割っていったときに現れる余りを足していく関数

g(n) は，n を 2 で割っていったときに現れる商を足していく関数

ということです。

(1)

f(0) + g(0) = 0 + 0 = 0

f(1) + g(1) = 1 + 0 = 1

f(2) + g(2) = 1 + 1 = 2

f(3) + g(3) = 2 + 1 = 3

f(4) + g(4) = 1 + 3 = 4

(2)

f(2^n) = f(2^(n-1)) = ... = f(2) = f(1) = 1

f(2^n - 1) = f(2(2^(n-1) - 1) + 1) = f(2^(n-1) - 1) + 1 = ... = f(1) + (n-1) = n

(3)

g(2^n) = g(2^(n-1)) + 2^(n-1) = ...

= g(1) + (1 + 2 + ... + 2^(n-1))

= 1 + 2 + ... + 2^(n-1) = 2^n - 1

g(2^n - 1) = g(2(2^(n-1) - 1) + 1) = g(2^(n-1) - 1) + (2^(n-1) - 1) = ..

= g(1) + ((2^1 - 1) + (2^2 - 1) + ... + (2^(n-1) - 1))

= 2(1 + 2 + ... + 2^(n-2)) - (n-1) = 2(2^(n-1) - 1) - (-1) = (2^n - 1) - n

(4)

予想 f(n) + g(n) = n

証明

n = 0 のとき

f(0) + g(0) = 0 + 0 = 0

で成立。

n が k 以下で成立するとします。

n = k+1 を 2 で割った商を q，余りを r，とすると，

k+1 = 2q + r

ここで，q は k 以下で，r は k+1 が偶数又は奇数にしたがって 0 又は 1 です。

そこで，

f(k+1) = f(q) + r，g(k+1) = g(q) + q

f(k+1) + g(k+1) = (f(q) + r) + (g(q) + q) = (f(q) + g(q)) + q + r

ここで，数学的帰納法の仮定より，f(q) + g(q) = q，なので，

f(k+1) + g(k+1) = (f(q) + g(q)) + q + r = q + q + r = 2q + r = k+1

で成立。

以上より，

f(n) + g(n) = n

がいえました。

(考察＆感想)

n を２進法で表すには，

n を 2 で割っていき，出て来た余りを下１桁から上位桁に向かって順番に並べればいいです。

このときの，余りの和 = 桁の数字の和 = f(n)，商の和 = g)n，となっています。

例えば，15 で確かめてみると．．．

２進法への変換の計算

13

= 2 * 6 + 1

= 2 * (2 * 3 + 0) + 1

= 2 * (2 * (2 * 1 + 1) + 0) + 1

= 1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1

-> 1101

ところが，この式を書き換えると，

13

= 2 * 6 + 1 = 1 + 6 + 6

= 1 + 6 + (2 * 3 + 0) = (1 + 0) + (6 + 3) + 3

= (1 + 0) + (6 + 3) + (2 * 1 + 1) = (1 + 0 + 1) + (6 + 3 + 1) + 1

= (1 + 0 + 1) + (6 + 3 + 1) + (2 * 0 + 1) = (1 + 0 + 1 + 1) + (6 + 3 + 1 + 0)

= f(13) + g(13)

つまり，結局，同じ n に関する式ををどのように式変形するかということだけなので，

実は当たり前のことをもっともらしく尋ねているだけの問題でしたね。

でも，難しげな式で書かれると，何かすごいことのようにも見えてしまうから不思議 (^^;

ＮＯ２「浜田明巳」　10/03 09時30分受信 更新10/27

（１）ｆ(０)＝０
　　　ｆ(１)＝ｆ(０)＋１＝１
　　　ｆ(２)＝ｆ(１)＝１
　　　ｆ(３)＝ｆ(１)＋１＝２
　　　ｆ(４)＝ｆ(２)＝１
　次に，０！＝１！＝１から，
　　ｇ(０)＝ｇ(１)＝０
　２！＝１・２，３！＝１・２・３から，
　　ｇ(２)＝ｇ(３)＝１
　４！＝１・２・３・４から，
　　ｇ(４)＝１＋２＝３
　まとめると，
　　ｆ(０)＋ｇ(０)＝０＋０＝０
　　ｆ(１)＋ｇ(１)＝１＋０＝１
　　ｆ(２)＋ｇ(２)＝１＋１＝２
　　ｆ(３)＋ｇ(３)＝２＋１＝３
　　ｆ(４)＋ｇ(４)＝１＋３＝４

（２）ｆ(２^ｎ)＝ｆ(２^ｎ−１)＝ｆ(２^ｎ−２)＝………＝ｆ(２)＝ｆ(１)＝１
　　　ｆ(２^ｎ−１)＝ｆ(２^ｎ−１−１)＋１＝ｆ(２^ｎ−２−１)＋２＝………
　　　　＝ｆ(２^０−１)＋ｎ＝ｆ(０)＋ｎ＝ｎ

（３）ｇ(２^０)＝ｇ(１)＝０＝２^０−１
　　　ｇ(２^１)＝ｇ(２)＝１＝２^１−１
　　　ｇ(２^２)＝ｇ(４)＝３＝２^２−１
　　　ｇ(２^３)＝ｇ(８)
　８！＝１・２・３・４・５・６・７・８から，
　　　ｇ(２^３)＝１＋２＋１＋３＝７＝２^３−１
　故にｇ(２^ｎ)＝２^ｎ−１と類推できる．
　これを数学的帰納法で証明する．
i). ｎ＝０のとき，ｇ(２^０)＝０となり，成立する．
ii). ｎ＝ｋ（ｋ≧０）のとき，ｇ(２^ｋ)＝２^ｋ−１と仮定する．
　つまり，
　　２^ｋ！＝１・２・３・………・(２^ｋ−１)・２^ｋ
を素因数分解したときの２の指数が，ｇ(２^ｋ)＝２^ｋ−１である．
　ｎ＝ｋ＋１のとき，
　　２^ｋ＋１！＝{１・２・３・………・(２^ｋ−１)・２^ｋ}
　　　　　　　　　　・{(２^ｋ＋１)・(２^ｋ＋２)・(２^ｋ＋３)・………・(２^ｋ＋２^ｋ−１)・(２^ｋ＋２^ｋ)}
を素因数分解したときの２の指数は，
　　ｇ(２^ｋ)＋{ｇ(２^ｋ)＋１}＝２ｇ(２^ｋ)＋１＝２(２^ｋ−１)＋１＝２^ｋ＋１−１
　故にｎ＝ｋ＋１のときも成立する．
　　∴ｇ(２^ｎ)＝２^ｎ−１（ｎは０以上の整数）

　次に，ｇ(２^ｎ−１)は，
　　１・２・３・………・(２^ｎ−１)
を素因数分解したときの２の指数なので，
　　ｇ(２^ｎ)
すなわち，
　　１・２・３・………・(２^ｎ−１)・２^ｎ
を素因数分解したときの２の指数よりも，ｎ少ない．
　　∴ｇ(２^ｎ−１)＝ｇ(２^ｎ)−ｎ＝２^ｎ−１−ｎ

（４）（１）より，ｆ(ｎ)＋ｇ(ｎ)＝ｎと類推できる．これを数学的帰納法で証明する．
i). ０≦ｎ≦２のとき，（１）より成立する．
ii). ０≦ｎ≦２^ｋのとき，成立すると仮定すると，
　　ｆ(ｎ)＋ｇ(ｎ)＝ｎ
　２^ｋ＋１≦ｎ≦２^ｋ＋１のときを考える．
　１≦ｍ≦２^ｋとして，ｆ(２^ｋ＋ｍ)−ｆ(ｍ)を計算する．
　(1) ｍ＝２^ｋのとき，
　　ｆ(２^ｋ＋２^ｋ)−ｆ(２^ｋ)＝ｆ(２^ｋ＋１)−ｆ(２^ｋ)＝１−１＝０
　(2) ２≦ｍ≦２^ｋ−１のとき，
　　ア). ｍ＝２ｓのとき（ｓ≧１），
　　　ｆ(２^ｋ＋ｍ)−ｆ(ｍ)＝ｆ(２^ｋ＋２ｓ)−ｆ(２ｓ)＝ｆ(２^ｋ−１＋ｓ)−ｆ(ｓ)
　　イ). ｍ＝２ｓ＋１のとき（ｓ≧１），
　　　ｆ(２^ｋ＋ｍ)−ｆ(ｍ)＝ｆ(２^ｋ＋２ｓ＋１)−ｆ(２ｓ＋１)
　　　　＝{ｆ(２^ｋ−１＋ｓ)＋１}−{ｆ(ｓ)＋１}＝ｆ(２^ｋ−１＋ｓ)−ｆ(ｓ)
　いずれの場合も，
　　ｆ(２^ｋ＋ｍ)−ｆ(ｍ)＝ｆ(２^ｋ−１＋ｓ)−ｆ(ｓ)（ｍ＞ｓ）
となる．
　故に何回かの操作の後に，
　　ｆ(２^ｋ＋ｍ)−ｆ(ｍ)＝ｆ(２^ｔ＋１)−ｆ(１)（ｔ≧１）
となる．これはｍ＝１のときも成立する．
　　∴ｆ(２^ｋ＋ｍ)−ｆ(ｍ)＝{ｆ(２^ｔ−１)＋１}−ｆ(１)＝１

　次に，ｇ(２^ｋ＋ｍ)−ｇ(ｍ)を計算する．
　ｇ(ｍ)は，
　　１・２・３・………・ｍ
を素因数分解したときの２の指数．
　ｇ(２^ｋ＋ｍ)は，
　　(１・２・３・………・２^ｋ)・{(２^ｋ＋１)・(２^ｋ＋２)・(２^ｋ＋３)・………・(２^ｋ＋ｍ)
を素因数分解したときの２の指数．
　　１・２・３・………・２^ｋ
の２の指数は，ｇ(２^ｋ)．
　　(２^ｋ＋１)・(２^ｋ＋２)・(２^ｋ＋３)・………・(２^ｋ＋ｍ−１)・(２^ｋ＋ｍ)
の２の指数は，
　　１≦ｍ≦２^ｋ−１のとき，ｇ(ｍ)
　　ｍ＝２^ｋのとき，ｇ(２^ｋ)＋１
　故に，
　　１≦ｍ≦２^ｋ−１のとき，ｇ(２^ｋ＋ｍ)−ｇ(ｍ)＝ｇ(２^ｋ)
　　ｍ＝２^ｋのとき，ｇ(２^ｋ＋２^ｋ)−ｇ(２^ｋ)＝ｇ(２^ｋ)＋１

　まとめると，
　１≦ｍ≦２^ｋ−１のとき，
　　ｆ(２^ｋ＋ｍ)＋ｇ(２^ｋ＋ｍ)＝{ｆ(ｍ)＋１}＋ｇ(ｍ)＋ｇ(２^ｋ)
　　　＝{ｆ(ｍ)＋ｇ(ｍ)}＋２^ｋ＝ｍ＋２^ｋ
　ｍ＝２^ｋのとき，
　　ｆ(２^ｋ＋２^ｋ)＋ｇ(２^ｋ＋２^ｋ)＝ｆ(２^ｋ)＋２ｇ(２^ｋ)＋１
　　　＝１＋２(２^ｋ−１)＋１＝２^ｋ＋１＝２^ｋ＋２^ｋ
　故に２^ｋ＋１≦ｎ≦２^ｋ＋１のときも成立する．

　i).，ii).から，０以上の整数ｎに対して，ｆ(ｎ)＋ｇ(ｎ)＝ｎ

　ひどいものになってしまいました．２進法を使っていません．
　やはり，エクセルのマクロの方が簡単ですね．
　ｆ(ｎ)＋ｇ(ｎ)＝ｎ（０≦ｎ≦１０００）を確かめました．

Option Explicit
Const max As Long = 1000
Sub Macro1()
     Dim n As Long, dame As Integer
     dame = 0: n = 1
     While dame = 0 And n <= max
       Cells(n, 1).Value = n
       Cells(n, 2).Value = f(n)
       Cells(n, 3).Value = g(n)
       Cells(n, 4).Value = f(n) + g(n)
       If f(n) + g(n) = n Then
         Cells(n, 5).Value = "○"
         n = n + 1
       Else
         Cells(n, 5).vallue = "×"
         dame = 0
       End If
       Range("A" & n).Select
     Wend
     If dame = 0 Then Range("A1").Select
End Sub
Private Function f(ByVal n As Long) As Long
     If n = 0 Then
       f = 0
     ElseIf n Mod 2 = 0 Then
       f = f(n / 2)
     Else
       f = f((n - 1) / 2) + 1
     End If
End Function
Private Function g(ByVal n As Long) As Long
     Dim j As Long, jj As Long
     g = 0
     For j = 1 To n
       jj = j
       While jj Mod 2 = 0
         g = g + 1: jj = jj / 2
       Wend
     Next j
End Function

ＮＯ３「二度漬け白菜」10/17 21時52分受信 更新10/27

「第２９８回数学的な応募問題」 の解答

ペンネーム：二度漬け白菜

(1)g(n)=max{p;(2^p)|n!}=Σ[k=1〜∞]floor(n/(2^k)) です。

f(0)+g(0)=0+0=0,
f(1)+g(1)=(f(0)+1)+0=0+1+0=1,
f(2)+g(2)=f(1)+floor(2/2)=1+1=2,
f(3)+g(3)=(f(1)+1)+floor(3/2)=1+1+1=3,
f(4)+g(4)=f(2)+floor(4/2)+floor(4/4)=1+2+1=4 (答)

(2)f(2^n)=1, f(2^n - 1)=n (答)

nを2進法で n=Σ[i=0〜k]a[k]*(2^i) (a[i]は 0 または 1)
と表示するとき、
「f(n)はa[0],a[1], …,a[k]の中の 1 の個数に等しい」---(*)
ことをnに関する帰納法で証明します。

(証明)0以上の任意の整数nに対して、
f(n)=f(floor(n/2))+n-2*floor(n/2)
が成り立ちます。これを利用します。
(nが偶数のとき、floor(n/2)=n/2, n-2*floor(n/2)=0.
nが奇数のとき、floor(n/2)=(n-1)/2, n-2*floor(n/2)=1.)

n=0 および n=1 のとき(*)は正しい。
N≧2として、 0≦n＜Nなる任意のnについて(*)が正しいと仮定する。
floor(N/2)=Σ[i=1〜k]a[k]*(2^(i-1)) であるので、
帰納法の仮定によりf(floor(N/2))は a[1],a[2], …,a[k]の中の1の
個数に等しい。
また、a[0]=N-2*floor(N/2)であるので、
f(N)=f(floor(N/2))+N-2*floor(N/2)
と合わせると、n=Nのときにも(*)は正しい。(証明終)

(3) g(2^n)=2^n - 1, g(2^n - 1)=2^n - 1 - n (答)

任意の非負整数nに対して、
g(2^n - 1)=b[n], g(2^n)=c[n] とおく。
b[n+1]
=max{p;(2^p)|(2^(n+1)-1)!}
=max{p;(2^p)|(1)*(2)*(3)*…*(2^n)*(2^n + 1)*(2^n + 2)*(2^n + 3)*…*(2^n + 2^n -1)}
=max{p;(2^p)|(1)*(2)*(3)*…*(2^n)} + max{p; (2^p)|(2^n + 1)*(2^n + 2)*(2^n + 3)*…*(2^n + 2^n -1)}
=c[n]+max{p; (2^p)|(2^n + 1)*(2^n + 2)*(2^n + 3)*…*(2^n + 2^n -1)}.
ここで、1≦i≦2^n -1 のとき、max{p; (2^p)|(2^n + i)}=max{p; (2^p)|i}であるので、
max{p; (2^p)|(2^n + 1)*(2^n + 2)*(2^n + 3)*…*(2^n + 2^n -1)}
=max{p; (2^p)|(1)*(2)*(3)*…*(2^n -1)}
=b[n].
よって、b[n+1]=c[n]+b[n] ---(**) が成り立つ。
また、
c[n]=max{p;(2^p)|(1)*(2)*(3)*…*(2^n)}
=max{p;(2^p)|(1)*(2)*(3)*…*(2^n - 1)}+max{p;(2^p)|(2^n)}
=b[n]+n.
つまり、c[n]=b[n]+n ---(***) が成り立つ。
(**)および(***)とから、c[n]=2^n - 1, b[n]=2^n - 1 - n となる。

(4)「 f(n)+g(n)=n 」---(****) であると類推できる。

この類推が正しいことをnに関する帰納法で証明する。
(証明) n=0,1,2,3,4のときには(****)は正しい。(このことは(1)で既に示した)
N≧5として、0≦n＜Nなる任意のnについて(****)が正しいと仮定する。
N=2^m + k (mは0以上の整数、kは0≦k≦2^m - 1 を満たす整数)　と表せる。
ここで、k≦N-1 に注意。
f(N)+g(N)
=f(2^m + k)+g(2^m + k)
=f(2^m)+f(k)+g(2^m)+g(k)
=1+f(k)+(2^m - 1)+g(k)
=f(k)+g(k)+2^m
=f(k)+g(k)+(N-k)
=k+(N-k) (∵帰納法の仮定により、(N-1)以下のすべての非負整数kに対してf(k)+g(k)=k)
=N.
よって、n=Nでも(****)は正しい。
以上より任意の非負整数nに対して、 f(n)+g(n)=n が成り立つ。(証明終
-------------------------------------------------------------------------n=0,1,2,3,… に対するf(n)の値を列挙してみると、
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, … となります。
この数列はOEISに登録されていますね。
http://oeis.org/A000120
どうやら、f(n)の一般項は簡潔な形には書けないようですね。
次のような不等式が成立します。
f(n^2)≦(1/2)*f(n)*(f(n)+1).

＜水の流れ：f(n)の値が数列として登録されているとは知りませんでした。参考にします。＞

ＮＯ４「にいばりZ12」10/28 18時43分受信 更新10/28

（1） （１）

（2） f(0)=0

f(1)= f((1-1)/2)+1=f(0)+1=0+1=1

f(2)= f(2/2) =f(1) =1

f(3)= f((3-1)/2)+1=f(1)+1=1+1=2

f(4)= f(4/2) =f(2) =1

g(0)=0

g(1)=0 ∵1!=2^0

g(2)=1= g(1)+1 ∵2!=2^1×2^0

g(3)=1= g(2)+0 ∵3!=3^1×2^1

g(4)=3= g(3)+2 ∵4!= 2^2×3^1×2^1

∴f(n)+g(n)=n　ただし0≦n≦4・・・・・・・・・解答

(2)

　　　f(2^n)= f(2^(n-1))= f(2^(n-2))= f(2^(n-3))=・・・= f(2^1)= f(1)=1・・・・・・・・・解答

      f(2^n-1)=f((2^n-2-2-2・2-2・2・2・・・-2^(n-1))/2^n)+n

            =f((2^n-2^n)/2^n)+n=f(0)+n=n          

∵-2-2-2・2-2・2・2・・・-2^(n-1)

=-( 2+2+2・2+2・2・2・・・+2^(n-1))

=1+((2^(n-1+1)-1)/(2-1))=-(1+2^n-1)=-2^n

　　　　　　　・・・・・・・・・解答

(3)

      (2^n)!=2ⁿ・(2ⁿ-1) ・(2ⁿ-2) ・(2ⁿ-3) ・(2ⁿ-4)・・・・・・(2ⁿ-(2ⁿ-1))

　　　上式右辺因数(必ずしも素因数ではない)には

　　　2の倍数が2ⁿ/2個

　　　2²の倍数が2ⁿ/2²個

　　　2³の倍数が2ⁿ/2³個

　　　2⁴の倍数が2ⁿ/2⁴個

　　　　　　　・

　　　　　　　・

　　　2ⁿの倍数が2ⁿ/2ⁿ個

　　　よって(2^n)!に含まれる素因数2の個数g(2^n)は

　　　2^n-1+2^n-2+2^n-3+2^n-4+・・・+1

　　　g(2^n)=( 2^n-1+1-1)/(2-1)= 2ⁿ-1・・・・・・・・・回答

　　　g(2^n-1)は(2^n-1)!に含まれる素因数2の個数なので

(2^n)!に含まれる素因数2の個数から2^nに含まれる素因数2の個数ｎを引けばよい

　　　g(2^n-1)=g(2^n)-n= 2ⁿ-1-n・・・・・・・・・回答

※ (2)(3)より　　　f(2^n)+ g(2^n)= 2^n

　　　　　 　　　f(2^n-1)+ g(2^n-1)= 2^n-1

（４）

f(1)+g(1)=1　(1)より明らか

f(n)+g(n)=n を真としたとき

f(n+1)+g(n+1)=n+1

が真で有る事を証明する

準備

i　:　非負整数(0,1,2,3,4,・・・・)

q=p₂^j1 p₃^j2 p₄^j3 p₅^j4 p₆^j5 : 奇素数の累乗の積(p₂, p₃, p₄, p_5,・・・・：3,5,7,11・・・、j_k：非負整数(0,1,2,3,4,・・・・)

とすると、１以上の整数は次式で表される

n=2ⁱq

nを偶奇に分けて証明する

n: 偶数の場合i≠0

f(n)=f(2ⁱq) =f(2^i-1q) =f(2^i-2q)=・・・・・・= f(2⁰q) = f(q)

f(n+1)=f(2ⁱq+1) =f((2ⁱq+1-1)/2) +1= f(2^i-1q) +1= f(q)+1= f(n)+1

g(n+1)= g(n) ∵n+1は奇数なので２を因数に含まない

∴　f(n+1)+ g(n+1)= f(n)+g(n)+1=n+1・・・・�@

n: 奇数の場合

n+1=2ⁱqと置く

f(n) = f(2ⁱq-1)= f((2ⁱq -1-1)/2)+1= f(2^i-1q -1)+1=・・・・= f(q -1)+i= f((q -1)/2)+i

f(n+1)= f(2ⁱq)= f(q)= f((q -1)/2)+1= f(n)+1-i

g(n+1)= g(2ⁱq)= g(2ⁱq-1)+i= g(n)+i   ∵2ⁱq!= (2ⁱq-1)! ×2ⁱq

∴　f(n+1)+ g(n+1)= f(1) +1-i + g(n)+i = f(n)+g(n)+1=n+1・・・・�A

�@ �Aからnが偶奇とも

f(n)+g(n)=n

が成立する事が示され

（１） よりf(0)+g(0)=0が示されているので

非負整数において

f(n)+g(n)=n

が成立する

感想

（4）にすべてが収斂されますが、とても面白く広がりのある問題ですね。

関数ｆ（ｎ）とｇ（ｎ）がこのように補完し合うとは考えもよりませんでした。

この手の方法を使うと数論の問題でいろいろな結果が導けそうです。

皆さん、問題や質問に答えてください。一部でも構いませんから、解答とペンネームを添えて、メールで送ってください。待っています。