OKWAVEのAI「あい」が美容・健康の悩みに最適な回答をご提案!
-PR-
解決
済み

数列

  • すぐに回答を!
  • 質問No.184994
  • 閲覧数51
  • ありがとう数3
  • 気になる数0
  • 回答数7
  • コメント数0

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

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

なにかヒントありましたら,頂けませんでしょうか?
ひょっとして無理なのかなとも思っています
通報する
  • 回答数7
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

質問者が選んだベストアンサー

  • 回答No.7
レベル14

ベストアンサー率 57% (1014/1775)

仕上げです。

α≧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…答
という具合です。
お礼コメント
noname#2879

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

stomachmanさまの回答,解読させていただきました.

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

本当にありがとうございました.
投稿日時 - 2002-04-03 00:23:13
-PR-
-PR-

その他の回答 (全6件)

  • 回答No.2
レベル14

ベストアンサー率 57% (1014/1775)

とりあえず、ひとつのアプローチを検討してみました。 [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>ceilin ...続きを読む
とりあえず、ひとつのアプローチを検討してみました。
[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となって)0になるまでこの計算を反復すればよく、計算量がかなり減っていることがわかります。

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


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

  • 回答No.1
レベル9

ベストアンサー率 64% (11/17)

STEP1 まずf(α)=Σ[iα]について考えてみると見通しがいいです 以後Σはiを変数として1からnまでの和をとるものとします  ・α=1のとき [i]=iですから、f(1)=n(n+1)/2 ・0<α<1のとき ここで記号をひとつ導入しておきます αをk進展開したときα=0.・・・・と書けますよね このときの小数点以下第1位の点というのは0,1,・・,k-1のいず ...続きを読む
STEP1
まずf(α)=Σ[iα]について考えてみると見通しがいいです
以後Σはiを変数として1からnまでの和をとるものとします 

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

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

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

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

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

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

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

・αが0と1の間の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とする

眺めていると難しそうですが、やってみるとすぐ分かると思います
また分からなかったら聞いてください
お礼コメント
noname#2879

ありがとうございます.

1つ伺わせてください.
用語:「k進展開」とはk進数に表示を改めることですか?
投稿日時 - 2001-12-14 21:10:36
  • 回答No.3
レベル14

ベストアンサー率 57% (1014/1775)

No.2の回答。やっちまいました。毎度の計算間違いです。 S(α,n) はceilingに関する和なのに、最後の漸化式にするところでfloorに関する和S(1/α,k)とごっちゃにしてしまっています。 基本的考え方は同じなので、少々手直しすれば良いのですが、暫くお待ち下さい。
No.2の回答。やっちまいました。毎度の計算間違いです。

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

基本的考え方は同じなので、少々手直しすれば良いのですが、暫くお待ち下さい。
  • 回答No.4
レベル9

ベストアンサー率 64% (11/17)

No.1のhismixです >「k進展開」とはk進数に表示を改めることですか? 全くその通りです 定義してない用語使ってごめんね~
No.1のhismixです
>「k進展開」とはk進数に表示を改めることですか?
全くその通りです
定義してない用語使ってごめんね~
  • 回答No.5
レベル14

ベストアンサー率 57% (1014/1775)

●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<β≦ ...続きを読む
●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.6
レベル14

ベストアンサー率 57% (1014/1775)

またまたstomachmanです。 前の回答では実用上問題がある。どういうことかというと、S(α,n)、あるいはR(α,n)を求める場合、αが1に近い値であると、繰り返しが多くなってしまうんです。Rを繰り返し計算していく内にいったん1に近い値が現れると、収束が遅い。 そこで、 S(α,n) = Σ<i=1~n>(ceiling(iα))= n(n+1)/2-R(1-α,n) R( ...続きを読む
またまた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の対数)の繰り返し回数で計算が終わることが保証できます。
このQ&Aで解決しましたか?
関連するQ&A
-PR-
-PR-
このQ&Aにこう思った!同じようなことあった!感想や体験を書こう
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する
-PR-
-PR-
-PR-

特集


いま みんなが気になるQ&A

関連するQ&A

-PR-

ピックアップ

-PR-
ページ先頭へ