1/n の小数点第i位から第j位までの和を求めるには？

Question

n を自然数とし、
1/n の小数点第i位から第j位までの和を求める
Rubyのプログラムを教えてください。
可能であれば、そのプログラムにおいて、
j の上限も教えてください。

以下途中経過を示しておきます。

def sum(str, i, j)
  x, y, *z = str.split('')
  z.map(&:to_i)[i - 1..j - 1].inject(:+)
end
# 本来以下のstr に 1 / n の小数点表示がくる
str = 
"0.010309278350515463917525773195876288659793814432989690721649484536082474226804123711340206185567"
p sum(str, 2, 96)    # 1 + 0 + 3 + 0 + … + 5 + 6 + 7 = 432

（追記）2015/07/25 21:57
（回答を受けつけてから気がついたのですが、）
1 / n の小数点表示を用いて解いていただけたら幸いです。

Comments

[KenTerada]

例えば0.12345の，2から4位の和は，2+3+4=9ということでしょうか？それとも，0.0234ということでしょうか？

[ozwk]

まさか自分で考えるの面倒という理由で質問していないでしょうから、「ここまでは出来た」コードを張って下さい

Answer 1

jの上限はメモリが許す限りです。

require 'bigdecimal'
def dec_sum(n, i, j)
  BigDecimal(1r/n, j+1).to_s[i+1..j+1].each_char.map(&:to_i).reduce(&:+)
end
# 使い方
puts dec_sum(7, 3, 8) # => 0.1428571428..のうち285714を全部足して27
puts dec_sum(97,2,96) #=> 431 ← これ、間違いです！

(修正)有効桁数は1つ多めにしないと四捨五入されちゃうときがある。
参考: Ruby docs: library bigdecimal

(追記) 間違っていました＞＜
上のコードではE-nを考慮してなかったです。
E-n部分はmanmanさんの回答を参照して下さい。
で、BigDecimal#to_sに"F"渡すとEじゃなくなるので、それでの回答を

require 'bigdecimal'
def dec_sum(n, i, j)
  BigDecimal(1r/n, j+1).to_s("F")[i+1..j+1].each_char.map(&:to_i).reduce(&:+)
end
# 使い方
puts dec_sum(7, 3, 8) # => 0.1428571428..のうち285714を全部足して27
puts dec_sum(97,2,96) #=> 432

Comments

[manman]

（修正前の）dec_sum(97,2,96)の場合、E-1分位がずれています。
（手前みそですが）私のコードではremainでその分を調整しています。

[raccy]

文字列表記だと"小数点E-n"なのでその文ずれちゃうのですね。
考えてなかったです、ありがとうです。
そして、to_s("F")なるものみつけたので、修正しておきます。

[manman]

短くて素晴らしいコードです。
ただ、1/nが有限小数のとき0が後に続かないので、計算できないときがあります。

[raccy]

有限小数でto_s("F")で作成された文字列がj+2の長さ以下だった場合は、
[i+1..j+1]で単に切り捨てられるだけなので大丈夫みたいです。
すいません、全然考慮してませんでしたが、偶然うまくいくようです。

Answer 2

sun(2, 109, 109) は 0
sum(3, 109, 109) は 3 ですが、いままでの回答例ではこの計算は数秒では終わらないはずです。
1/n の小数表現を 10**9 桁目まで実際に求めているからです。(掲載時間も消費メモリもそれなりに必要)

そこで、小数表現の 数字が循環しない部分、循環する部分を求め、そこから 小数ｎ桁目を得るようにしてみました。この方法だと 10**9 桁目という場合も一瞬で求める事ができます。

# coding: utf-8

# See http://qiita.com/katoy/items/b25696acb91c0d3b1134

# a / b の小数表現を得る。
#  配列 [符号、巡廻しない部分, 巡廻する部分] を返す。
#  例：
#    1/3 => [1, [1], [3]]
#    1/7 -> [1, [0], [1, 4, 2, 8, 5, 7]]
def get_repeat_string(a, b)
  s = []  # 商を保存
  m = []  # 余りを保存
  sign = (1.0 * a / b > 0) ? 1: -1
  a = a.abs
  b = b.abs

  r = a / b
  a = a % b
  s << r

  i = nil
  while a > 0
    m << a
    a = a * 10

    r = a / b
    a = a % b
    s << r
    i = m.index(a)
    break if i != nil # 余りが繰り返されたので
  end

  if i == nil
    [sign, s, []]
  else
    [sign, s[0..i], s[(i + 1)..-1]]
  end
end

