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]]