数列

質問

今，数列
-[-iα]　α∈(0,1]，i=1,2,…,n
までの和を求めたいのですが，うまく行きません．

考える過程でしょうもない公式
-[-z-q]=z-[-q], z∈整数，q∈有理数
は作れたのですが，結局とけません．

なにかヒントありましたら，頂けませんでしょうか？
ひょっとして無理なのかなとも思っています

回答No.7

stomachman · ベストアンサー

仕上げです。

α≧1の場合には、
S(α,n)
　= S(floor(α)+(α-floor(α)),n)
　= S(floor(α),n)+S(α-floor(α),n)
　= floor(α)(Σ<i=1～n>i )+S(α-floor(α),n)
　= floor(α)n(n+1)/2+S(α-floor(α),n)
R(α,n)
　= R(floor(α)+(α-floor(α)),n)
　= R(floor(α),n)+R(α-floor(α),n)
　= floor(α)n(n+1)/2+R(α-floor(α),n)
また、α＜0の場合には、
S(α,n)
　= Σ<i=1～n>ceiling(αi)
　= -Σ<i=1～n>floor(-αi)
　= -R(-α,n)
R(α,n) = -S(-α,n)
となります。

かくて、このアルゴリズムは完成。

計算例として、α=1/π、n=floor(1000e)の場合をやってみました。

S(0.318309886, 2718) = 1230031 - R(0.141592654, 864)
R(0.141592654, 864) = 45620 + R(0.937486694, 121)
R(0.937486694, 121) = 7381 - S(0.062513306, 121)
S(0.062513306, 121) = 542 - R(0.996594407, 6)
R(0.996594407, 6) = 21 - S(0.003405593, 6)
S(0.003405593, 6) = 6 - R(0.634590875, -1)
R(0.634590875, -1) = 0

従って、
R(0.634590875, -1) = 0
S(0.003405593, 6) = 6 - 0 = 6
R(0.996594407, 6) = 21 - 6 = 15
S(0.062513306, 121) = 542 - 15 = 527
R(0.937486694, 121) = 7381 - 527 = 6854
R(0.141592654, 864) = 45620 + 6854 = 52474
S(0.318309886, 2718) = 1230031 - 52474 = 1177557…答
という具合です。

お礼

お返事がおそくなりました．

stomachmanさまの回答，解読させていただきました．

収束のはやさまで考えていただいて有難うございました．

本当にありがとうございました．

回答No.6

stomachman

またまたstomachmanです。
前の回答では実用上問題がある。どういうことかというと、S(α,n)、あるいはR(α,n)を求める場合、αが1に近い値であると、繰り返しが多くなってしまうんです。Rを繰り返し計算していく内にいったん1に近い値が現れると、収束が遅い。

そこで、
S(α,n) = Σ<i=1～n>(ceiling(iα))= n(n+1)/2-R(1-α,n)
R(α,n) = Σ<i=1～n>floor(iα)= n(n+1)/2-S(1-α,n)
を利用することにしました。これは
ceiling(iα)=i-floor(i(1-α))
floor(iα)=i-ceiling(i(1-α))
だから成り立つのです。

すなわち、以下のようにして計算を行います。
S(α,n) =
if α=0 又は n≦0 then
　　0
elseif α< 1/2 then
　　β=1/α-floor(1/α) ,
　　m=ceiling(nα)-2 ,
　　(m+2)n - floor((m+1)/α) - (m(m+1)/2)floor(1/α) - R(β,m)
else
　　n(n+1)/2-R(1-α,n)
であり、

R(α,n) =
if α=0 又は n≦0 then
　　0
elseif α < 1/2 then
　　β = ceiling(1/α)-1/α ,
　　m=floor(nα)-1 ,
　　(m+1)(n+1) - ceiling((m+1)/α) - (m(m+1)/2)ceiling(1/α) + R(β,m)
else
　　n(n+1)/2-S(1-α,n)
です。

この手を使えば、S,Rの一つ目の引数はαか1-αの小さい方であり、それは必ず1/2より小さい。つまりm=ceiling(nα)-2 もしくはm=floor(nα)-1によって、確実にm≦n/2ですから、最悪でも概ね log(n) （logは2の対数）の繰り返し回数で計算が終わることが保証できます。