# 1/n の小数 i 桁目 .. j 桁目 までの数字の和を求める。
def sum(n, i, j)
  (sign, fix_str, repeat_str) = get_repeat_string(1, n)

  #  1/n の小数 n 桁目の数字を得る。
  def get_nth(n, fix_str, repeat_str)
    if n < fix_str.length - 1
      return fix_str[n + 1]
    else
      return 0 if repeat_str.length == 0

      r = n - fix_str.length
      return repeat_str[r % repeat_str.length]
    end
  end

  sum = 0
  (i..j).each do |x|
    d = get_nth(x, fix_str, repeat_str)
    sum += d
  end
  sum
end

tests = [
  [7, 1, 1, 1],  # 1     => 1
  [7, 1, 2, 5],  # 14    => 5
  [7, 1, 3, 7],  # 142   => 7
  [7, 1, 4, 15], # 1428  => 15
  [7, 1, 5, 20], # 14285 => 20

  [7, 2, 2, 4],  # 4     => 4
  [7, 2, 3, 6],  # 42    => 6
  [7, 2, 4, 14], # 428   => 14
  [7, 2, 5, 19], # 4285  => 19

  # [7, 3, 8, 27],
  # [95, 2, 96, 432]
]
tests.each do |t|
  v = sum(t[0], t[1], t[2])
  # p v
  puts "# fail #{t} -> #{v}}" if t[3] != v
end

p sum(7, 3, 8) # => 0.1428571428..のうち285714を全部足して27
p sum(97,2,96) #=> 432
p sum(3, 10**9, 10**9)  #=> 3
p sum(2, 10**9, 10**9)  #=> 0

Comments

[manman]

「i, j が大きい時は、小数の循環しない部分、循環する部分 (たかだか n 桁のはず)
を計算して、 足し算対象の数字を抽出するようにする必要がありそうです。」
という問題点を自身で解決されたわけですね。

[katoy]

はい。n 桁目の数字を求めることの改善しました。
次の改善点は、合計の計算です。
10**9 桁目から 10**10 桁目の数字の和を求めるのに律儀に n 桁目を求めて足し算をするのは効率が悪いです。
数字の巡廻パターンがわかっているのですから、もっと効率的に足し算の結果を計算することができるはずです。

Answer 3

方針だけを書きます。

1. 1/n の小数部分の数字を1 つずつ得る Stream を作る。
2. その Strem の i 番目から j 番目を得て、毎回 足し算するようにする。

これだと、j の上限は無いとおもわれます。
// 循環小数に扱えるはずだし。

Comments

[raccy]

その方針で作ってみました。
```Ruby
def div_stream(n)
Enumerator.new do |yielder|
i = 1
loop do
i *= 10
yielder << i / n
i %= n
end
end
end

def div_sum(n, i, j)
div_stream(n).take(j).drop(i - 1).inject(&:+)
end

puts div_sum(7, 3, 8) #=> 27
puts div_sum(97, 2, 96) #=> 432
```

[katoy]

↑ 実装例の提示、ありがとうございます。素晴らしい！

[katoy]

↑ のコードの場合、sum(3, 10**9 10**9) は 数秒では返ってきませんでした。(5 分かかりました)

i, j が大きい時は、小数の循環しない部分、循環する部分 (たかだか n 桁のはず)
を計算して、 足し算対象の数字を抽出するようにする必要がありそうです。
この対処をすれば、 計算可能な i, j の範囲を広げることができると思います。

[katoy]

追加情報：
小数表記の 循環する部分、循環しない部分を見つける方法については、
https://github.com/katoy/node-rational　に cooffee-script での例があります。
https://github.com/katoy/node-rational/blob/master/test/testParseRepeatStr.coffee には
1/1, .. 1/120 の場合の小数表記の一覧もあります。
ここでは循環部分を {} で囲って示すという表記になっています。

Answer 4

シンプルに解いてみた。

jの上限はメモリが許す限りです。

require 'bigdecimal'

# 1/nが有限小数でないとき
def sum(n, i, j) 
  if n > 10
    a, remain = BigDecimal("1").div(n, j + n).to_s.split('E-') # 念のためn余分に位をとっている
  else
    a, remain = BigDecimal("1").div(n, j + n).to_s.split('E') # 念のためn余分に位をとっている
  end
  x, y, *z = a.split('')
  z.map(&:to_i).unshift(0 * remain.to_i)[i - 1..j - 1].inject(:+)
end

p sum(7, 3, 8)
p sum(97, 2, 96)

実行結果
27
432

Comments

[manman]

