面白い問題おしえて～な十七問目

面白い問題おしえて～ ..

15:１３２人目の素数さん
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)

となる。

次ページ

続きを表示

1を表示