2018年12月24日月曜日

181224

Ruby


オイラー関数のベキ(4)

150927(2)分で
500次までに現れる0の個数を出力したが、
係数が0となる次数(<= 500)を出力してみた。

def s(n)
  s = 0
  (1..n).each{|i| s += i if n % i == 0}
  s
end

def A(m, n)
  ary = [1]
  a = [0] + (1..n).map{|i| s(i)}
  (1..n).each{|i| ary << (1..i).inject(0){|s, j| s - m * a[j] * ary[-j]} / i}
  ary
end

def B(k, n)
  a = A(k, n)
  (0..n).select{|i| a[i] == 0}
end

n = 500
[1, 2, 3, 4, 5, 6, 8, 10, 14, 15, 26].each{|i|
  j = B(i, n)
  p [i, j.size, j]
}

出力結果
[1, 464, [3, 4, 6, 8, 9, 10, 11, 13, 14, 16, 17, 18, 19, 20, 21, 23, 24, 25, 27, 28, 29, 30, 31, 32, 33, 34, 36, 37, 38, 39, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 52, 53, 54, 55, 56, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 71, 72, 73, 74, 75, 76, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 93, 94, 95, 96, 97, 98, 99, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 118, 119, 120, 121, 122, 123, 124, 125, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 146, 147, 148, 149, 150, 151, 152, 153, 154, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 248, 249, 250, 251, 252, 253, 254, 255, 256, 257, 258, 259, 261, 262, 263, 264, 265, 266, 267, 268, 269, 270, 271, 272, 273, 274, 275, 276, 277, 278, 279, 280, 281, 282, 283, 284, 285, 286, 288, 289, 290, 291, 292, 293, 294, 295, 296, 297, 298, 299, 300, 302, 303, 304, 305, 306, 307, 308, 309, 310, 311, 312, 313, 314, 315, 316, 317, 318, 319, 320, 321, 322, 323, 324, 325, 326, 327, 328, 329, 331, 332, 333, 334, 335, 336, 337, 338, 339, 340, 341, 342, 343, 344, 346, 347, 348, 349, 350, 351, 352, 353, 354, 355, 356, 357, 358, 359, 360, 361, 362, 363, 364, 365, 366, 367, 368, 369, 370, 371, 372, 373, 374, 375, 377, 378, 379, 380, 381, 382, 383, 384, 385, 386, 387, 388, 389, 390, 391, 393, 394, 395, 396, 397, 398, 399, 400, 401, 402, 403, 404, 405, 406, 407, 408, 409, 410, 411, 412, 413, 414, 415, 416, 417, 418, 419, 420, 421, 422, 423, 424, 426, 427, 428, 429, 430, 431, 432, 433, 434, 435, 436, 437, 438, 439, 440, 441, 443, 444, 445, 446, 447, 448, 449, 450, 451, 452, 453, 454, 455, 456, 457, 458, 459, 460, 461, 462, 463, 464, 465, 466, 467, 468, 469, 470, 471, 472, 473, 474, 475, 476, 478, 479, 480, 481, 482, 483, 484, 485, 486, 487, 488, 489, 490, 491, 492, 493, 494, 496, 497, 498, 499, 500]]
[2, 243, [7, 11, 12, 17, 18, 21, 22, 25, 32, 37, 39, 41, 42, 43, 46, 47, 49, 54, 57, 58, 60, 62, 65, 67, 68, 72, 74, 75, 76, 81, 82, 87, 88, 90, 92, 95, 97, 98, 99, 106, 107, 109, 111, 112, 113, 116, 117, 120, 122, 123, 125, 126, 128, 130, 132, 136, 137, 142, 143, 144, 147, 153, 157, 158, 159, 160, 162, 163, 164, 165, 167, 172, 173, 175, 177, 179, 181, 182, 186, 187, 192, 193, 194, 197, 201, 204, 205, 207, 208, 211, 212, 214, 215, 217, 219, 220, 221, 222, 228, 230, 231, 232, 235, 237, 239, 240, 241, 242, 244, 245, 247, 251, 256, 257, 258, 262, 263, 266, 267, 270, 272, 273, 274, 277, 278, 279, 282, 283, 284, 285, 287, 291, 292, 296, 297, 302, 304, 305, 307, 312, 315, 317, 318, 319, 320, 322, 325, 326, 328, 329, 330, 331, 332, 333, 334, 337, 340, 342, 343, 345, 347, 349, 351, 353, 354, 357, 359, 360, 361, 362, 364, 366, 367, 368, 369, 372, 375, 381, 382, 384, 386, 387, 389, 390, 392, 393, 395, 397, 398, 403, 406, 407, 408, 410, 412, 415, 417, 418, 419, 421, 422, 424, 427, 428, 429, 431, 432, 435, 437, 438, 439, 441, 442, 446, 447, 448, 449, 450, 452, 455, 457, 458, 459, 461, 462, 466, 467, 468, 472, 473, 476, 480, 481, 482, 483, 486, 487, 491, 492, 497, 498, 499, 500]]
[3, 469, [2, 4, 5, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 20, 22, 23, 24, 25, 26, 27, 29, 30, 31, 32, 33, 34, 35, 37, 38, 39, 40, 41, 42, 43, 44, 46, 47, 48, 49, 50, 51, 52, 53, 54, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 254, 255, 256, 257, 258, 259, 260, 261, 262, 263, 264, 265, 266, 267, 268, 269, 270, 271, 272, 273, 274, 275, 277, 278, 279, 280, 281, 282, 283, 284, 285, 286, 287, 288, 289, 290, 291, 292, 293, 294, 295, 296, 297, 298, 299, 301, 302, 303, 304, 305, 306, 307, 308, 309, 310, 311, 312, 313, 314, 315, 316, 317, 318, 319, 320, 321, 322, 323, 324, 326, 327, 328, 329, 330, 331, 332, 333, 334, 335, 336, 337, 338, 339, 340, 341, 342, 343, 344, 345, 346, 347, 348, 349, 350, 352, 353, 354, 355, 356, 357, 358, 359, 360, 361, 362, 363, 364, 365, 366, 367, 368, 369, 370, 371, 372, 373, 374, 375, 376, 377, 379, 380, 381, 382, 383, 384, 385, 386, 387, 388, 389, 390, 391, 392, 393, 394, 395, 396, 397, 398, 399, 400, 401, 402, 403, 404, 405, 407, 408, 409, 410, 411, 412, 413, 414, 415, 416, 417, 418, 419, 420, 421, 422, 423, 424, 425, 426, 427, 428, 429, 430, 431, 432, 433, 434, 436, 437, 438, 439, 440, 441, 442, 443, 444, 445, 446, 447, 448, 449, 450, 451, 452, 453, 454, 455, 456, 457, 458, 459, 460, 461, 462, 463, 464, 466, 467, 468, 469, 470, 471, 472, 473, 474, 475, 476, 477, 478, 479, 480, 481, 482, 483, 484, 485, 486, 487, 488, 489, 490, 491, 492, 493, 494, 495, 497, 498, 499, 500]]
[4, 158, [9, 14, 19, 24, 31, 34, 39, 42, 44, 49, 53, 59, 64, 65, 69, 74, 75, 82, 84, 86, 89, 94, 97, 99, 108, 109, 111, 114, 116, 119, 124, 130, 133, 134, 139, 144, 149, 150, 152, 157, 159, 163, 164, 167, 169, 174, 180, 184, 185, 189, 194, 196, 198, 199, 201, 203, 207, 209, 214, 218, 219, 224, 226, 227, 229, 234, 235, 239, 240, 244, 249, 251, 252, 256, 259, 264, 269, 272, 273, 274, 284, 285, 286, 289, 294, 295, 299, 303, 306, 309, 314, 317, 318, 319, 320, 321, 324, 328, 334, 339, 341, 343, 344, 349, 350, 354, 359, 361, 362, 364, 369, 371, 372, 374, 384, 387, 388, 389, 394, 399, 401, 403, 405, 409, 410, 414, 415, 416, 419, 422, 424, 427, 430, 433, 434, 438, 439, 444, 449, 456, 459, 460, 462, 464, 469, 471, 473, 474, 479, 482, 484, 485, 488, 489, 490, 493, 494, 499]]
[5, 0, []]
[6, 212, [5, 8, 14, 17, 19, 23, 26, 32, 33, 35, 40, 41, 44, 47, 50, 52, 53, 54, 59, 62, 63, 68, 71, 74, 75, 77, 80, 82, 85, 86, 89, 95, 96, 98, 103, 104, 107, 109, 113, 116, 117, 118, 122, 124, 125, 128, 129, 131, 134, 138, 140, 143, 145, 147, 149, 152, 155, 158, 161, 162, 166, 167, 170, 173, 176, 178, 179, 180, 184, 185, 187, 188, 194, 195, 197, 201, 203, 204, 206, 209, 212, 215, 217, 221, 222, 223, 224, 228, 229, 230, 233, 236, 239, 242, 243, 247, 248, 250, 251, 257, 260, 261, 264, 266, 269, 270, 271, 275, 278, 280, 283, 284, 285, 287, 290, 292, 293, 294, 296, 299, 302, 305, 311, 313, 314, 316, 317, 318, 320, 323, 327, 329, 332, 333, 334, 337, 338, 339, 341, 347, 348, 349, 350, 356, 359, 360, 362, 364, 365, 368, 369, 371, 374, 375, 376, 377, 382, 383, 385, 386, 390, 392, 394, 395, 397, 398, 401, 404, 408, 410, 411, 413, 415, 418, 419, 422, 425, 426, 428, 431, 432, 437, 439, 440, 446, 448, 449, 452, 454, 455, 457, 458, 459, 460, 464, 467, 470, 473, 474, 476, 477, 479, 481, 482, 485, 488, 489, 491, 492, 494, 495, 500]]
[8, 250, [3, 7, 11, 13, 15, 18, 19, 23, 27, 28, 29, 31, 35, 38, 39, 43, 45, 47, 48, 51, 53, 55, 59, 61, 62, 63, 67, 68, 71, 73, 75, 77, 78, 79, 83, 84, 87, 88, 91, 93, 95, 98, 99, 103, 106, 107, 109, 111, 113, 115, 117, 118, 119, 123, 125, 127, 128, 130, 131, 135, 138, 139, 141, 143, 147, 148, 150, 151, 153, 155, 157, 159, 163, 164, 167, 168, 171, 172, 173, 175, 178, 179, 181, 183, 187, 188, 189, 191, 193, 194, 195, 198, 199, 203, 205, 207, 211, 213, 215, 216, 218, 219, 221, 222, 223, 227, 228, 231, 232, 235, 237, 238, 239, 243, 245, 247, 248, 249, 251, 253, 255, 259, 260, 263, 266, 267, 268, 269, 271, 273, 275, 278, 279, 283, 285, 287, 288, 291, 293, 295, 298, 299, 300, 301, 303, 304, 307, 309, 311, 313, 314, 315, 317, 318, 319, 323, 326, 327, 328, 331, 333, 334, 335, 337, 338, 339, 343, 347, 348, 349, 351, 353, 355, 359, 360, 363, 365, 367, 368, 370, 371, 373, 375, 378, 379, 381, 383, 387, 388, 391, 392, 393, 395, 396, 397, 398, 399, 402, 403, 406, 407, 411, 413, 414, 415, 418, 419, 423, 425, 427, 428, 429, 431, 435, 436, 437, 438, 439, 443, 445, 447, 448, 451, 452, 453, 454, 455, 458, 459, 461, 463, 467, 468, 469, 470, 471, 473, 475, 477, 478, 479, 480, 483, 487, 488, 491, 493, 495, 498, 499]]
[10, 151, [6, 13, 17, 27, 28, 34, 36, 39, 41, 48, 55, 59, 61, 62, 72, 74, 76, 82, 83, 90, 93, 94, 97, 104, 105, 111, 112, 116, 121, 125, 127, 128, 131, 132, 138, 139, 146, 149, 151, 152, 153, 160, 168, 169, 174, 181, 182, 183, 188, 193, 195, 197, 202, 204, 207, 209, 211, 214, 215, 223, 226, 230, 237, 243, 244, 245, 248, 251, 254, 258, 259, 262, 264, 266, 270, 272, 276, 279, 281, 283, 286, 289, 293, 297, 300, 302, 303, 307, 309, 312, 314, 321, 325, 328, 329, 335, 336, 338, 340, 342, 347, 349, 356, 358, 359, 369, 370, 377, 378, 380, 381, 383, 384, 388, 391, 396, 397, 398, 402, 403, 404, 405, 416, 419, 424, 426, 427, 431, 433, 435, 440, 446, 447, 450, 454, 457, 462, 463, 467, 468, 469, 473, 475, 479, 482, 489, 490, 492, 493, 496, 497]]
[14, 172, [4, 9, 15, 19, 24, 26, 29, 32, 34, 37, 44, 48, 49, 54, 55, 59, 66, 69, 74, 78, 79, 81, 83, 84, 92, 94, 99, 100, 101, 103, 104, 109, 113, 114, 117, 119, 124, 125, 129, 134, 136, 142, 144, 147, 149, 151, 154, 158, 159, 160, 169, 170, 171, 174, 179, 180, 184, 185, 193, 194, 199, 200, 201, 202, 204, 207, 209, 213, 216, 219, 224, 229, 234, 235, 236, 239, 242, 244, 246, 249, 253, 254, 257, 258, 259, 260, 262, 268, 269, 270, 274, 279, 283, 284, 285, 287, 290, 294, 299, 301, 304, 309, 313, 316, 319, 321, 323, 324, 329, 331, 334, 338, 344, 345, 348, 349, 354, 355, 356, 359, 365, 366, 367, 369, 372, 374, 377, 378, 379, 384, 389, 394, 395, 399, 400, 403, 404, 406, 409, 411, 419, 422, 423, 424, 429, 432, 434, 437, 440, 442, 444, 446, 447, 449, 454, 455, 459, 461, 466, 469, 472, 474, 477, 479, 484, 488, 489, 491, 492, 494, 496, 499]]
[15, 2, [53, 482]]
[26, 80, [9, 20, 31, 42, 43, 53, 64, 66, 75, 86, 89, 97, 108, 112, 119, 135, 136, 141, 152, 158, 163, 171, 174, 181, 183, 185, 196, 204, 206, 207, 218, 227, 229, 230, 240, 241, 250, 262, 273, 277, 284, 289, 295, 296, 306, 311, 317, 319, 324, 328, 339, 342, 348, 350, 361, 365, 371, 381, 383, 388, 394, 405, 407, 411, 416, 418, 419, 427, 434, 438, 449, 457, 460, 465, 466, 471, 480, 482, 486, 490]]

