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
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]]
0 件のコメント:
コメントを投稿
注: コメントを投稿できるのは、このブログのメンバーだけです。