【解答】
・第１問：4938　
・第２問：164293127179　
【方針】
 
まず、n=2^k（k>=0，kは整数）の場合を考える。
 
例えば、n=16 のときは、
 
 0:00000
 1:00001
 2:00010
 3:00011
 4:00100
 5:00101
 6:00110
 7:00111
 8:01000
 9:01001
10:01010
11:01011
12:01100
13:01101
14:01110
15:01111
16:10000
 
半角スペースで区切ると
 0:0 0 000
 1:0 0 001
 2:0 0 010
 3:0 0 011
 4:0 0 100
 5:0 0 101
 6:0 0 110
 7:0 0 111
 
 8:0 1 000
 9:0 1 001
10:0 1 010
11:0 1 011
12:0 1 100
13:0 1 101
14:0 1 110
15:0 1 111
 
16:1 0 000
 
 
n=15のときは、n=7のときの下3桁のパターンが2回あり、
また、8～15までは、最上位桁の1が8個あるので、
以下の様な漸化式が得られる
 
F(15) = F(7) * 2 + 8
 
8，16は、1が1個なので、以下のように変形できる。
 
F(16) = (F(8) - 1) * 2 + 8 + 1
      = 2 * F(8) + 8 - 1
 
これを一般化すると
 
 
F(2^k) = 2 * F(2^(k - 1)) + 2^(k - 1) - 1
 
また、
F(0) = 0
F(1) = 1
である。
 
 
次に、n=2^k+m（k>=0，2^k>m，k，mは整数）の場合を考える。
 
例えば、n=21 のときは、
 
 0:0 0 000
 1:0 0 001
 2:0 0 010
 3:0 0 011
 4:0 0 100
 5:0 0 101
 6:0 0 110
 7:0 0 111
 
 8:0 1 000
 9:0 1 001
10:0 1 010
11:0 1 011
12:0 1 100
13:0 1 101
14:0 1 110
15:0 1 111
 
16:1 0 000
17:1 0 001
18:1 0 010
19:1 0 011
20:1 0 100
21:1 0 101
 
F(21)は、F(15)と、16～21の下4桁の1の数F(5)、16～21の最上位桁の1の数6の和となる。
漸化式では
F(21) = F(15) + F(5) + 6
F(16 + 5) = (F(16) - 1) + F(5) + 5 + 1
          = F(16) + F(5) + 5
 
これを一般化すると、
F(n) = F(2^k + m)
     = F(2^k) + F(m) + m
 
 
よって、F(n)は、
 
F(0) = 0
F(1) = 1
F(n) = F(2^k) + F(m) + m (n=2^k+m（k>=0，2^k>m，k，mは整数）)
F(2^k) = 2 * F(2^(k - 1)) + 2^(k - 1) - 1
 
【言語】
Ruby
 
【コード】
 
@F = {}
def F(n)
  return 0 if n == 0
  return 1 if n == 1
 
  k = Math.log2(n).floor
  m = n - (2 ** k)
 
  if !@F.has_key?(2 ** k)
    @F[2 ** k] = 2 * F(2 ** (k - 1)) + 2 ** (k - 1) - 1
  end
  if !@F.has_key?(m)
    @F[m] = F(m)
  end
  return  @F[2 ** k] + @F[m] + m
end
 
puts F(10 ** 3)
puts F(10 ** 10)
 
 
http://i...content-available-to-author-only...e.com/Dt6SDx
 
 

