2016年1月12日火曜日

160112(2)

Ruby


n と互いに素なn 未満の自然数の和

確か中学1, 2 年の頃、以下のように考えた。
(その後大学2, 3 年の頃、反転公式を使う別証明を習ったが、
こっちの方が素直なやり方だと思う。)
例えば、n = 12 のとき、
n と互いに素なn 未満の自然数は、
1, 5, 7, 11 の4 (= φ(12)) 個あるが、
(1 + 11) / 2 = 6,
(5 + 7) / 2 = 6
となるので、これらの平均は12 / 2 である。
よって、これらの和は(12 / 2) × φ(12)。
一般のn では次のようになる。
n と互いに素なn 未満の自然数がφ(n) 個あり、
(a, n) = 1 ならば、(n - a, n) = 1 なので、
これらの平均はn / 2 である。
よって、これらの和は(n / 2) × φ(n)。

(n / 2) × φ(n) を使う方法と
n と互いに素なn 未満の自然数を足し合わせる方法の
両方をコードにしてみた。

オンライン整数列大辞典の
A000010(http://oeis.org/A000010/list)、
A023896(http://oeis.org/A023896/list)
と比較し、答え合わせしてみる。

def f(n)
  return 1 if n == 1
  (1..n - 1).select{|i| i.gcd(n) == 1}.size
end

def g1(n)
  return 1 if n == 1
  (1..n - 1).select{|i| i.gcd(n) == 1}.size * n / 2
end

def g2(n)
  return 1 if n == 1
  (1..n - 1).select{|i| i.gcd(n) == 1}.inject(:+)
end

def A000010(n)
  (1..n).map{|i| f(i)}
end

def A023896_1(n)
  (1..n).map{|i| g1(i)}
end

def A023896_2(n)
  (1..n).map{|i| g2(i)}
end

ary = A000010(69)
# OEIS A000010のデータ
ary0 =
[1,1,2,2,4,2,6,4,6,4,10,4,12,6,8,8,16,6,18,8,12,
 10,22,8,20,12,18,12,28,8,30,16,20,16,24,12,36,18,
 24,16,40,12,42,20,24,22,46,16,42,20,32,24,52,18,
 40,24,36,28,58,16,60,30,36,32,48,20,66,32,44]
# 一致の確認
p ary == ary0

ary1 = A023896_1(56)
ary2 = A023896_2(56)
# OEIS A023896のデータ
ary0 =
[1,1,3,4,10,6,21,16,27,20,55,24,78,42,60,64,136,
 54,171,80,126,110,253,96,250,156,243,168,406,120,
 465,256,330,272,420,216,666,342,468,320,820,252,
 903,440,540,506,1081,384,1029,500,816,624,1378,
 486,1100,672]
# 一致の確認
p ary1 == ary0
p ary2 == ary0

出力結果
true
true
true

0 件のコメント:

コメントを投稿

注: コメントを投稿できるのは、このブログのメンバーだけです。