回答No.5

stomachman

●No.2の訂正、追加です。
No.2では[4]の後半で間違えてしまいました。すいません。

【A】R(β,m)の漸化式
R(β,m)=Σ<i=1～m>[iβ]=Σ<i=1～m>floor(iβ) （ただし0≦β≦1）
をきちんとやっつけましょう。やりかたはS(α,n)と同じようなものです。

まず、m≦0またはβ=0の場合はR(β,m)=0です。

0＜β≦1の場合には、
L[β,j] = {i| i∈N-{0}∧floor(iβ)=j}
と定義すると、以下の事が言えます。
Nを自然数(0を含む)の集合とするとき、∀j≧0について、
・L[β,j] = {i| i∈N かつ j≦iβ＜j+1} = {i| i∈N かつ j/β≦i＜(j+1)/β}
・L[β,j]≠φ　（∵0＜β≦1だから）
・max L[β,j]+1=min L[β,j+1]
・min L[β,j] = ceiling(j/β)
・|L[β,j]| = min L[β,j+1]-min L[β,j] = ceiling((j+1)/β)-ceiling(j/β)
・Σ<i∈L[β,j] > floor(iβ) = |L[β,j]| j

ここで
U(β,k)=Σ<j=1～k>(|L[β,j]| j)
とおくと、（0＜β≦1かつm＞0のとき）
R(β,m) =(floor(mβ))(m-min L[β,floor(mβ)]+1) ＋ U(β,floor(mβ)-1)
=(floor(mβ))(m-ceiling(floor(mβ)/β)+1) ＋ U(β,floor(mβ)-1)
となります。

さて、
U(β,k)=Σ<j=1～k>(|L[β,j]| j)
=Σ<j=1～k>(ceiling((j+1)/β)j-ceiling(j/β)j)
=Σ<j=1～k>j ceiling((j+1)/β)-Σ<j=1～k>j ceiling(j/β)
=Σ<j=0～k>j ceiling((j+1)/β)-Σ<j=1～k>j ceiling(j/β)
=Σ<j=1～k+1>(j-1) ceiling(j/β)-Σ<j=1～k>j ceiling(j/β)
=k ceiling((k+1)/β)-Σ<j=1～k>ceiling(j/β)
ここで
β'= ceiling(1/β)-1/β
とおくと、
ceiling(j/β)=ceiling(j (ceiling(1/β) -β'))
　= ceiling(j (ceiling(1/β)) - ceiling(jβ')
　= j ceiling(1/β) - ceiling(jβ')
だから、
Σ<j=1～k>ceiling(j/β)
= Σ<j=1～k>j ceiling(1/β) - Σ<j=1～k>ceiling(jβ')
= (k(k+1)/2)ceiling(1/β) - Σ<j=1～k>ceiling(jβ')
= (k(k+1)/2)ceiling(1/β) - R(β',k)
よって
U(β,k)=k ceiling((k+1)/β)-(k(k+1)/2)ceiling(1/β)+R(β',k)
です。

ここでさらに
m' = floor(mβ)-1
とおくと、
R(β,m) =(m'+1)(m-ceiling((m'+1)/β)+1) ＋ U(β,m')
=(m'+1)(m-ceiling((m'+1)/β)+1) ＋ m' ceiling((m'+1)/β)-(m'(m'+1)/2)ceiling(1/β)+R(β',m')
=(m'+1)(m+1)-ceiling((m'+1)/β)-(m'(m'+1)/2)ceiling(1/β)+R(β',m')
となります。

したがって、
β[0]=β, β[p+1] = ceiling(1/β[p])-1/β[p]
m[0]=m, m[p+1]=floor(m[p]β[p])-1
とすれば、
R(β[p],m[p])=(m[p+1]+1)(m[p]+1) - ceiling(m[p+1]+1)/β[p]) - (m[p+1](m[p+1]+1)/2)ceiling(1/β[p]) + R(β[p+1],m[p+1])
というRに関する漸化式が得られました。