44CQ6Kej562U44CRCuODu+esrO+8keWVj++8mjQ5MzjjgIAK44O756ys77yS5ZWP77yaMTY0MjkzMTI3MTc544CACuOAkOaWuemHneOAkQoK44G+44Ga44CBbj0yXmvvvIhrPj0w77yMa+OBr+aVtOaVsO+8ieOBruWgtOWQiOOCkuiAg+OBiOOCi+OAggoK5L6L44GI44Gw44CBbj0xNiDjga7jgajjgY3jga/jgIEKCiAwOjAwMDAwCiAxOjAwMDAxCiAyOjAwMDEwCiAzOjAwMDExCiA0OjAwMTAwCiA1OjAwMTAxCiA2OjAwMTEwCiA3OjAwMTExCiA4OjAxMDAwCiA5OjAxMDAxCjEwOjAxMDEwCjExOjAxMDExCjEyOjAxMTAwCjEzOjAxMTAxCjE0OjAxMTEwCjE1OjAxMTExCjE2OjEwMDAwCgrljYrop5Ljgrnjg5rjg7zjgrnjgafljLrliIfjgovjgagKIDA6MCAwIDAwMAogMTowIDAgMDAxCiAyOjAgMCAwMTAKIDM6MCAwIDAxMQogNDowIDAgMTAwCiA1OjAgMCAxMDEKIDY6MCAwIDExMAogNzowIDAgMTExCgogODowIDEgMDAwCiA5OjAgMSAwMDEKMTA6MCAxIDAxMAoxMTowIDEgMDExCjEyOjAgMSAxMDAKMTM6MCAxIDEwMQoxNDowIDEgMTEwCjE1OjAgMSAxMTEKCjE2OjEgMCAwMDAKCgpuPTE144Gu44Go44GN44Gv44CBbj0344Gu44Go44GN44Gu5LiLM+ahgeOBruODkeOCv+ODvOODs+OBjDLlm57jgYLjgorjgIEK44G+44Gf44CBOO+9njE144G+44Gn44Gv44CB5pyA5LiK5L2N5qGB44GuMeOBjDjlgIvjgYLjgovjga7jgafjgIEK5Lul5LiL44Gu5qeY44Gq5ry45YyW5byP44GM5b6X44KJ44KM44KLCgpGKDE1KSA9IEYoNykgKiAyICsgOAoKOO+8jDE244Gv44CBMeOBjDHlgIvjgarjga7jgafjgIHku6XkuIvjga7jgojjgYbjgavlpInlvaLjgafjgY3jgovjgIIKCkYoMTYpID0gKEYoOCkgLSAxKSAqIDIgKyA4ICsgMQogICAgICA9IDIgKiBGKDgpICsgOCAtIDEKCuOBk+OCjOOCkuS4gOiIrOWMluOBmeOCi+OBqAoKCkYoMl5rKSA9IDIgKiBGKDJeKGsgLSAxKSkgKyAyXihrIC0gMSkgLSAxCgrjgb7jgZ/jgIEKRigwKSA9IDAKRigxKSA9IDEK44Gn44GC44KL44CCCgoK5qyh44Gr44CBbj0yXmsrbe+8iGs+PTDvvIwyXms+be+8jGvvvIxt44Gv5pW05pWw77yJ44Gu5aC05ZCI44KS6ICD44GI44KL44CCCgrkvovjgYjjgbDjgIFuPTIxIOOBruOBqOOBjeOBr+OAgQoKIDA6MCAwIDAwMAogMTowIDAgMDAxCiAyOjAgMCAwMTAKIDM6MCAwIDAxMQogNDowIDAgMTAwCiA1OjAgMCAxMDEKIDY6MCAwIDExMAogNzowIDAgMTExCgogODowIDEgMDAwCiA5OjAgMSAwMDEKMTA6MCAxIDAxMAoxMTowIDEgMDExCjEyOjAgMSAxMDAKMTM6MCAxIDEwMQoxNDowIDEgMTEwCjE1OjAgMSAxMTEKCjE2OjEgMCAwMDAKMTc6MSAwIDAwMQoxODoxIDAgMDEwCjE5OjEgMCAwMTEKMjA6MSAwIDEwMAoyMToxIDAgMTAxCgpGKDIxKeOBr+OAgUYoMTUp44Go44CBMTbvvZ4yMeOBruS4izTmoYHjga4x44Gu5pWwRig1KeOAgTE2772eMjHjga7mnIDkuIrkvY3moYHjga4x44Gu5pWwNuOBruWSjOOBqOOBquOCi+OAggrmvLjljJblvI/jgafjga8KRigyMSkgPSBGKDE1KSArIEYoNSkgKyA2CkYoMTYgKyA1KSA9IChGKDE2KSAtIDEpICsgRig1KSArIDUgKyAxCiAgICAgICAgICA9IEYoMTYpICsgRig1KSArIDUKCuOBk+OCjOOCkuS4gOiIrOWMluOBmeOCi+OBqOOAgQpGKG4pID0gRigyXmsgKyBtKQogICAgID0gRigyXmspICsgRihtKSArIG0KCgrjgojjgaPjgabjgIFGKG4p44Gv44CBCgpGKDApID0gMApGKDEpID0gMQpGKG4pID0gRigyXmspICsgRihtKSArIG0gKG49Ml5rK23vvIhrPj0w77yMMl5rPm3vvIxr77yMbeOBr+aVtOaVsO+8iSkKRigyXmspID0gMiAqIEYoMl4oayAtIDEpKSArIDJeKGsgLSAxKSAtIDEKCuOAkOiogOiqnuOAkQpSdWJ5CgrjgJDjgrPjg7zjg4njgJEKCkBGID0ge30KZGVmIEYobikKICByZXR1cm4gMCBpZiBuID09IDAKICByZXR1cm4gMSBpZiBuID09IDEKCiAgayA9IE1hdGgubG9nMihuKS5mbG9vcgogIG0gPSBuIC0gKDIgKiogaykKCiAgaWYgIUBGLmhhc19rZXk/KDIgKiogaykKICAgIEBGWzIgKioga10gPSAyICogRigyICoqIChrIC0gMSkpICsgMiAqKiAoayAtIDEpIC0gMQogIGVuZAogIGlmICFARi5oYXNfa2V5PyhtKQogICAgQEZbbV0gPSBGKG0pCiAgZW5kCiAgcmV0dXJuICBARlsyICoqIGtdICsgQEZbbV0gKyBtCmVuZAoKcHV0cyBGKDEwICoqIDMpCnB1dHMgRigxMCAqKiAxMCkKCgpodHRwOi8vaS4uLmNvbnRlbnQtYXZhaWxhYmxlLXRvLWF1dGhvci1vbmx5Li4uZS5jb20vRHQ2U0R4Cgo=