2014年9月27日土曜日

140927(2)

Ruby


Lucky prime

Wikipediaによれば、Lucky primeが無限に存在するかどうかは分かっていないらしい。
それはさておき、オンライン整数列大辞典の
A031157(http://oeis.org/A031157/list)
と比較し、答え合わせしてみる。

require 'prime'

# Nは3以上
N = 1123
ary = (1..(N / 2.0).ceil).map{|i| i * 2 - 1}

m = 1
n = ary[m]
while 2 * n <= N   # 次に取り除く数がNを超えなくなるまで続ける。
  ary0 = []
  ary.each_with_index{|e, i|
    if e <=  n
      ary0 << e
    elsif
      if (i + 1) % n != 0
        ary0 << e
      end
    end
  }
  ary = ary0
  m += 1
  n = ary[m]
end

l_prime = []
ary.each{|i|
  l_prime << i if i.prime?
}

# OEIS A031157のデータ
l_prime0 =
[3,7,13,31,37,43,67,73,79,127,151,163,193,211,223,
 241,283,307,331,349,367,409,421,433,463,487,541,
 577,601,613,619,631,643,673,727,739,769,787,823,
 883,937,991,997,1009,1021,1039,1087,1093,1117,
 1123]
# 一致の確認
p l_prime == l_prime0

140927

Ruby


Lucky number

ハッピー数の生成はよく見かけるので、幸福数を生成してみる。
オンライン整数列大辞典の
A000959(http://oeis.org/A000959/list)
と比較し、答え合わせしてみる。

# Nは3以上
N = 303
ary = (1..(N / 2.0).ceil).map{|i| i * 2 - 1}

m = 1
n = ary[m]
while 2 * n <= N   # 次に取り除く数がNを超えなくなるまで続ける。
  ary0 = []
  ary.each_with_index{|e, i|
    if e <=  n
      ary0 << e
    elsif
      if (i + 1) % n != 0
        ary0 << e
      end
    end
  }
  ary = ary0
  m += 1
  n = ary[m]
end

# OEIS A000959のデータ
ary0 =
[1,3,7,9,13,15,21,25,31,33,37,43,49,51,63,67,69,
 73,75,79,87,93,99,105,111,115,127,129,133,135,141,
 151,159,163,169,171,189,193,195,201,205,211,219,
 223,231,235,237,241,259,261,267,273,283,285,289,
 297,303]
# 一致の確認
p ary == ary0

2014年9月21日日曜日

140921

Ruby


約数の和(自身を含む)(ver.2.0)

140823(2)分より短く書いてみた。

require 'prime'

def sum2(i)
  list = [1]
  for a in (i.prime_division.to_a)
    list += list.product((1..a[1]).map{|e| a[0] ** e}).map{|e| e.inject(:*)}
  end
  list.inject(:+)
end

p sum2(24)

出力結果
60

2014年9月7日日曜日

140907(2)

Ruby


経路の和(ver.2.0)
テキストファイルに以下のような行列が書かれている。

11,66,55,33, 1
22,20, 1,99, 2
66,46,42,99, 3
99,44,99,96, 4
88,20,99,33,30
44,44,44,44,44

左上から右下までを上下左右方向(ただし、全ての方向を使用しなくてもよい。)
に移動するとき、経路の和の最小値を求めよ。

ver.1.1を少し変更するだけでよい。

a = []
size = 0
ARGF.each_line{|line|
  ary = line.chomp.split(/,/).map(&:to_i)
  @size = ary.size
  a << ary
  size += 1
}
if size < @size
  (@size - size).times{
    a0 = []
    @size.times{a0 << 1.0 / 0}
    a << a0
  }
elsif size > @size
  for i in (0..size - 1)
    (size - @size).times{
      a[i] << 1.0 / 0
    }
  end
else
end

Size = [size, @size].max
b = Array.new(Size){Array.new(Size){1.0 / 0}}

# スタート
si = 0
sj = 0
# ゴール
gi = size - 1
gj = @size - 1

b[si][sj] = a[si][sj]
q = [[si, sj]]
until q.empty?
  i, j = q.pop
  for ni, nj in [
    ([i + 1, j] if i + 1 < Size),
    ([i, j + 1] if j + 1 < Size),
    ([i - 1, j] if i > 0),
    ([i, j - 1] if j > 0)
  ].compact
    if (new_sum = b[i][j] + a[ni][nj]) < b[ni][nj]
      b[ni][nj] = new_sum
      q.unshift([ni, nj])
    end
  end
end

p b[gi][gj]

出力結果
226

ちなみに以下の経路

11,66,55,33, 1
22,20, 1,99, 2
66,46,42,99, 3
99,44,99,96, 4
88,20,99,33,30
44,44,44,44,44


応用
テキストファイルに以下のような行列が書かれている。

11,66,55,33, 1
22,20, 1,99, 2
66,46,42,99, 3
99,44,99,96, 4
88,20,99,33,30
44,44,44,44,44

(1,0)から(4,4)までを上下左右方向(ただし、全ての方向を使用しなくてもよい。)
に移動するとき、経路の和の最小値を求めよ。

上のコードにおいて
# スタート
si = 1
sj = 0
# ゴール
gi = 4
gj = 4
と変更すると、「171」と求まる。

ちなみに以下の経路

11,66,55,33, 1
22,201,99, 2
66,46,42,99, 3
99,44,99,96, 4
88,20,99,33,30
44,44,44,44,44

140907

Ruby


経路の和(ver.1.1)
テキストファイルに以下のような行列が書かれている。

11,66,55,33, 1
22,20, 1,99, 2
66,46,42,99, 3
99,44,99,96, 4
88,20,99,33,30
44,44,44,44,44

左上から右下までを下方向と右方向のみ移動するとき、
経路の和の最小値を求めよ。

昨日のコードでも「236」と求まるが、
より汎用性のあるコードを書いてみた。

a = []
size = 0
ARGF.each_line{|line|
  ary = line.chomp.split(/,/).map(&:to_i)
  @size = ary.size
  a << ary
  size += 1
}
if size < @size
  (@size - size).times{
    a0 = []
    @size.times{a0 << 1.0 / 0}
    a << a0
  }
elsif size > @size
  for i in (0..size - 1)
    (size - @size).times{
      a[i] << 1.0 / 0
    }
  end
else
end

Size = [size, @size].max
b = Array.new(Size){Array.new(Size){1.0 / 0}}

# スタート
si = 0
sj = 0
# ゴール
gi = size - 1
gj = @size - 1

b[si][sj] = a[si][sj]
q = [[si, sj]]
until q.empty?
  i, j = q.pop
  for ni, nj in [
    ([i + 1, j] if i + 1 < Size),
    ([i, j + 1] if j + 1 < Size)
  ].compact
    if (new_sum = b[i][j] + a[ni][nj]) < b[ni][nj]
      b[ni][nj] = new_sum
      q.unshift([ni, nj])
    end
  end
end

p b[gi][gj]

ちなみに以下の経路

11,66,55,33, 1
22,20, 1,99, 2
66,46,42,99, 3
99,44,99,96, 4
88,20,99,33,30
44,44,44,44,44


応用
テキストファイルに以下のような行列が書かれている。

11,66,55,33, 1
22,20, 1,99, 2
66,46,42,99, 3
99,44,99,96, 4
88,20,99,33,30
44,44,44,44,44

(1,0)から(2,2)までを下方向と右方向のみ移動するとき、
経路の和の最小値を求めよ。

上のコードにおいて
# スタート
si = 1
sj = 0
# ゴール
gi = 2
gj = 2
と変更すると、「85」と求まる。

ちなみに以下の経路

11,66,55,33, 1
22,20, 1,99, 2
66,46,42,99, 3
99,44,99,96, 4
88,20,99,33,30
44,44,44,44,44

2014年9月6日土曜日

140906

Ruby


経路の和(ver.1.0)
テキストファイルに以下のような行列が書かれている。

11,66,55,33
22,20,99,77
66,46,42,11
99,44,21,96
88,20,70,33

左上から右下までを下方向と右方向のみ移動するとき、
経路の和の最小値を求めよ。

a = []
size = 0
ARGF.each_line{|line| 
  ary = line.chomp.split(/,/).map(&:to_i)
  @size = ary.size
  a << ary
  size += 1
}

for i in (0..size - 1)
  for j in (0..@size - 1)
    if i == 0                # 一行目二列目以降は左だけ
      if j != 0
        a[i][j] += a[i][j - 1]
      end
    elsif j == 0             # 二行目以降の一列目は上だけ
      a[i][j] += a[i - 1][j]
    else                     # 二行目以降の二列目以降は左と上
      a[i][j] += [a[i][j - 1], a[i - 1][j]].min
    end
  end
end

p a[-1][-1]

出力結果
265

ちなみに以下の経路

11,66,55,33
22,20,99,77
66,46,42,11
99,44,21,96
88,20,70,33

2014年9月2日火曜日

140902

Ruby


BigMath

require 'bigdecimal'
require 'bigdecimal/math'

include BigMath

p PI(10).to_s
p PI(20).to_s

p E(10).to_s
p E(20).to_s

a = BigDecimal((PI(100) / 3).to_s)
p sin(a, 10).to_s
p sin(a, 20).to_s
p cos(a, 10).to_s
p cos(a, 20).to_s

p BigDecimal.new(2).sqrt(10).to_s
p BigDecimal.new(2).sqrt(20).to_s

出力結果
"0.3141592653589793238462643388813853786957412E1"
"0.3141592653589793238462643383279502883919859293521427E1"
"0.271828182845904523536028752390026306410273E1"
"0.2718281828459045235360287471352662501431940501312544E1"
"0.86602540378443864676372317195984839934691003312503527365831486410260546876206
96662093449417807056893273826955044274342879543627868976E0"
"0.86602540378443864676372317075293618360922677726177827365831486410260546876206
96662093449417807056893273826955044274342879543627868976E0"
"0.499999999999999999999999989308915718660433E0"
"0.50000000000000000000000000000000000112254582427634098E0"
"0.1414213562373095048690567017E1"
"0.141421356237309504880168872420969807825E1"