2018年12月12日水曜日

181212

Ruby


1212

この記事は
日曜数学 Advent Calendar 2018 (https://adventar.org/calendars/3009)
の12/12 分として書いております。
前回はだまさんの初等的解法の存在する角度の問題でした。

「1が2個, 2が2個」を一列に並べるとき、
同じ数字が並ばない並べ方は何通りあるでしょう。
解:1212、2121の2通り。

「1が9個, 2が9個, ... , 9が9個」を一列に並べるとき、
同じ数字が並ばない並べ方は何通りあるでしょう。
また、
「1がn個, 2がn個, ... , nがn個」を一列に並べるとき、
同じ数字が並ばない並べ方の個数を高速に求めるには
どうすればよいでしょうか?

数学の知識と初歩的なプログラミングの知識が必要になります。

①数学の知識
パスカルの三角形とは次のようなものです。
1,
1, 1,
1, 2, 1,
1, 3, 3, 1,
1, 4, 6, 4, 1,
...
さて次のように細工します。
 1/1,
-1/1,  1/2,
 1/1, -2/2,  1/6,
-1/1,  3/2, -3/6,  1/24,
 1/1, -4/2,  6/6, -4/24, 1/120,
...
これらを係数にもつ多項式q_i(x) を作ります。
q_1(x) =  x,
q_2(x) = -x + 1/2 * x^2,
q_3(x) =  x - 2/2 * x^2 + 1/6 * x^3,
q_4(x) = -x + 3/2 * x^2 - 3/6 * x^3 + 1/24 * x^4,
q_5(x) =  x - 4/2 * x^2 + 6/6 * x^3 - 4/24 * x^4 + 1/120 * x^5,
...
さて、q_i(x) は次のような驚くべき性質を持っています。

「1がm_1個, 2がm_2個, ... , kがm_k個」を一列に並べるとき、同じ数字が並ばない並べ方は
Integral_{0..infinity} Product_{i=1..k} q_{m_i}(x) * exp(-x) dx.

ちなみに、Integral_{0..infinity} x^m * exp(-x) dx = m! ですので、
多項式の掛け算をして、係数を求めることが重要であることがわかります。

今回の場合に当てはめると
Integral_{0..infinity} (q_n(x))^n * exp(-x) dx
となります。

②プログラミングの知識
 (q_n(x))^n の計算はバイナリ法を用いると計算回数が少なくてすみます。

これらをもとに実装すると次のようになり、
n = 9 のときは、
11655577382287102750765311537460065620507094071664576111302628243840
通りと求まります。

def mul(f_ary, b_ary)
  s1, s2 = f_ary.size, b_ary.size
  ary = Array.new(s1 + s2 - 1, 0)
  (0..s1 - 1).each{|i|
    (0..s2 - 1).each{|j|
      ary[i + j] += f_ary[i] * b_ary[j]
    }
  }
  ary
end

def power(ary, n)
  return [1] if n == 0
  k = power(ary, n >> 1)
  k = mul(k, k)
  return k if n & 1 == 0
  return mul(k, ary)
end

def ncr(n, r)
  return 1 if r == 0
  (n - r + 1..n).inject(:*) / (1..r).inject(:*)
end

def f(n)
  return 1 if n < 2
  (1..n).inject(:*)
end

def A(n)
  ary = power([0] + (1..n).map{|i| (-1) ** (n - i) * ncr(n - 1, n - i) / f(i).to_r}, n)
  (0..ary.size - 1).inject(0){|s, i| s + f(i) * ary[i]}.to_i
end

n = 20
(0..n).each{|i| p [i, A(i)]}

出力結果
[0, 1]
[1, 1]
[2, 2]
[3, 174]
[4, 2265024]
[5, 7946203275000]
[6, 12229789732207993835280]
[7, 12202002913678756821228939869239920]
[8, 10937192762438008527903830198163831816546577931520]
[9, 11655577382287102750765311537460065620507094071664576111302628243840]
[10, 18877545858631350177544126730326118579042534510881427013497201905522243828084277155584000]
[11, 57814365142525615345822290635367980031764472894406481579410336826627768364093502411683595510203294058889662636800]
[12, 407658789636795392873224914660821849906640854496041813132347715886561006703544292229875155619913436614371595102735557393480894068396031590400]
[13, 7916240618568924952784422376897285074349407297177155333772267175236361650837449810625502710956077916339020347009688544252921894901829502808023567304468717311128650695552000]
[14, 498961977012237615935915814835809945218689415847045000987626530145354117671508674820161361629165453542631518534948206591419638038499418413317775100822845509486513888639232738104669714232846642736185909196800]
[15, 118813418570954352257626152461870566748175083811925094869482044671635443619567119146472438369570944844793864117533983401043281073111768900013398219072288449242647438928900346234820007048719066622523886248828693230918893944171625097165388804864000]
[16, 123074415490344199979921662196075276052024358457569576638878274700296813263968616812171263108052043597819537373317572776761453007104704321107605953901687032805754242905638392434082191822082575494722399225216595810131347324670136983012576738242197768842539749995881462695930820212498432000]
[17, 632673322223167150563381180449202895810656486275138980768979126849568078803929001026198717240246438492208986017127366607503113807961453674908153743390688559089518342608243133491125088605989422356306262511591012413333743083156845181593352662535492648478551130685710723664924508871843351853059474256064874854425780258865548135985152000]
[18, 18262485268060395471719629462211789200248188118212907564935177446312080481434798754251346826458783843905735671916454235952642336679346522571446273991105431911451246995478453093531740103567375709740164836196952627498127365568349243885731021363958900889615826228391994012608680368231380597695100532416438065107000126490501124888837506361583551279679270162874801672720230508095201280000]
[19, 3325346401901827184405264043746239777213987165498607952527099919169429535191502889521807119252816036721707694000409416885917354468125596599265774644403590455801186699549289399295618384982739223055026353093870119637734650695671402196886800379294232694826306609192327108837847109423774316242807710788886545902961566935329488725575424433775416001359407137834222431223588069183910836336963435557633128490071733441789088652042060740714496000]
[20, 4263374507224750254652747946709751036907009890731720806160330060792101908200442231854976249703550510732440932255817411768387265800055035356279767743465046586935783799213627064605070089606422958689740675558147647400901384320375900390925397265681026115099056542471222575925955266135626206309095922246090256122147265738804913109253904934843458466990632702917971742764047620310632779114398031596958284411852848038321222991793804098769489620905040225884507551867559309764993380559572463906816000000]

2018年12月2日日曜日

181202

Ruby


A060963 とA322178

出力してみた。

def search(a, num, d, k, n)
  if num == 0
    @cnt += 1
  else
    (2 * n - 1).times{|i|
      if a[i] == 0
        (i + d + 1..2 * n - 1).each{|j|
          if a[j] == 0
            a[i], a[j] = num, num
            search(a, num - 1, j - i - k, k, n)
            a[i], a[j] = 0, 0
          end
        }
      end
    }
  end
end

def A(k, n)
  a = [0] * 2 * n
  @cnt = 0
  search(a, n, 0, k, n)
  @cnt
end

puts "A060963"
p (0..9).map{|i| A(0, i)}
puts "A322178"
p (0..7).map{|i| A(1, i)}

出力結果
A060963
[1, 1, 1, 5, 29, 145, 957, 8397, 85169, 944221]
A322178
[1, 1, 5, 33, 329, 3825, 57293, 977581]