10/09/15 01:07:02
>>8
略解：
n≧2のときを考える。
D1：＝ { (x,y)∈R^2｜1≦x≦n－1 , 0≦y≦log_[2]x }
D2：＝ { (x,y)∈R^2｜0≦y≦log_[2](n－1) , 0≦x≦2^y }
と置く。D1に含まれる格子点の個数がf(n)である。
D2に含まれる格子点の個数をg(n)と置けば、
D1∪D2 ＝ { (x,y)∈R^2｜0≦x≦n－1 , 0≦y≦log_[2](n－1) } (長方形)
となるから、f(n)＋g(n)＝n*(1＋[log_[2](n－1)]) となる。g(n)は簡単に
計算できてるので詳細は省略する。最終的に、
f(n) ＝ n*(1＋[log_[2](n－1)]) ＋ 1－2^*(1＋[log_[2](n－1)]) (n≧2)
となる。