どうもnが10以下でうまくいっていないが、すぐ直せそうだ。

Answer 5

多倍長整数で処理してみました。

# See
#  http://melborne.github.io/2009/01/22/Ruby-Ruby-Problem16/
#  > Rubyで桁の合計を求める

# 1/n の小数点第i位から第j位までの和を求める。
def sum(n, i, j)
  v =  (10 ** j) / n
  v = v % (10 ** (j - i + 1))
  v.to_s.split("").map { |s| s.to_i }.inject(:+)
end

# 動作のチェック
# 1/7 = 0.14285714285714285
tests = [
  [7, 1, 1, 1],  # 1     => 1
  [7, 1, 2, 5],  # 14    => 5
  [7, 1, 3, 7],  # 142   => 7
  [7, 1, 4, 15], # 1428  => 15
  [7, 1, 5, 20], # 14285 => 20

  [7, 2, 2, 4],  # 4     => 4
  [7, 2, 3, 6],  # 42    => 6
  [7, 2, 4, 14], # 428   => 14
  [7, 2, 5, 19], # 4285  => 19
]
tests.each do |t|
  v = sum(t[0], t[1], t[2])
  puts "# fail #{t} -> #{v}}" if t[3] != v
end

Comments

[manman]

私の追記するタイミングが悪かったかもしれません。

Answer 6

###strを使うパターン

def sum(str,i,j)
  i +=1
  total=0
  for n in i..(j+1)
    total += str[n,1].to_i
  end
  total
end

str = 
"0.010309278350515463917525773195876288659793814432989690721649484536082474226804123711340206185567"
p sum(str, 2, 96)

###jが無制限なパターン
検証のしようが無いのですが、多分無制限なはず

def sum(n,i,j)
  total=0
  amari=1
  for num in 1..j do
    b = (amari*10)/n
    if num >= i then total += b end
    if b then print(b) else print(0) end
    amari = ((amari*10)%n)
  end
  total
end
print("1.")
print("\n",sum(97,2,96))

###最初に投稿したもの
限界は14?
※　15桁目以降の数値が1/nのほうと一致しませんし
※　それ以降は成否の検証方法が分からなかったため

def c(n,i,j)
  r=0
  for num in i..j do
    r += ((1.0*10**num)/n).floor % 10
    print(((1.0*10**num)/n).floor % 10, " + ")
  end
  r
end

print(1.0/7, ":  ")
print("= ",c(7,1,16))  
#0.142857142857143:  1 + 4 + 2 + 8 + 5 + 7 + 1 + 4 + 2 + 8 + 5 + 7 + 1 + 4 + 2 + 8 + = 69

Comments

[manman]

print("= ",c(97,2,96)) では合わないようです。

[hirohiro]

1/nの余りと深度を再帰で呼び出しで「c(n,余り*10,深度)」として
深度がjに達するまで実行するように設計すれば無限にいけそうですが、
用があって時間がなくなってしまい、iが1以外の場合とnが2桁以上のときのデバッグが間に合わないためここまでで終わります。

[hirohiro]

strを使った場合と、jが無制限でも多分動作するものを追加しました。

[hirohiro]

似たやり方が無いようなので、ちょっと不安になってきました。
j無制限コードのアルゴリズムも書いておきます。
ループの度に「nで割った数」と「余り」を求め、前者をreturn値に加算し、後者は次のループで10倍します。
sum(7,1,3)なら0回目の余りが1なので
初回は10/7で　商：1　余り：3　合計：1
2回目は30/7で　商：4　余り：2　合計：5
3回目は20/7で　商：2　余り：6　合計：7　となります。
リターン値に設定した変数が桁あふれを起こすまで、処理を継続する事が可能なはずです。

Answer 7

Floatで計算するなら、有効桁数はFloat::DIGになります。環境依存ですが、おそらく15。
有効桁数が15だとすると、jの最大値は"1/nの小数点以下の最初の非ゼロの数値の位置"+14ですね。

def foo(n,i,j)
    fraction = sprintf("%.#{j+1}f",1.0/n)[1..-1]
    fraction[i..j].split(//).inject(0){|sum,x| sum+=x.to_i}
end

BigDecimalライブラリを使うと、任意精度(jの上限無し)にも出来ます。

追記：
BigDecimal版です。j+1のところはjでも良いかもしれないけど考えてません。

require "bigdecimal"

def foo(n,i,j)
    fraction = BigDecimal(1).div(BigDecimal(n),j+1).to_s("f")[1..-1]
    fraction[i..j].split(//).inject(0){|sum,x| sum+=x.to_i}
end