【B】 Σ<j=1～n' -1> floor(j/α) の計算
α'= 1/α-floor(1/α)
n' = ceiling(nα)-1
とおくと、
Σ<j=1～n' -1>floor(j/α)
=Σ<j=1～n' -1>floor(j(floor(1/α)+α'))
= Σ<j=1～n' -1>j floor(j floor(1/α)) + Σ<j=1～n' -1>floor(jα')
= Σ<j=1～n' -1>j floor(1/α) + Σ<j=1～n' -1>floor(jα')
= (n'(n' -1)/2)floor(1/α) +Σ<j=1～n' -1>floor(jα')
= (n'(n' -1)/2)floor(1/α) + R(α',n' -1)

【C】正しいS(α,n)
既にNo.2の[1]～[3]で求めたとおり、
S(α,n) =(ceiling(nα))(n-floor((ceiling(nα)-1)/α)) ＋ T(α,ceiling(nα)-1)
T(α,n' ) = n' floor(n' /α)-Σ<j=1～n' -1> floor(j/α)
です。ここで【B】を使って
T(α,n' ) = n' floor(n' /α) - (n'(n' -1)/2)floor(1/α) - R(α',n' -1)
ゆえに、
S(α,n) =(ceiling(nα))(n-floor((ceiling(nα)-1)/α)) ＋ T(α,ceiling(nα)-1)
=(n'+1)(n-floor(n'/α)) ＋ T(α,n')
= (n'+1)(n-floor(n'/α)) ＋ n' floor(n' /α) - (n'(n' -1)/2)floor(1/α) - R(α',n' -1)
= (n'+1)n - floor(n'/α)) - (n'(n' -1)/2)floor(1/α) - R(α',n' -1)
です。

●答
以上【A】【C】から、

S(α,n) = (m[0]+2)n-floor((m[0]+1)/α)-(m[0](m[0]+1)/2)floor(1/α)-R(β[0],m[0])

ここに、
β[0]=1/α-floor(1/α)
m[0]=ceiling(nα)-2
β[p+1] = ceiling(1/β[p])-1/β[p]
m[p+1]=floor(m[p]β[p])-1

R(β[p],m[p])は、もしβ[p]=0 またはm[p]≦0なら R(β[p],m[p])=0で、さもなくば
R(β[p],m[p])=(m[p+1]+1)(m[p]+1) - ceiling(m[p+1]+1)/β[p]) - (m[p+1](m[p+1]+1)/2)ceiling(1/β[p]) + R(β[p+1],m[p+1])

となります。

回答No.4

hismix

No.1のhismixです
＞「k進展開」とはk進数に表示を改めることですか？
全くその通りです
定義してない用語使ってごめんね～

回答No.3

stomachman

No.2の回答。やっちまいました。毎度の計算間違いです。

S(α,n) はceilingに関する和なのに、最後の漸化式にするところでfloorに関する和S(1/α,k)とごっちゃにしてしまっています。

基本的考え方は同じなので、少々手直しすれば良いのですが、暫くお待ち下さい。

回答No.2

stomachman

とりあえず、ひとつのアプローチを検討してみました。
[1] 準備
-[-iα]　α∈(0,1]，i=1,2,…,n
[x]はガウスの記号ですね。xを越えない最大の整数。別名floor(x)。
つまり-[-x]とは、xより小さくない最小の整数。別名ceiling(x)です。この記号を使うと
S(α,n)=Σ<i=1～n>(-[-iα])
=Σ<i=1～n>ceiling(iα)
と書けます。以後、ガウスの記号はまぎらわしいので使わないことにしましょう。
αに関する条件から、
・ceiling(iα)はiについて、弱い単調増加。すなわち ceiling((i+1)α)≧ceiling(iα)である。
・任意のj∈{1,2,....,ceiling(nα)}について、ceiling(iα)=jを満たすiが少なくとも一つ存在する。
が分かります。

