2015年5月31日日曜日

150531(2)

Ruby


Gauss circle problem(1)

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

def f(r)
  s = 0
  q = r * r
  i = 1
  while q >= 2 * i - 1
    s0 = q / (2 * i - 1)
    if i % 2 == 1
      s += s0
    else
      s -= s0
    end
    i += 1
  end 
  s * 4 + 1
end
ary = (0..46).map{|i| f(i)}

# OEIS A000328のデータ
ary0 =
[1,5,13,29,49,81,113,149,197,253,317,377,441,529,
 613,709,797,901,1009,1129,1257,1373,1517,1653,
 1793,1961,2121,2289,2453,2629,2821,3001,3209,3409,
 3625,3853,4053,4293,4513,4777,5025,5261,5525,5789,
 6077,6361,6625]
# 一致の確認
p ary == ary0

150531

Ruby


Ulam number

昨日以下のサイトで N 以下の Ulam number の効率の良い求め方について質問してみた。
(http://ja.stackoverflow.com/questions/10791/ulam-number-%E3%81%AE%E5%8A%B9%E7%8E%87%E3%81%AE%E8%89%AF%E3%81%84%E6%B1%82%E3%82%81%E6%96%B9%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6)

これを用いて、339以下の Ulam number を求め、
オンライン整数列大辞典の
A002858(http://oeis.org/A002858/list)
と比較し、答え合わせしてみる。

N = 339
ary = [1, 2]
(3..N).each{|i|
  cnt = 0
  k = ary.size - 1
  (0..k - 1).each{|j|
    break if j >= k
    m = i - ary[j]
    while ary[k] > m
      k -= 1
    end
    cnt += 1 if ary[k] == m && j < k
  }
  ary.push(i) if cnt == 1
}

# OEIS A002858のデータ
ary0 =
[1,2,3,4,6,8,11,13,16,18,26,28,36,38,47,48,53,57,
 62,69,72,77,82,87,97,99,102,106,114,126,131,138,
 145,148,155,175,177,180,182,189,197,206,209,219,
 221,236,238,241,243,253,258,260,273,282,309,316,
 319,324,339]
# 一致の確認
p ary == ary0

2015年5月29日金曜日

150529

Ruby


Toothpick Sequence(1)

The Toothpick Sequence and Other Sequences from Cellular Automata
(http://arxiv.org/pdf/1004.3036v2.pdf)
この論文にもとづき、コードを作成してみた。
そして、オンライン整数列大辞典の
A139250(http://oeis.org/A139250/list)
と比較し、答え合わせしてみる。

def t(n)
  return 0 if n == 0
  m = n.to_s(2).size - 1
  n1 = 2 ** m
  i = n - n1
  t = (n1 * n1 * 2 + 1) / 3
  return t if i == 0
  return t + t(i) * 2 + t(i + 1) - 1
end
ary = (0..53).map{|i| t(i)}

# OEIS A139250のデータ
ary0 =
[0,1,3,7,11,15,23,35,43,47,55,67,79,95,123,155,
 171,175,183,195,207,223,251,283,303,319,347,383,
 423,483,571,651,683,687,695,707,719,735,763,795,
 815,831,859,895,935,995,1083,1163,1199,1215,1243,
 1279,1319,1379]
# 一致の確認
p ary == ary0

2015年5月27日水曜日

150527

Ruby


φの和

こちらの記事に(https://codeiq.jp/magazine/2014/08/13926/)
φの和を高速に求める方法が書いてあるのだが、
大事な部分だけを取り出してみた。

以下において、
n = Σφ(d) (d は n の約数) …①
という性質を用いる。
f(n) = Σφ(k) (k は 1〜n)、
g(n) = n * (n + 1) / 2
とおく。

例えば、
Σf([6 / k]) (k は 1〜6)
= f([6 / 1]) + f([6 / 2]) + f([6 / 3]) + f([6 / 4]) + f([6 / 5]) + f([6 / 6])
= φ(1) + φ(2) + φ(3) + φ(4) + φ(5) + φ(6)
+ φ(1) + φ(2) + φ(3)
+ φ(1) + φ(2)
+ φ(1)
+ φ(1)
+ φ(1)
= φ(1)
+ φ(1) + φ(2)
+ φ(1) + φ(3)
+ φ(1) + φ(2) + φ(4)
+ φ(1) + φ(5)
+ φ(1) + φ(2) + φ(3) + φ(6)
= 1 + 2 + 3 + 4 + 5 + 6 (∵①)
= g(6)

一般に、
g(n) = Σf([n / k]) (k は 1〜n) …②
が言える。

②より、
f(n) = g(n) - Σf([n / k]) (k は 2〜n)
また、f(1) = g(1) より、
f  は g で表される。
これを実装すると以下のとおりになる。

@memo = Hash.new

def f(n)
  return 1 if n == 1
  s = n * (n + 1) / 2
  (2..n).each{|k|
    @memo[n / k] = f(n / k) if @memo[n / k] == nil
    s -= @memo[n / k]
  }
  s
end
p f(7777777)

k が大きくなると、
f([n / k])が同じ値になることが多いので、
次のようにまとめると速くなる。

@memo = Hash.new

def f(n)
  return 1 if n == 1
  s = n * (n + 1) / 2
  sq = Math.sqrt(n).to_i

  # 前半部分は普通に計算
  (2..n / sq).each{|k|
    @memo[n / k] = f(n / k) if @memo[n / k] == nil
    s -= @memo[n / k]
  }

  # 後半部分は同じ値になる部分をまとめて計算
  (1..sq - 1).each{|k|
    @memo[k] = f(k) if @memo[k] == nil
    s -= @memo[k] * (n / k - n / (k + 1))
  }
  s
end
p f(7777777)

高速化できたが念のため、
オンライン整数列大辞典の
A002088(http://oeis.org/A002088/list)
と比較し、答え合わせしてみる。

@memo = Hash.new

def f(n)
  return 1 if n == 1
  s = n * (n + 1) / 2
  sq = Math.sqrt(n).to_i

  # 前半部分は普通に計算
  (2..n / sq).each{|k|
    @memo[n / k] = f(n / k) if @memo[n / k] == nil
    s -= @memo[n / k]
  }

  # 後半部分は同じ値になる部分をまとめて計算
  (1..sq - 1).each{|k|
    @memo[k] = f(k) if @memo[k] == nil
    s -= @memo[k] * (n / k - n / (k + 1))
  }
  s
end
ary = (1..56).map{|i| f(i)}.unshift(0)

# OEIS A002088のデータ
ary0 =
[0,1,2,4,6,10,12,18,22,28,32,42,46,58,64,72,80,96,
 102,120,128,140,150,172,180,200,212,230,242,270,
 278,308,324,344,360,384,396,432,450,474,490,530,
 542,584,604,628,650,696,712,754,774,806,830,882,
 900,940,964]
# 一致の確認
p ary == ary0

2015年5月25日月曜日

150525

Ruby


Conway-Guy sequence

オンライン整数列大辞典の
A005318(http://oeis.org/A005318/list)
と比較し、答え合わせしてみる。
(ついでに、A096858 も出力してみた。)

N = 33
b = [0, 1]
ary = [0, 1]
p b[1..-1]
i = 1
while i < N
  j = (Math.sqrt(i * 2) + 0.5).to_i
  k = ary[i] - ary[i - j]
  b = b.map{|l| l + k}.unshift(0)
  ary.push(b[-1])
  p b[1..-1]
  i += 1
end

# OEIS A005318のデータ
ary0 =
[0,1,2,4,7,13,24,44,84,161,309,594,1164,2284,4484,
 8807,17305,34301,68008,134852,267420,530356,
 1051905,2095003,4172701,8311101,16554194,32973536,
 65679652,130828948,261127540,521203175,1040311347,
 2076449993]
# 一致の確認
p ary == ary0

出力結果
[1]
[1, 2]
[2, 3, 4]
[3, 5, 6, 7]
[6, 9, 11, 12, 13]
[11, 17, 20, 22, 23, 24]
[20, 31, 37, 40, 42, 43, 44]
[40, 60, 71, 77, 80, 82, 83, 84]
[77, 117, 137, 148, 154, 157, 159, 160, 161]
[148, 225, 265, 285, 296, 302, 305, 307, 308, 309]
[285, 433, 510, 550, 570, 581, 587, 590, 592, 593, 594]
[570, 855, 1003, 1080, 1120, 1140, 1151, 1157, 1160, 1162, 1163, 1164]
[1120, 1690, 1975, 2123, 2200, 2240, 2260, 2271, 2277, 2280, 2282, 2283, 2284]
[2200, 3320, 3890, 4175, 4323, 4400, 4440, 4460, 4471, 4477, 4480, 4482, 4483, 4
484]
[4323, 6523, 7643, 8213, 8498, 8646, 8723, 8763, 8783, 8794, 8800, 8803, 8805, 8
806, 8807]
[8498, 12821, 15021, 16141, 16711, 16996, 17144, 17221, 17261, 17281, 17292, 172
98, 17301, 17303, 17304, 17305]
[16996, 25494, 29817, 32017, 33137, 33707, 33992, 34140, 34217, 34257, 34277, 34
288, 34294, 34297, 34299, 34300, 34301]
[33707, 50703, 59201, 63524, 65724, 66844, 67414, 67699, 67847, 67924, 67964, 67
984, 67995, 68001, 68004, 68006, 68007, 68008]
[66844, 100551, 117547, 126045, 130368, 132568, 133688, 134258, 134543, 134691,
134768, 134808, 134828, 134839, 134845, 134848, 134850, 134851, 134852]
[132568, 199412, 233119, 250115, 258613, 262936, 265136, 266256, 266826, 267111,
 267259, 267336, 267376, 267396, 267407, 267413, 267416, 267418, 267419, 267420]

[262936, 395504, 462348, 496055, 513051, 521549, 525872, 528072, 529192, 529762,
 530047, 530195, 530272, 530312, 530332, 530343, 530349, 530352, 530354, 530355,
 530356]
[521549, 784485, 917053, 983897, 1017604, 1034600, 1043098, 1047421, 1049621, 10
50741, 1051311, 1051596, 1051744, 1051821, 1051861, 1051881, 1051892, 1051898, 1
051901, 1051903, 1051904, 1051905]
[1043098, 1564647, 1827583, 1960151, 2026995, 2060702, 2077698, 2086196, 2090519
, 2092719, 2093839, 2094409, 2094694, 2094842, 2094919, 2094959, 2094979, 209499
0, 2094996, 2094999, 2095001, 2095002, 2095003]
[2077698, 3120796, 3642345, 3905281, 4037849, 4104693, 4138400, 4155396, 4163894
, 4168217, 4170417, 4171537, 4172107, 4172392, 4172540, 4172617, 4172657, 417267
7, 4172688, 4172694, 4172697, 4172699, 4172700, 4172701]
[4138400, 6216098, 7259196, 7780745, 8043681, 8176249, 8243093, 8276800, 8293796
, 8302294, 8306617, 8308817, 8309937, 8310507, 8310792, 8310940, 8311017, 831105
7, 8311077, 8311088, 8311094, 8311097, 8311099, 8311100, 8311101]
[8243093, 12381493, 14459191, 15502289, 16023838, 16286774, 16419342, 16486186,
16519893, 16536889, 16545387, 16549710, 16551910, 16553030, 16553600, 16553885,
16554033, 16554110, 16554150, 16554170, 16554181, 16554187, 16554190, 16554192,
16554193, 16554194]
[16419342, 24662435, 28800835, 30878533, 31921631, 32443180, 32706116, 32838684,
 32905528, 32939235, 32956231, 32964729, 32969052, 32971252, 32972372, 32972942,
 32973227, 32973375, 32973452, 32973492, 32973512, 32973523, 32973529, 32973532,
 32973534, 32973535, 32973536]
[32706116, 49125458, 57368551, 61506951, 63584649, 64627747, 65149296, 65412232,
 65544800, 65611644, 65645351, 65662347, 65670845, 65675168, 65677368, 65678488,
 65679058, 65679343, 65679491, 65679568, 65679608, 65679628, 65679639, 65679645,
 65679648, 65679650, 65679651, 65679652]
[65149296, 97855412, 114274754, 122517847, 126656247, 128733945, 129777043, 1302
98592, 130561528, 130694096, 130760940, 130794647, 130811643, 130820141, 1308244
64, 130826664, 130827784, 130828354, 130828639, 130828787, 130828864, 130828904,
 130828924, 130828935, 130828941, 130828944, 130828946, 130828947, 130828948]
[130298592, 195447888, 228154004, 244573346, 252816439, 256954839, 259032537, 26
0075635, 260597184, 260860120, 260992688, 261059532, 261093239, 261110235, 26111
8733, 261123056, 261125256, 261126376, 261126946, 261127231, 261127379, 26112745
6, 261127496, 261127516, 261127527, 261127533, 261127536, 261127538, 261127539,
261127540]
[260075635, 390374227, 455523523, 488229639, 504648981, 512892074, 517030474, 51
9108172, 520151270, 520672819, 520935755, 521068323, 521135167, 521168874, 52118
5870, 521194368, 521198691, 521200891, 521202011, 521202581, 521202866, 52120301
4, 521203091, 521203131, 521203151, 521203162, 521203168, 521203171, 521203173,
521203174, 521203175]
[519108172, 779183807, 909482399, 974631695, 1007337811, 1023757153, 1032000246,
 1036138646, 1038216344, 1039259442, 1039780991, 1040043927, 1040176495, 1040243
339, 1040277046, 1040294042, 1040302540, 1040306863, 1040309063, 1040310183, 104
0310753, 1040311038, 1040311186, 1040311263, 1040311303, 1040311323, 1040311334,
 1040311340, 1040311343, 1040311345, 1040311346, 1040311347]
[1036138646, 1555246818, 1815322453, 1945621045, 2010770341, 2043476457, 2059895
799, 2068138892, 2072277292, 2074354990, 2075398088, 2075919637, 2076182573, 207
6315141, 2076381985, 2076415692, 2076432688, 2076441186, 2076445509, 2076447709,
 2076448829, 2076449399, 2076449684, 2076449832, 2076449909, 2076449949, 2076449
969, 2076449980, 2076449986, 2076449989, 2076449991, 2076449992, 2076449993]
true

b[1..-1]だけでなく、考えられる和も出力するには次のようにすればよい。

def set(a)
  n = a.size
  ary = []
  (1..n).each{|i|
    a.combination(i){|c| ary.push(c.inject(:+))}
  }
  ary.sort!
  [ary.size, ary]
end

N = 8
b = [0, 1]
ary = [0, 1]
p b[1..-1]
p set(b[1..-1])
i = 1
while i < N
  j = (Math.sqrt(i * 2) + 0.5).to_i
  k = ary[i] - ary[i - j]
  b = b.map{|l| l + k}.unshift(0)
  ary.push(b[-1])
  p b[1..-1]
  p set(b[1..-1])
  i += 1
end

出力結果
[1]
[1, [1]]
[1, 2]
[3, [1, 2, 3]]
[2, 3, 4]
[7, [2, 3, 4, 5, 6, 7, 9]]
[3, 5, 6, 7]
[15, [3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 21]]
[6, 9, 11, 12, 13]
[31, [6, 9, 11, 12, 13, 15, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
30, 31, 32, 33, 34, 36, 38, 39, 40, 42, 45, 51]]
[11, 17, 20, 22, 23, 24]
[63, [11, 17, 20, 22, 23, 24, 28, 31, 33, 34, 35, 37, 39, 40, 41, 42, 43, 44, 45
, 46, 47, 48, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66
, 67, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 80, 82, 83, 84, 86, 89, 93, 94, 95
, 97, 100, 106, 117]]
[20, 31, 37, 40, 42, 43, 44]
[127, [20, 31, 37, 40, 42, 43, 44, 51, 57, 60, 62, 63, 64, 68, 71, 73, 74, 75, 7
7, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 91, 93, 94, 95, 97, 99, 100, 101, 102
, 103, 104, 105, 106, 107, 108, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119
, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135
, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 149, 150, 151, 152
, 153, 154, 155, 156, 157, 158, 160, 162, 163, 164, 166, 169, 170, 171, 172, 173
, 174, 175, 176, 177, 178, 180, 182, 183, 184, 186, 189, 193, 194, 195, 197, 200
, 206, 213, 214, 215, 217, 220, 226, 237, 257]]
[40, 60, 71, 77, 80, 82, 83, 84]
[255, [40, 60, 71, 77, 80, 82, 83, 84, 100, 111, 117, 120, 122, 123, 124, 131, 1
37, 140, 142, 143, 144, 148, 151, 153, 154, 155, 157, 159, 160, 161, 162, 163, 1
64, 165, 166, 167, 171, 177, 180, 182, 183, 184, 188, 191, 193, 194, 195, 197, 1
99, 200, 201, 202, 203, 204, 205, 206, 207, 208, 211, 213, 214, 215, 217, 219, 2
20, 221, 222, 223, 224, 225, 226, 227, 228, 230, 231, 232, 233, 234, 235, 236, 2
37, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 251, 253, 254, 2
55, 257, 259, 260, 261, 262, 263, 264, 265, 266, 267, 268, 270, 271, 272, 273, 2
74, 275, 276, 277, 278, 279, 280, 281, 282, 283, 284, 285, 286, 287, 288, 289, 2
90, 291, 292, 293, 294, 295, 296, 297, 298, 299, 300, 301, 302, 303, 304, 305, 3
06, 307, 309, 310, 311, 312, 313, 314, 315, 316, 317, 318, 320, 322, 323, 324, 3
26, 328, 329, 330, 331, 332, 333, 334, 335, 336, 337, 338, 339, 340, 341, 342, 3
43, 344, 345, 346, 347, 349, 350, 351, 352, 353, 354, 355, 356, 357, 358, 360, 3
62, 363, 364, 366, 369, 370, 371, 372, 373, 374, 375, 376, 377, 378, 380, 382, 3
83, 384, 386, 389, 393, 394, 395, 397, 400, 406, 410, 411, 412, 413, 414, 415, 4
16, 417, 418, 420, 422, 423, 424, 426, 429, 433, 434, 435, 437, 440, 446, 453, 4
54, 455, 457, 460, 466, 477, 493, 494, 495, 497, 500, 506, 517, 537, 577]]

2015年5月24日日曜日

150524

Ruby


「普通の分数の足し算」と「日付の足し算」が一致する組合せ

3/3 + 7/2 = 9/2
62 + 183 = 245
の両方が成り立っている。
このような例を全部出力してみる。
(https://teratail.com/questions/10223)

require 'date'

md0 = Date.new(2013, 12, 31)
(1..365).to_a.repeated_combination(2){|i, j|
  x, y, z = md0 + i, md0 + j, md0 + i + j 
  z0 = Rational(x.mon,x.day) + Rational(y.mon, y.day)
  # Rational(x.mon,x.day) + Rational(y.mon, y.day) == Rational(z.mon, z.day)ではダメ
  if z.mon == z0.numerator && z.day == z0.denominator
    puts [x.strftime("%m/%d"), y.strftime("%m/%d")].join(",")
  end
}

出力結果
01/28,02/28
01/30,06/30
01/31,07/31
03/03,07/02
04/06,09/27
04/22,09/11
07/07,09/27
08/06,09/27
09/12,10/24
10/10,12/28
10/15,11/24
10/30,12/04
12/06,12/30

2015年5月23日土曜日

150523

Ruby


2〜Nまでをある規則にしたがって並びかえる

次のような2〜Nの小さい順の並びとあまり変わらない並びかえを
思いついた。

require 'prime'

N = 100
ary = []
h = {}
(2..N).each{|i|
  if i.prime?
    ary.push(h.values)
    p h # 検証用の出力なので省いても構わない
    h = {1 => [i]}
  else
    s = 0
    i.prime_division.map{|j| s += j[1]}
    h.key?(s) ? h[s] = h[s].push(i) : h[s] = [i] # sは1, 2, … とは限らない
  end
}
p ary.push(h.values).flatten

出力結果
{}
{1=>[2]}
{1=>[3], 2=>[4]}
{1=>[5], 2=>[6]}
{1=>[7], 3=>[8], 2=>[9, 10]}
{1=>[11], 3=>[12]}
{1=>[13], 2=>[14, 15], 4=>[16]}
{1=>[17], 3=>[18]}
{1=>[19], 3=>[20], 2=>[21, 22]}
{1=>[23], 4=>[24], 2=>[25, 26], 3=>[27, 28]}
{1=>[29], 3=>[30]}
{1=>[31], 5=>[32], 2=>[33, 34, 35], 4=>[36]}
{1=>[37], 2=>[38, 39], 4=>[40]}
{1=>[41], 3=>[42]}
{1=>[43], 3=>[44, 45], 2=>[46]}
{1=>[47], 5=>[48], 2=>[49, 51], 3=>[50, 52]}
{1=>[53], 4=>[54, 56], 2=>[55, 57, 58]}
{1=>[59], 4=>[60]}
{1=>[61], 2=>[62, 65], 3=>[63, 66], 6=>[64]}
{1=>[67], 3=>[68, 70], 2=>[69]}
{1=>[71], 5=>[72]}
{1=>[73], 2=>[74, 77], 3=>[75, 76, 78]}
{1=>[79], 5=>[80], 4=>[81], 2=>[82]}
{1=>[83], 4=>[84, 88], 2=>[85, 86, 87]}
{1=>[89], 4=>[90], 2=>[91, 93, 94, 95], 3=>[92], 6=>[96]}
[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23,
 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43,
 44, 45, 46, 47, 48, 49, 51, 50, 52, 53, 54, 56, 55, 57, 58, 59, 60, 61, 62, 65,
 63, 66, 64, 67, 68, 70, 69, 71, 72, 73, 74, 77, 75, 76, 78, 79, 80, 81, 82, 83,
 84, 88, 85, 86, 87, 89, 90, 91, 93, 94, 95, 92, 96, 97, 98, 99, 100]

2015年5月17日日曜日

150517

Ruby


n進グレイコード ↔ n進表記

n進グレイコード を作り、また元に戻すコード。
(http://ja.stackoverflow.com/questions/10263/%EF%BD%8E%E9%80%B2%E3%82%B0%E3%83%AC%E3%82%A4%E3%82%B3%E3%83%BC%E3%83%89%E3%81%8B%E3%82%89%EF%BD%8E%E9%80%B2%E8%A1%A8%E8%A8%98%E3%81%B8%E6%88%BB%E3%81%99%E3%81%AB%E3%81%AF)

# n進表記から n進グレイコードへ
def to_gray(n, k, str)
  str.rjust(k + 1, '0').split('').each_cons(2).map{|d|
    ((d[1].to_i(n) - d[0].to_i(n)) % n).to_s(n)
  }.join
end

# n進グレイコードから n進表記へ
def to_n_ary(n, k, str)
  a = 0
  str.rjust(k, '0').split('').map{|d| ((a += d.to_i(n)) % n).to_s(n)}.join
end

n, k = 11, 2

ary0 = []
(0..n ** k - 1).each{|i| ary0 << to_gray(n, k, i.to_s(n))}
p ary0

ary1 = []
(0..n ** k - 1).each{|i| ary1 << to_n_ary(n, k, to_gray(n, k, i.to_s(n)))}
p ary1 # n進表記に戻っているはず

出力結果
["00", "01", "02", "03", "04", "05", "06", "07", "08", "09", "0a", "1a", "10", "
11", "12", "13", "14", "15", "16", "17", "18", "19", "29", "2a", "20", "21", "22
", "23", "24", "25", "26", "27", "28", "38", "39", "3a", "30", "31", "32", "33",
 "34", "35", "36", "37", "47", "48", "49", "4a", "40", "41", "42", "43", "44", "
45", "46", "56", "57", "58", "59", "5a", "50", "51", "52", "53", "54", "55", "65
", "66", "67", "68", "69", "6a", "60", "61", "62", "63", "64", "74", "75", "76",
 "77", "78", "79", "7a", "70", "71", "72", "73", "83", "84", "85", "86", "87", "
88", "89", "8a", "80", "81", "82", "92", "93", "94", "95", "96", "97", "98", "99
", "9a", "90", "91", "a1", "a2", "a3", "a4", "a5", "a6", "a7", "a8", "a9", "aa",
 "a0"]
["00", "01", "02", "03", "04", "05", "06", "07", "08", "09", "0a", "10", "11", "
12", "13", "14", "15", "16", "17", "18", "19", "1a", "20", "21", "22", "23", "24
", "25", "26", "27", "28", "29", "2a", "30", "31", "32", "33", "34", "35", "36",
 "37", "38", "39", "3a", "40", "41", "42", "43", "44", "45", "46", "47", "48", "
49", "4a", "50", "51", "52", "53", "54", "55", "56", "57", "58", "59", "5a", "60
", "61", "62", "63", "64", "65", "66", "67", "68", "69", "6a", "70", "71", "72",
 "73", "74", "75", "76", "77", "78", "79", "7a", "80", "81", "82", "83", "84", "
85", "86", "87", "88", "89", "8a", "90", "91", "92", "93", "94", "95", "96", "97
", "98", "99", "9a", "a0", "a1", "a2", "a3", "a4", "a5", "a6", "a7", "a8", "a9",
 "aa"]

2015年5月3日日曜日

150503(3)

Ruby


| σ(i + 1) - σ(1) | ≠ 1 を満たすσの個数

σをSnの要素とし、
1 ≦ i ≦ n - 1 に対し、| σ(i + 1) - σ(1) | ≠ 1 を満たす
ものの個数を求めるコードを書いてみた。
(150503(2)のコードと比べ物にならないくらい速い。
 なお、c(-1, -1) = 1 としていますが、「コンピュータの数学」5.1
 に書いてあるように本来は n < 0 のとき、c(n, n) = 0 です。)
オンライン整数列大辞典の
A002464(http://oeis.org/A002464/list)
と比較し、答え合わせしてみる。

def c(m, n)
  return 1 if m == n
  return 0 if m < n
  return 0 if n < 0
  return 1 if n == 0
  n = m - n if n > m - n
  return (m - n + 1..m).inject(:*) / (1..n).inject(:*)
end

N = 23
ary = [1]
(1..N).each{|n|
  cnt1 = 0
  (0..n - 1).each{|r|
    cnt2 = 0
    (0..r).each{|c|
      cnt2 += 2 ** c * c(r - 1, c - 1) * c(n - r, c)
    }
    cnt1 += (-1) ** r * (1..n - r).inject(:*) * cnt2
  }
  ary << cnt1
}

# OEIS A002464のデータ
ary0 =
[1,1,0,0,2,14,90,646,5242,47622,479306,5296790,
 63779034,831283558,11661506218,175203184374,
 2806878055610,47767457130566,860568917787402,
 16362838542699862,327460573946510746,
 6880329406055690790,151436547414562736234,
 3484423186862152966838]
# 一致の確認
p ary == ary0

150503(2)

Ruby


3 6 9 2 5 8 1 4 7 (2)

1からNまでのN個の整数で、
 1)隣り合う2数の差はD以上、1個おいた数との差もD以上、… 、
   D - 2個おいた数との差もD以上 
という条件を満たす順列を考える。
D、Nが与えられたとき、条件を満たす順列の個数を求める。

N = 11
D1 = 4

def check1(d, a, i)
  return true if i == 0
  j = 1
  d_max = [i, d - 1].min
  while (a[i] - a[i - j]).abs >= d && j < d_max
    j += 1
  end
  (a[i] - a[i - j]).abs >= d
end

def solve1(d, len, a = [])
  b = []
  if a.size == len
    b << a
  else
    (1..len).each{|m|
      s = a.size
      if s == 0 || (s > 0 && !a.include?(m))
        if check1(d, a + [m], s)
          b += solve1(d, len, a + [m])
        end
      end
    }
  end
  b
end

(2..D1).each{|d1|
  (d1..N).each{|b|
    p [d1, b, solve1(d1, b).size]
  }
}

出力結果
[2, 2, 0]
[2, 3, 0]
[2, 4, 2]
[2, 5, 14]
[2, 6, 90]
[2, 7, 646]
[2, 8, 5242]
[2, 9, 47622]
[2, 10, 479306]
[2, 11, 5296790]
[3, 3, 0]
[3, 4, 0]
[3, 5, 0]
[3, 6, 0]
[3, 7, 0]
[3, 8, 0]
[3, 9, 2]
[3, 10, 40]
[3, 11, 792]
[4, 4, 0]
[4, 5, 0]
[4, 6, 0]
[4, 7, 0]
[4, 8, 0]
[4, 9, 0]
[4, 10, 0]
[4, 11, 0]

1からNまでのN個の整数で、
 2)D - 2個おいた数との差がD以外
という条件を満たす順列を考える。
D、Nが与えられたとき、条件を満たす順列の個数を求める。

N = 11
D2 = 3

def check2(d, a, i)
  return true if i < d
  !((a[i] - a[i - d]).abs == d)
end

def solve2(d, len, a = [])
  b = []
  if a.size == len
    b << a
  else
    (1..len).each{|m|
      s = a.size
      if s == 0 || (s > 0 && !a.include?(m))
        if check2(d, a + [m], s)
          b += solve2(d, len, a + [m])
        end
      end
    }
  end
  b
end

(1..D2).each{|d2|
  (1..N).each{|b|
    p [d2, b, solve2(d2, b).size]
  }
}

出力結果
[1, 1, 1]
[1, 2, 0]
[1, 3, 0]
[1, 4, 2]
[1, 5, 14]
[1, 6, 90]
[1, 7, 646]
[1, 8, 5242]
[1, 9, 47622]
[1, 10, 479306]
[1, 11, 5296790]
[2, 1, 1]
[2, 2, 2]
[2, 3, 4]
[2, 4, 16]
[2, 5, 44]
[2, 6, 200]
[2, 7, 1288]
[2, 8, 9512]
[2, 9, 78652]
[2, 10, 744360]
[2, 11, 7867148]
[3, 1, 1]
[3, 2, 2]
[3, 3, 6]
[3, 4, 20]
[3, 5, 80]
[3, 6, 384]
[3, 7, 2240]
[3, 8, 15424]
[3, 9, 123456]
[3, 10, 1110928]
[3, 11, 11287232]

赤の部分が一致するのは、明らかだろう。

また、
条件2)を満たす順列の個数は
1 ≦ i ≦ N - D に対し、| σ(i + D) - σ(D) | ≠ D を満たすσの個数 …①
と言い換えられる。
①についてシグマで表された式がある。
(http://www.kurims.kyoto-u.ac.jp/EMIS/journals/INTEGERS/papers/g11/g11.pdf)
よって、条件2)を満たす順列の個数についてシグマで表された式があると言える。

150503

Ruby


Ducci sequence

[1, 2, … , n]からスタートしたとき、周期の長さを
出力するコードを書いてみた。

def d(ary)
  d_ary = []
  ary1 = ary.clone
  (ary1 << ary[0]).each_cons(2){|a| d_ary << a.max - a.min}
  d_ary
end

(1..24).each{|n|
  ary = (1..n).to_a
  i = 0
  s_ary = [ary]
  d_ary = d(ary)
  i += 1
  while !s_ary.include?(d_ary)
    ary = d_ary
    s_ary << ary
    d_ary = d(ary)
    i += 1
  end
  ary = d_ary
  p [n, i - s_ary.index(ary)]
}

出力結果
[1, 1]
[2, 1]
[3, 3]
[4, 1]
[5, 15]
[6, 6]
[7, 7]
[8, 1]
[9, 63]
[10, 30]
[11, 341]
[12, 12]
[13, 819]
[14, 14]
[15, 15]
[16, 1]
[17, 255]
[18, 126]
[19, 9709]
[20, 60]
[21, 63]
[22, 682]
[23, 2047]
[24, 24]

2015年5月2日土曜日

150502

Ruby


3 6 9 2 5 8 1 4 7 (1)

1からNまでのN個の整数で、
 1)隣り合う2数の差はD以上、1個おいた数との差もD以上、… 、
   D - 2個おいた数との差もD以上 
という条件を満たす順列を考える。
Dを固定したとき、条件を満たす順列が存在するための最小のNはいくつだろうか?
また、このとき条件を満たす順列はどんなものだろうか?
(http://www004.upp.so-net.ne.jp/s_honma/mathbun/mathbun113.htm)

def check(d, a, i)
  return true if i == 0
  j = 1
  d_max = [i, d - 1].min
  while (a[i] - a[i - j]).abs >= d && j < d_max
    j += 1
  end
  (a[i] - a[i - j]).abs >= d
end

def solve(d, len, a = [])
  b = []
  if a.size == len
    b << a
  else
    (1..len).each{|m|
      s = a.size
      if s == 0 || (s > 0 && !a.include?(m))
        if check(d, a + [m], s)
          b += solve(d, len, a + [m])
        end
      end
    }
  end
  b
end

# Dを固定したとき、条件を満たす順列が存在するための最小のN
(2..5).each{|d|
  n = d
  while solve(d, n).size == 0
    n += 1
  end
  p n
  p solve(d, n)
}

出力結果
4
[[2, 4, 1, 3], [3, 1, 4, 2]]
9
[[3, 6, 9, 2, 5, 8, 1, 4, 7], [7, 4, 1, 8, 5, 2, 9, 6, 3]]
16
[[4, 8, 12, 16, 3, 7, 11, 15, 2, 6, 10, 14, 1, 5, 9, 13], [13, 9, 5, 1, 14, 10,
6, 2, 15, 11, 7, 3, 16, 12, 8, 4]]
25
[[5, 10, 15, 20, 25, 4, 9, 14, 19, 24, 3, 8, 13, 18, 23, 2, 7, 12, 17, 22, 1, 6,
 11, 16, 21], [21, 16, 11, 6, 1, 22, 17, 12, 7, 2, 23, 18, 13, 8, 3, 24, 19, 14,
 9, 4, 25, 20, 15, 10, 5]]