[2] 問題の分割
K[j] = {i| i∈N-{0}∧ceiling(iα)=j}
つまり与えられた正の自然数jについてceiling(iα)=jを満たす正の自然数iの集合K[j]を考えます。その要素の数を|K[j]|と表します。
たとえばα=0.3とすると
K[α,1]={1,2,3}, K[α,2]={4,5,6},K[α,3]={7,8,9,10},K[α,4]={11,12,13},.....
という具合。ついでにK[α,0]={0}と定義しておきましょう。
当然ながら
・K[α,j] = {i| j-1＜iα≦j}
・K[α,j]≠φ　（0＜α≦1だから）
です。min Xを集合Xの中の最小の要素、max Xを集合Xの中の最大の要素のことと定義すると
・max K[α,j]+1=min K[α,j+1]
・|K[α,j]| = min K[α,j+1]-min K[α,j] = max K[α,j]-max K[α,j-1]
も自明でしょう。
　そうするとi∈{1,2,....}の内でceiling(iα)=jである様なiの集合がK[α,j]である。
そのようなiだけについて、ceiling(iα)の部分和を作ると
Σ<i∈K[α,j] > ceiling(iα) = |K[α,j]| j
です。だからこの部分和をj=1,2,....,ceiling(nα)-1について足し合わせると
Σ<j=1～ceiling(nα)-1>(|K[α,j]| j)
となります。あと残っているのは ceiling(iα)=ceiling(nα) となるiだけで、このようなiは
min K[α,ceiling(nα) ]～nまで、つまりn-min K[α,ceiling(nα)]+1 個ある。

従って、
T(α,k)=Σ<j=1～k>(|K[α,j]| j)
とおくと
S(α,n) =(ceiling(nα))(n-min K[α,ceiling(nα)]+1) ＋ T(α,ceiling(nα)-1)
となります。

[3] min K[α,ceiling(nα)]
min K[α,ceiling(nα)]=max K[α,ceiling(nα)-1]+1
とも書けます。
α＞0より
max K[α,ceiling(nα)-1]-1=max{i| ceiling(nα)-2＜iα≦ceiling(nα)-1}+1
　=max{i| (ceiling(nα)-2)/α＜i≦(ceiling(nα)-1)/α}+1
　=floor((ceiling(nα)-1)/α)+1
です。だから
S(α,n) =(ceiling(nα))(n-floor((ceiling(nα)-1)/α)) ＋ T(α,ceiling(nα)-1)

[4] T(α,k)を求める。
|K[α,j]| = max K[α,j]-max K[α,j-1]
ですから、max K[α,j]を求めることが出来れば、|K[α,j]| が分かります。そしてα＞0より、
K[α,j] ={i| j-1＜iα≦j} = {i| (j-1)/α＜i≦j/α}
ですから、
max K[α,j] = floor(j/α)
であることが分かります。（j=0の場合にもfloor(0)=0=maxK[0]は成り立っています。）よって、
|K[α,j]| = floor(j/α)-floor((j-1)/α)
です。これを使うと、
T(α,k)=Σ<j=1～k>(|K[j]| j)
=Σ<j=1～k>j floor(j/α)-Σ<j=1～k>j floor((j-1)/α)
=Σ<j=1～k>j floor(j/α)-Σ<j=0～k-1>(j+1) floor(j/α)
= floor(0)+k floor(k/α)+Σ<j=1～k-1>(j floor(j/α)-(j+1) floor(j/α))
= k floor(k/α)-Σ<j=1～k-1> floor(j/α)
だから
S(1/α,k-1)=Σ<j=1～k-1> floor(j/α)
を求める問題に帰着してしまいました。一見元の木阿弥のようですが、S(α,n)を直接計算するのに比べると手間がα倍程度に減っています。
さて、
a[0]=α, a[1]=1/a[0]-floor(1/a[0])
N[0]=n, N[1]=ceiling(N[0]a[0])-1
としますと、0≦a[1]≦1
floor(j/a[0])=floor(j(floor(1/a[0])+a[1])) = j floor(1/a[0])+floor(ja[1])
だから
S(1/a[0],k-1)=(floor(1/a[0]))Σ<j=1～k-1> j ＋Σ<j=1～k-1>floor(ja[1])
=(floor(1/a[0]))k(k-1)/2 ＋Σ<j=1～k-1>floor(ja[1])
=(floor(1/a[0]))k(k-1)/2 ＋S(a[1],k-1)
です。a[1]=0だったらS(a[1],k-1)=0になって、これで出来上がりですから、0＜a[1]≦1の場合だけ考えることにしましょう。

[5] 漸化式
求めたかったのは
S(α,n) =(ceiling(nα))(n-min K[α,ceiling(nα)]+1) ＋ T(α,ceiling(nα)-1)
でしたから
S(α,n)
=S(a[0],N[0])
　= (ceiling(N[0]a[0]))(N[0]-floor((ceiling(N[0]a[0])-1)/a[0])) ＋ T(a[0],N[1])
　= (ceiling(N[0]a[0]))(N[0]-floor((ceiling(N[0]a[0])-1)/a[0])) ＋ N[1] floor(N[1]/a[0]) - (floor(1/a[0]))N[1](N[1]-1)/2 - S(a[1],N[1]-1)

かくて、
a[0]=α, N[0]=n,
a[m]=1/a[m-1]-floor(1/a[m-1]), N[m]=ceiling(N[m]a[m])-1　　(m=1,2,...)
とすれば
S(a[m],N[m])
　= (ceiling(N[m]a[m]))(N[m]-floor((ceiling(N[m]a[m])-1)/a[m])) ＋ N[1] floor(N[m+1]/a[m]) - (floor(1/a[m]))N[m+1](N[m+1]-1)/2 - S(a[m+1],N[m+1]-1)
というとんでもねえ漸化式が得られます。
a[m] (m=0,1,....)はいずれも1以下なので、N[m]-1は単調減少します。そしていずれ S(a[m+1],N[m+1]-1)が（a[m+1]=0もしくはN[m+1]-1≦0となって）０になるまでこの計算を反復すればよく、計算量がかなり減っていることがわかります。

[6] 漸化式の一般項
で、この漸化式の一般項が求められれば最終解決というわけですが....こいつは手に負えません。

＊この回答は随分中途半端とは思いますけど、No.1の回答もどうかな？　k進展開の小数点以下１桁目を求めて総和を取る、というのは結局[kα]を全てのk=1,2,...,nについて計算することに他ならない訳で、手間は変わらないように思えるんですが。

回答No.1

hismix

STEP１
まずf(α)=Σ[iα]について考えてみると見通しがいいです
以後Σはiを変数として１からｎまでの和をとるものとします　

・α=1のとき
[i]=iですから、f(1)=n(n+1)/2

・０<α<１のとき
ここで記号をひとつ導入しておきます
αをk進展開したときα=０.・・・・と書けますよね
このときの小数点以下第１位の点というのは０,１,・・,k-1のいずれかの値です
この値をα(k)と書くことにしましょう

すると
[α]=α(1),[2α]=α(2),・・・,[nα]=α(n)となっています
これは実際やってみるとすぐにわかります
よって
f(α)=Σα(i)となります

STEP２
では本題に入りましょう
f(α)=Σ-[-iα]と置きます

・α=1のとき
[-i]=-iより
f(1)=n(n+1)/2となります

・αが０と１の間のi等分点上に無いとき(i=1,2,・・,n)
[iα]=α(i)でした
これより[-iα]=-α(i)-1 ・・・・(1)
ガウス記号の非対称性から-1がでてきました。注意が必要ですね
よって
-[-iα]=α(i)+1
よって
f(α)=n(n+1)/2+Σα(i)

最後にちょっと厄介なのが

・αが０と１の間のi等分点上にあるとき(i=1,2,・・,n)
これは一体どういうときかというと
例えばα=1/2のときです
このときi=2のときを見ると[-iα]=[-1]=-1となりますが
α(2)=1より(1)が成立しません
だからこのような場合分けが必要だったんです

今αがj1,j2,・・,js等分点上にあったとしましょう
すると
i=j1,j2,・・,jsのときは
-[-iα]=α(i)
i≠j1,j2,・・,jsのときは
-[-iα]=α(i)+1

よって以上より
f(α)=t(t+1)/2+Σα(i)
ここでt=n-sとする

眺めていると難しそうですが、やってみるとすぐ分かると思います
また分からなかったら聞いてください

お礼

ありがとうございます．

１つ伺わせてください．
用語：「k進展開」とはk進数に表示を改めることですか？