#! /usr/bin/env python3 # def web_matrix_test ( ): #*****************************************************************************80 # ## web_matrix_test() tests web_matrix(). # # Licensing: # # This code is distributed under the MIT license. # # Modified: # # 27 September 2022 # # Author: # # John Burkardt # from scipy.sparse import coo_matrix import numpy as np import platform print ( '' ) print ( 'web_matrix_test():' ) print ( ' Python version: ' + platform.python_version ( ) ) print ( ' Test web_matrix()' ) print ( '' ) print ( ' Process the "tiny" web matrix' ) i, j, v = tiny_st ( ) m = np.max ( i ) + 1 n = np.max ( j ) + 1 A_coo = coo_matrix ( ( v, ( i, j ) ), shape = ( m, n ), dtype = np.int ) A = A_coo.toarray ( ) power_rank ( A ) print ( '' ) print ( ' Process the "moler" web matrix' ) i, j, v = moler_st ( ) m = np.max ( i ) + 1 n = np.max ( j ) + 1 A_coo = coo_matrix ( ( v, ( i, j ) ), shape = ( m, n ), dtype = np.int ) A = A_coo.toarray ( ) power_rank ( A ) print ( '' ) print ( ' Process the "sauer" web matrix' ) i, j, v = sauer_st ( ) m = np.max ( i ) + 1 n = np.max ( j ) + 1 A_coo = coo_matrix ( ( v, ( i, j ) ), shape = ( m, n ), dtype = np.int ) A = A_coo.toarray ( ) power_rank ( A ) # # Terminate. # print ( '' ) print ( 'web_matrix_test():' ) print ( ' Normal end of execution.' ) return def harvard_st ( ): #*****************************************************************************80 # ## harvard_st() returns the Harvard web matrix in sparse triplet form. # # Discussion: # # 500 nodes, 2636 links. # # Licensing: # # This code is distributed under the MIT license. # # Modified: # # 27 September 2022 # # Author: # # John Burkardt # # Reference: # # Cleve Moler, # Experiments with Matlab, # Chapter 7: Google PageRank, # https://www.mathworks.com/moler/exm/chapters/pagerank.pdf # # Output: # # integer i(2636), j(2636), v(2636): the sparse triplet information. # import numpy as np i = np.array ( [ \ 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, 1, 28, 29, 30, \ 1, 31, 32, 33, 34, 35, 36, 37, 38, 39, \ 40, 41, 1, 22, 42, 43, 44, 45, 46, 1, \ 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, \ 57, 58, 59, 1, 12, 23, 60, 61, 62, 63, \ 64, 65, 66, 1, 67, 68, 69, 70, 71, 72, \ 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, \ 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, \ 1, 93, 94, 95, 96, 97, 98, 99, 100, 101, \ 102, 103, 104, 105, 106, 107, 108, 109, 1, 110, \ 111, 112, 113, 114, 1, 115, 116, 117, 118, 119, \ 120, 121, 1, 122, 1, 52, 85, 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, 148, 149, 150, 151, 152, 153, 154, 155, \ 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, \ 166, 167, 168, 1, 169, 170, 171, 172, 173, 174, \ 175, 176, 177, 178, 179, 180, 1, 85, 181, 182, \ 183, 184, 1, 42, 185, 186, 187, 188, 189, 190, \ 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, \ 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, \ 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, \ 221, 222, 223, 224, 225, 226, 227, 228, 1, 229, \ 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, \ 240, 241, 242, 243, 244, 245, 246, 247, 248, 1, \ 26, 27, 42, 249, 250, 251, 252, 253, 254, 255, \ 256, 257, 258, 259, 1, 26, 27, 249, 258, 259, \ 260, 1, 26, 27, 42, 249, 250, 251, 252, 253, \ 254, 255, 256, 258, 259, 1, 26, 27, 249, 258, \ 259, 260, 261, 262, 263, 264, 265, 266, 267, 268, \ 269, 270, 271, 272, 273, 274, 275, 276, 277, 278, \ 279, 280, 281, 1, 26, 27, 249, 258, 259, 260, \ 1, 249, 260, 42, 282, 44, 283, 1, 42, 43, \ 44, 1, 284, 285, 286, 287, 288, 289, 290, 291, \ 292, 293, 294, 295, 296, 297, 298, 299, 106, 300, \ 301, 302, 303, 304, 305, 306, 307, 303, 304, 307, \ 308, 1, 31, 32, 33, 34, 35, 36, 37, 38, \ 39, 40, 309, 1, 4, 260, 310, 311, 312, 313, \ 314, 1, 26, 27, 249, 258, 259, 260, 315, 316, \ 317, 318, 319, 320, 321, 322, 323, 324, 325, 326, \ 327, 328, 329, 330, 331, 332, 333, 334, 335, 1, \ 1, 260, 336, 337, 338, 339, 340, 341, 342, 343, \ 130, 344, 2, 3, 4, 5, 6, 7, 8, 62, \ 77, 170, 173, 177, 191, 210, 288, 289, 292, 312, \ 345, 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, 376, 377, 378, 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, 406, 407, 408, 409, 410, 411, 412, 413, 414, \ 415, 416, 417, 418, 419, 2, 3, 4, 5, 6, \ 7, 12, 63, 141, 144, 146, 147, 187, 354, 358, \ 371, 376, 386, 389, 397, 408, 413, 420, 421, 422, \ 423, 424, 425, 426, 427, 428, 429, 430, 431, 432, \ 433, 434, 435, 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, 465, 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, 496, 497, 498, 499, 500, 2, 3, \ 4, 5, 6, 7, 19, 44, 138, 175, 201, 312, \ 314, 353, 373, 374, 387, 388, 401, 414, 419, 423, \ 429, 466, 491, 2, 3, 4, 5, 6, 7, 40, \ 44, 401, 1, 3, 5, 8, 42, 61, 407, 1, \ 1, 1, 12, 45, 61, 62, 63, 317, 1, 26, \ 27, 249, 258, 259, 260, 1, 26, 27, 249, 258, \ 259, 260, 1, 9, 1, 9, 1, 9, 1, 9, \ 1, 9, 1, 9, 87, 1, 9, 87, 1, 9, \ 1, 3, 75, 77, 78, 79, 80, 82, 83, 84, \ 86, 87, 88, 89, 91, 383, 388, 424, 1, 9, \ 88, 1, 9, 1, 9, 1, 84, 85, 1, 9, \ 9, 383, 1, 9, 76, 85, 1, 9, 76, 85, \ 2, 3, 4, 5, 6, 7, 1, 9, 73, 1, \ 9, 76, 85, 1, 9, 1, 84, 1, 9, 10, \ 96, 101, 102, 107, 10, 1, 10, 101, 102, 106, \ 107, 106, 107, 10, 95, 10, 101, 102, 7, 10, \ 101, 102, 10, 95, 96, 101, 102, 103, 104, 105, \ 106, 108, 300, 379, 1, 10, 85, 101, 102, 104, \ 107, 300, 379, 1, 10, 101, 102, 300, 10, 101, \ 102, 3, 10, 96, 97, 101, 102, 106, 285, 300, \ 10, 10, 2, 3, 4, 5, 6, 7, 11, 1, \ 12, 42, 120, 1, 47, 120, 1, 120, 1, 12, \ 1, 12, 42, 1, 12, 42, 15, 52, 126, 130, \ 380, 382, 15, 130, 131, 13, 15, 123, 130, 1, \ 3, 13, 17, 130, 13, 15, 17, 52, 85, 123, \ 126, 129, 133, 138, 150, 358, 15, 126, 127, 131, \ 132, 132, 130, 148, 130, 133, 138, 150, 363, 130, \ 133, 138, 150, 435, 1, 15, 62, 130, 52, 123, \ 130, 139, 140, 141, 142, 143, 144, 145, 146, 148, \ 15, 42, 52, 444, 1, 130, 52, 130, 136, 160, \ 456, 385, 15, 15, 130, 133, 138, 144, 150, 385, \ 15, 138, 150, 353, 373, 52, 130, 148, 153, 130, \ 52, 130, 130, 261, 281, 161, 298, 15, 15, 164, \ 1, 16, 42, 169, 170, 171, 172, 173, 174, 176, \ 177, 178, 179, 16, 42, 169, 170, 171, 172, 173, \ 174, 176, 177, 178, 179, 16, 42, 169, 170, 171, \ 172, 173, 174, 176, 177, 178, 179, 16, 42, 169, \ 170, 171, 172, 173, 174, 176, 177, 178, 179, 16, \ 194, 16, 42, 169, 170, 171, 172, 173, 174, 176, \ 177, 178, 179, 16, 260, 16, 42, 169, 170, 171, \ 172, 173, 174, 176, 177, 178, 179, 16, 42, 169, \ 170, 171, 172, 173, 174, 176, 177, 178, 179, 16, \ 42, 169, 170, 171, 172, 173, 174, 176, 177, 178, \ 179, 6, 16, 42, 169, 170, 171, 172, 173, 174, \ 176, 177, 178, 179, 16, 42, 169, 170, 171, 172, \ 173, 174, 176, 177, 178, 179, 17, 92, 17, 1, \ 18, 187, 192, 214, 222, 223, 361, 1, 18, 187, \ 214, 222, 223, 228, 361, 1, 18, 185, 186, 189, \ 190, 214, 222, 223, 483, 492, 18, 1, 18, 190, \ 200, 214, 222, 223, 1, 18, 214, 222, 223, 1, \ 18, 222, 223, 1, 202, 228, 1, 1, 18, 222, \ 223, 1, 18, 190, 222, 223, 1, 18, 42, 214, \ 222, 223, 1, 18, 187, 190, 191, 200, 202, 206, \ 208, 214, 222, 223, 226, 344, 477, 1, 18, 187, \ 190, 191, 200, 202, 206, 208, 214, 222, 223, 226, \ 344, 477, 1, 18, 191, 214, 222, 223, 1, 18, \ 214, 222, 223, 226, 314, 366, 487, 1, 18, 42, \ 214, 222, 223, 1, 18, 189, 190, 192, 200, 208, \ 214, 222, 223, 344, 1, 18, 222, 223, 18, 42, \ 200, 201, 214, 1, 18, 214, 222, 223, 225, 226, \ 227, 1, 18, 222, 223, 1, 18, 191, 200, 214, \ 222, 223, 1, 18, 207, 208, 214, 222, 223, 1, \ 18, 210, 211, 212, 214, 222, 223, 1, 18, 210, \ 211, 212, 214, 222, 223, 1, 3, 18, 192, 194, \ 207, 210, 211, 212, 214, 222, 223, 1, 18, 214, \ 222, 223, 18, 42, 200, 201, 214, 18, 200, 201, \ 214, 1, 26, 27, 42, 249, 250, 251, 252, 253, \ 254, 255, 256, 258, 259, 1, 18, 200, 208, 214, \ 222, 223, 1, 18, 191, 202, 208, 210, 214, 222, \ 223, 361, 1, 3, 18, 187, 189, 190, 191, 195, \ 196, 197, 198, 200, 201, 202, 203, 204, 206, 207, \ 208, 210, 211, 212, 213, 214, 219, 220, 222, 223, \ 225, 344, 354, 361, 483, 492, 498, 1, 7, 18, \ 42, 200, 208, 214, 221, 222, 223, 344, 1, 18, \ 214, 222, 223, 226, 18, 185, 225, 1, 18, 222, \ 223, 18, 210, 1, 18, 187, 192, 214, 222, 223, \ 361, 1, 19, 229, 230, 231, 232, 233, 234, 235, \ 236, 237, 238, 239, 240, 241, 1, 19, 229, 230, \ 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, \ 241, 1, 19, 229, 230, 231, 232, 233, 234, 235, \ 236, 237, 238, 239, 240, 241, 1, 19, 229, 230, \ 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, \ 241, 1, 19, 229, 230, 231, 232, 233, 234, 235, \ 236, 237, 238, 239, 240, 241, 1, 19, 229, 230, \ 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, \ 1, 19, 42, 229, 230, 231, 232, 233, 234, 235, \ 236, 237, 238, 239, 240, 241, 1, 19, 229, 230, \ 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, \ 241, 1, 19, 229, 230, 231, 232, 233, 234, 235, \ 236, 237, 238, 239, 240, 241, 1, 19, 229, 230, \ 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, \ 241, 1, 19, 229, 231, 232, 234, 236, 237, 238, \ 239, 240, 241, 242, 1, 19, 229, 230, 231, 232, \ 233, 234, 235, 236, 237, 238, 239, 240, 241, 1, \ 19, 229, 230, 231, 232, 233, 234, 235, 236, 237, \ 238, 239, 240, 241, 19, 284, 1, 19, 229, 230, \ 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, \ 241, 1, 19, 229, 230, 231, 232, 233, 234, 235, \ 236, 237, 238, 239, 240, 241, 1, 19, 229, 230, \ 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, \ 241, 19, 1, 19, 229, 230, 231, 232, 233, 234, \ 235, 236, 237, 238, 239, 240, 241, 1, 19, 229, \ 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, \ 240, 241, 1, 26, 27, 249, 258, 259, 260, 1, \ 26, 27, 249, 258, 259, 260, 1, 26, 27, 249, \ 258, 259, 260, 1, 26, 27, 249, 258, 259, 260, \ 1, 26, 27, 249, 258, 259, 260, 1, 26, 27, \ 249, 258, 259, 260, 1, 26, 27, 249, 258, 259, \ 260, 1, 42, 43, 44, 1, 1, 130, 261, 281, \ 261, 262, 263, 264, 266, 267, 274, 275, 276, 277, \ 278, 279, 280, 281, 261, 262, 263, 264, 265, 266, \ 267, 268, 269, 270, 271, 272, 273, 274, 275, 276, \ 277, 278, 279, 280, 281, 261, 262, 263, 264, 265, \ 266, 267, 268, 269, 270, 271, 272, 273, 274, 275, \ 276, 277, 278, 279, 280, 281, 261, 262, 263, 264, \ 266, 267, 274, 275, 276, 277, 278, 279, 280, 281, \ 261, 262, 263, 264, 266, 267, 274, 275, 276, 277, \ 278, 279, 280, 281, 261, 262, 263, 264, 265, 266, \ 267, 268, 269, 270, 271, 272, 273, 274, 275, 276, \ 277, 278, 279, 280, 281, 261, 262, 263, 264, 265, \ 266, 267, 268, 269, 270, 271, 272, 273, 274, 275, \ 276, 277, 278, 279, 280, 281, 261, 262, 263, 264, \ 265, 266, 267, 268, 269, 270, 271, 272, 273, 274, \ 275, 276, 277, 278, 279, 280, 281, 261, 262, 263, \ 264, 265, 266, 267, 268, 269, 270, 271, 272, 273, \ 274, 275, 276, 277, 278, 279, 280, 281, 261, 262, \ 263, 264, 265, 266, 267, 268, 269, 270, 271, 272, \ 273, 274, 275, 276, 277, 278, 279, 280, 281, 261, \ 262, 263, 264, 265, 266, 267, 268, 269, 270, 271, \ 272, 273, 274, 275, 276, 277, 278, 279, 280, 281, \ 261, 262, 263, 264, 266, 267, 274, 275, 276, 277, \ 278, 279, 280, 281, 261, 262, 263, 264, 266, 267, \ 274, 275, 276, 277, 278, 279, 280, 281, 261, 262, \ 263, 264, 266, 267, 274, 275, 276, 277, 278, 279, \ 280, 281, 164, 261, 262, 263, 264, 266, 267, 274, \ 275, 276, 277, 278, 279, 280, 281, 261, 262, 263, \ 264, 266, 267, 274, 275, 276, 277, 278, 279, 280, \ 281, 261, 262, 263, 264, 266, 267, 274, 275, 276, \ 277, 278, 279, 280, 281, 261, 262, 263, 264, 266, \ 267, 274, 275, 276, 277, 278, 279, 280, 281, 262, \ 1, 28, 29, 30, 1, 19, 229, 231, 232, 234, \ 236, 237, 238, 239, 240, 241, 242, 11, 1, 3, \ 32, 194, 1, 293, 1, 1, 3, 194, 312, 458, \ 3, 14, 42, 1, 106, 107, 39, 40, 1, 3, \ 288, 1, 3, 1, 44, 1, 44, 1, 329, 46, \ 315, 316, 317, 318, 319, 320, 321, 322, 323, 324, \ 325, 326, 327, 328, 329, 330, 331, 335, 315, 316, \ 317, 318, 319, 320, 321, 322, 323, 324, 325, 326, \ 327, 328, 329, 330, 331, 332, 333, 334, 335, 46, \ 315, 316, 317, 318, 319, 320, 321, 322, 323, 324, \ 325, 326, 327, 328, 329, 330, 331, 335, 46, 315, \ 316, 317, 318, 319, 320, 321, 322, 323, 324, 325, \ 326, 327, 328, 329, 330, 331, 335, 46, 315, 316, \ 317, 318, 319, 320, 321, 322, 323, 324, 325, 326, \ 327, 328, 329, 330, 331, 335, 46, 315, 316, 317, \ 318, 319, 320, 321, 322, 323, 324, 325, 326, 327, \ 328, 329, 330, 331, 335, 46, 315, 316, 317, 318, \ 319, 320, 321, 322, 323, 324, 325, 326, 327, 328, \ 329, 330, 331, 335, 46, 315, 316, 317, 318, 319, \ 320, 321, 322, 323, 324, 325, 326, 327, 328, 329, \ 330, 331, 335, 46, 315, 316, 317, 318, 319, 320, \ 321, 322, 323, 324, 325, 326, 327, 328, 329, 330, \ 331, 335, 46, 315, 316, 317, 318, 319, 320, 321, \ 322, 323, 324, 325, 326, 327, 328, 329, 330, 331, \ 335, 46, 317, 318, 319, 320, 321, 322, 324, 325, \ 326, 327, 328, 329, 330, 331, 417, 46, 315, 316, \ 317, 318, 319, 320, 321, 322, 323, 324, 325, 326, \ 327, 328, 329, 330, 331, 335, 46, 315, 316, 317, \ 318, 319, 320, 321, 322, 323, 324, 325, 326, 327, \ 328, 329, 330, 331, 335, 46, 315, 316, 317, 318, \ 319, 320, 321, 322, 323, 324, 325, 326, 327, 328, \ 329, 330, 331, 335, 46, 335, 46, 315, 316, 317, \ 318, 319, 320, 321, 322, 323, 324, 325, 326, 327, \ 328, 329, 330, 331, 335, 46, 315, 316, 317, 318, \ 319, 320, 321, 322, 323, 324, 325, 326, 327, 328, \ 329, 330, 331, 335, 1, 260, 336, 337, 1, 260, \ 336, 337, 260, 336, 337, 2, 3, 4, 5, 6, \ 7, 153, 202, 311, 341, 345, 260, 336, 337, 1, \ 8, 1, 1, 10, 101, 102, 421, 1, 8, 1, \ 18, 185, 190, 222, 223, 463, 500, 42, 1, 62, \ 1, 18, 187, 192, 214, 222, 223, 361, 1, 13, \ 15, 17, 130, 155, 159, 161, 163, 164, 42, 1, \ 260, 1, 6, 42, 10, 101, 102, 13, 358, 6, \ 7, 13, 15, 130, 1, 9, 6, 62, 260, 260, \ 391, 11, 394, 52, 130, 1, 62, 42, 42, 3, \ 1, 8, 61, 18, 185, 225, 312, 85, 1, 1, \ 3, 31, 414, 46, 1, 1, 12, 61, 62, 63, \ 317, 389, 397, 429, 446, 452, 460, 486, 10, 101, \ 102, 348, 379, 441, 465, 478, 484, 42, 77, 1, \ 130, 133, 138, 139, 141, 143, 144, 146, 147, 150, \ 444, 182, 183, 374, 42, 1, 1, 42, 15, 1, \ 1, 130, 136, 139, 140, 143, 160, 456, 17, 10, \ 101, 102, 421, 17, 42, 52, 444, 1, 1, 1, \ 1, 1, 1, 1, 1, 8, 260, 1, 365, 458, \ 1, 42, 460, 1, 1, 13, 358, 1, 10, 101, \ 102, 1, 42, 17, 1, 1, 42, 1, 17, 1, \ 1, 1, 18, 222, 223, 10, 101, 102, 421, 1, \ 1, 1, 18, 10, 101, 102, 1, 17, 1, 17, \ 1, 1, 18, 222, 223, 361, 1, 360, 260, 1, \ 18, 222, 223, 17, 13, 358 ] ) j = np.array ( [ \ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, \ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, \ 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, \ 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, \ 3, 3, 4, 4, 4, 4, 4, 4, 5, 7, \ 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, \ 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, \ 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, \ 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, \ 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, \ 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, \ 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, \ 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, \ 12, 13, 14, 14, 15, 15, 15, 15, 15, 15, \ 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, \ 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, \ 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, \ 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, \ 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, \ 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, \ 17, 17, 18, 18, 18, 18, 18, 18, 18, 18, \ 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, \ 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, \ 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, \ 18, 18, 18, 18, 18, 18, 18, 18, 19, 19, \ 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, \ 19, 19, 19, 19, 19, 19, 19, 19, 19, 20, \ 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, \ 20, 20, 20, 20, 21, 21, 21, 21, 21, 21, \ 21, 22, 22, 22, 22, 22, 22, 22, 22, 22, \ 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, \ 23, 23, 24, 24, 24, 24, 24, 24, 24, 24, \ 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, \ 24, 24, 24, 25, 25, 25, 25, 25, 25, 25, \ 26, 26, 26, 27, 27, 28, 28, 29, 29, 29, \ 29, 30, 32, 32, 32, 32, 32, 32, 32, 32, \ 32, 33, 33, 34, 34, 34, 35, 35, 36, 36, \ 36, 37, 39, 39, 39, 39, 39, 40, 40, 40, \ 40, 41, 41, 41, 41, 41, 41, 41, 41, 41, \ 41, 41, 41, 44, 44, 44, 44, 44, 44, 44, \ 44, 45, 45, 45, 45, 45, 45, 45, 46, 46, \ 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, \ 46, 46, 46, 46, 46, 46, 46, 46, 46, 47, \ 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, \ 52, 52, 53, 53, 53, 53, 53, 53, 53, 53, \ 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, \ 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, \ 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, \ 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, \ 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, \ 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, \ 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, \ 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, \ 53, 53, 53, 53, 53, 54, 54, 54, 54, 54, \ 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, \ 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, \ 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, \ 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, \ 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, \ 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, \ 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, \ 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, \ 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, \ 54, 54, 54, 54, 54, 54, 54, 54, 55, 55, \ 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, \ 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, \ 55, 55, 55, 56, 56, 56, 56, 56, 56, 56, \ 56, 56, 61, 61, 61, 61, 61, 61, 61, 62, \ 63, 64, 64, 64, 64, 64, 64, 64, 65, 65, \ 65, 65, 65, 65, 65, 66, 66, 66, 66, 66, \ 66, 66, 67, 67, 68, 68, 69, 69, 70, 70, \ 71, 71, 72, 72, 72, 73, 73, 74, 75, 75, \ 76, 76, 76, 76, 76, 76, 76, 76, 76, 76, \ 76, 76, 76, 76, 76, 76, 76, 76, 77, 77, \ 77, 78, 78, 79, 79, 80, 80, 80, 81, 81, \ 82, 82, 83, 83, 83, 83, 84, 84, 84, 84, \ 85, 85, 85, 85, 85, 85, 87, 87, 87, 88, \ 88, 88, 88, 89, 89, 90, 90, 91, 91, 93, \ 93, 93, 93, 93, 95, 96, 96, 96, 96, 96, \ 96, 97, 97, 98, 98, 99, 99, 99, 101, 101, \ 101, 101, 102, 102, 102, 102, 102, 102, 102, 102, \ 102, 102, 102, 102, 103, 103, 103, 103, 103, 103, \ 103, 103, 103, 104, 104, 104, 104, 104, 105, 105, \ 105, 106, 106, 106, 106, 106, 106, 106, 106, 106, \ 107, 108, 109, 109, 109, 109, 109, 109, 111, 115, \ 115, 115, 115, 116, 116, 116, 117, 117, 118, 118, \ 119, 119, 119, 120, 120, 120, 121, 121, 121, 123, \ 124, 124, 125, 125, 125, 126, 126, 126, 128, 129, \ 129, 129, 129, 129, 130, 130, 130, 130, 130, 130, \ 130, 130, 130, 130, 130, 130, 131, 131, 131, 131, \ 131, 132, 133, 133, 134, 134, 134, 134, 134, 135, \ 135, 135, 135, 135, 136, 136, 136, 137, 138, 138, \ 138, 138, 138, 138, 138, 138, 138, 138, 138, 138, \ 139, 140, 140, 140, 141, 141, 144, 144, 144, 144, \ 144, 145, 146, 148, 148, 148, 148, 148, 148, 148, \ 149, 149, 149, 149, 149, 150, 150, 150, 150, 152, \ 153, 155, 160, 160, 160, 161, 162, 164, 165, 165, \ 168, 169, 169, 169, 169, 169, 169, 169, 169, 169, \ 169, 169, 169, 170, 170, 170, 170, 170, 170, 170, \ 170, 170, 170, 170, 170, 171, 171, 171, 171, 171, \ 171, 171, 171, 171, 171, 171, 171, 172, 172, 172, \ 172, 172, 172, 172, 172, 172, 172, 172, 172, 173, \ 173, 174, 174, 174, 174, 174, 174, 174, 174, 174, \ 174, 174, 174, 175, 175, 176, 176, 176, 176, 176, \ 176, 176, 176, 176, 176, 176, 176, 177, 177, 177, \ 177, 177, 177, 177, 177, 177, 177, 177, 177, 178, \ 178, 178, 178, 178, 178, 178, 178, 178, 178, 178, \ 178, 179, 179, 179, 179, 179, 179, 179, 179, 179, \ 179, 179, 179, 179, 180, 180, 180, 180, 180, 180, \ 180, 180, 180, 180, 180, 180, 182, 182, 183, 185, \ 185, 185, 185, 185, 185, 185, 185, 186, 186, 186, \ 186, 186, 186, 186, 186, 187, 187, 187, 187, 187, \ 187, 187, 187, 187, 187, 187, 188, 189, 189, 189, \ 189, 189, 189, 189, 190, 190, 190, 190, 190, 191, \ 191, 191, 191, 192, 192, 192, 193, 195, 195, 195, \ 195, 196, 196, 196, 196, 196, 197, 197, 197, 197, \ 197, 197, 198, 198, 198, 198, 198, 198, 198, 198, \ 198, 198, 198, 198, 198, 198, 198, 199, 199, 199, \ 199, 199, 199, 199, 199, 199, 199, 199, 199, 199, \ 199, 199, 200, 200, 200, 200, 200, 200, 201, 201, \ 201, 201, 201, 201, 201, 201, 201, 202, 202, 202, \ 202, 202, 202, 203, 203, 203, 203, 203, 203, 203, \ 203, 203, 203, 203, 204, 204, 204, 204, 205, 205, \ 205, 205, 205, 206, 206, 206, 206, 206, 206, 206, \ 206, 207, 207, 207, 207, 208, 208, 208, 208, 208, \ 208, 208, 209, 209, 209, 209, 209, 209, 209, 210, \ 210, 210, 210, 210, 210, 210, 210, 211, 211, 211, \ 211, 211, 211, 211, 211, 212, 212, 212, 212, 212, \ 212, 212, 212, 212, 212, 212, 212, 213, 213, 213, \ 213, 213, 214, 214, 214, 214, 214, 215, 215, 215, \ 215, 218, 218, 218, 218, 218, 218, 218, 218, 218, \ 218, 218, 218, 218, 218, 219, 219, 219, 219, 219, \ 219, 219, 220, 220, 220, 220, 220, 220, 220, 220, \ 220, 220, 222, 222, 222, 222, 222, 222, 222, 222, \ 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, \ 222, 222, 222, 222, 222, 222, 222, 222, 222, 222, \ 222, 222, 222, 222, 222, 222, 222, 223, 223, 223, \ 223, 223, 223, 223, 223, 223, 223, 223, 224, 224, \ 224, 224, 224, 224, 225, 225, 225, 226, 226, 226, \ 226, 227, 227, 228, 228, 228, 228, 228, 228, 228, \ 228, 229, 229, 229, 229, 229, 229, 229, 229, 229, \ 229, 229, 229, 229, 229, 229, 230, 230, 230, 230, \ 230, 230, 230, 230, 230, 230, 230, 230, 230, 230, \ 230, 231, 231, 231, 231, 231, 231, 231, 231, 231, \ 231, 231, 231, 231, 231, 231, 232, 232, 232, 232, \ 232, 232, 232, 232, 232, 232, 232, 232, 232, 232, \ 232, 233, 233, 233, 233, 233, 233, 233, 233, 233, \ 233, 233, 233, 233, 233, 233, 234, 234, 234, 234, \ 234, 234, 234, 234, 234, 234, 234, 234, 234, 234, \ 235, 235, 235, 235, 235, 235, 235, 235, 235, 235, \ 235, 235, 235, 235, 235, 235, 236, 236, 236, 236, \ 236, 236, 236, 236, 236, 236, 236, 236, 236, 236, \ 236, 237, 237, 237, 237, 237, 237, 237, 237, 237, \ 237, 237, 237, 237, 237, 237, 238, 238, 238, 238, \ 238, 238, 238, 238, 238, 238, 238, 238, 238, 238, \ 238, 239, 239, 239, 239, 239, 239, 239, 239, 239, \ 239, 239, 239, 239, 240, 240, 240, 240, 240, 240, \ 240, 240, 240, 240, 240, 240, 240, 240, 240, 241, \ 241, 241, 241, 241, 241, 241, 241, 241, 241, 241, \ 241, 241, 241, 241, 242, 242, 243, 243, 243, 243, \ 243, 243, 243, 243, 243, 243, 243, 243, 243, 243, \ 243, 244, 244, 244, 244, 244, 244, 244, 244, 244, \ 244, 244, 244, 244, 244, 244, 245, 245, 245, 245, \ 245, 245, 245, 245, 245, 245, 245, 245, 245, 245, \ 245, 246, 247, 247, 247, 247, 247, 247, 247, 247, \ 247, 247, 247, 247, 247, 247, 247, 248, 248, 248, \ 248, 248, 248, 248, 248, 248, 248, 248, 248, 248, \ 248, 248, 250, 250, 250, 250, 250, 250, 250, 251, \ 251, 251, 251, 251, 251, 251, 252, 252, 252, 252, \ 252, 252, 252, 253, 253, 253, 253, 253, 253, 253, \ 254, 254, 254, 254, 254, 254, 254, 255, 255, 255, \ 255, 255, 255, 255, 256, 256, 256, 256, 256, 256, \ 256, 257, 257, 257, 257, 258, 260, 262, 262, 262, \ 263, 263, 263, 263, 263, 263, 263, 263, 263, 263, \ 263, 263, 263, 263, 264, 264, 264, 264, 264, 264, \ 264, 264, 264, 264, 264, 264, 264, 264, 264, 264, \ 264, 264, 264, 264, 264, 265, 265, 265, 265, 265, \ 265, 265, 265, 265, 265, 265, 265, 265, 265, 265, \ 265, 265, 265, 265, 265, 265, 266, 266, 266, 266, \ 266, 266, 266, 266, 266, 266, 266, 266, 266, 266, \ 267, 267, 267, 267, 267, 267, 267, 267, 267, 267, \ 267, 267, 267, 267, 268, 268, 268, 268, 268, 268, \ 268, 268, 268, 268, 268, 268, 268, 268, 268, 268, \ 268, 268, 268, 268, 268, 269, 269, 269, 269, 269, \ 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, \ 269, 269, 269, 269, 269, 269, 270, 270, 270, 270, \ 270, 270, 270, 270, 270, 270, 270, 270, 270, 270, \ 270, 270, 270, 270, 270, 270, 270, 271, 271, 271, \ 271, 271, 271, 271, 271, 271, 271, 271, 271, 271, \ 271, 271, 271, 271, 271, 271, 271, 271, 272, 272, \ 272, 272, 272, 272, 272, 272, 272, 272, 272, 272, \ 272, 272, 272, 272, 272, 272, 272, 272, 272, 273, \ 273, 273, 273, 273, 273, 273, 273, 273, 273, 273, \ 273, 273, 273, 273, 273, 273, 273, 273, 273, 273, \ 274, 274, 274, 274, 274, 274, 274, 274, 274, 274, \ 274, 274, 274, 274, 275, 275, 275, 275, 275, 275, \ 275, 275, 275, 275, 275, 275, 275, 275, 276, 276, \ 276, 276, 276, 276, 276, 276, 276, 276, 276, 276, \ 276, 276, 277, 277, 277, 277, 277, 277, 277, 277, \ 277, 277, 277, 277, 277, 277, 277, 278, 278, 278, \ 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, \ 278, 279, 279, 279, 279, 279, 279, 279, 279, 279, \ 279, 279, 279, 279, 279, 280, 280, 280, 280, 280, \ 280, 280, 280, 280, 280, 280, 280, 280, 280, 281, \ 283, 283, 283, 283, 284, 284, 284, 284, 284, 284, \ 284, 284, 284, 284, 284, 284, 284, 286, 287, 287, \ 287, 287, 288, 288, 289, 290, 290, 290, 290, 290, \ 291, 291, 291, 292, 300, 300, 303, 303, 304, 304, \ 304, 305, 305, 311, 311, 313, 313, 314, 315, 316, \ 316, 316, 316, 316, 316, 316, 316, 316, 316, 316, \ 316, 316, 316, 316, 316, 316, 316, 316, 317, 317, \ 317, 317, 317, 317, 317, 317, 317, 317, 317, 317, \ 317, 317, 317, 317, 317, 317, 317, 317, 317, 318, \ 318, 318, 318, 318, 318, 318, 318, 318, 318, 318, \ 318, 318, 318, 318, 318, 318, 318, 318, 319, 319, \ 319, 319, 319, 319, 319, 319, 319, 319, 319, 319, \ 319, 319, 319, 319, 319, 319, 319, 320, 320, 320, \ 320, 320, 320, 320, 320, 320, 320, 320, 320, 320, \ 320, 320, 320, 320, 320, 320, 321, 321, 321, 321, \ 321, 321, 321, 321, 321, 321, 321, 321, 321, 321, \ 321, 321, 321, 321, 321, 322, 322, 322, 322, 322, \ 322, 322, 322, 322, 322, 322, 322, 322, 322, 322, \ 322, 322, 322, 322, 323, 323, 323, 323, 323, 323, \ 323, 323, 323, 323, 323, 323, 323, 323, 323, 323, \ 323, 323, 323, 324, 324, 324, 324, 324, 324, 324, \ 324, 324, 324, 324, 324, 324, 324, 324, 324, 324, \ 324, 324, 325, 325, 325, 325, 325, 325, 325, 325, \ 325, 325, 325, 325, 325, 325, 325, 325, 325, 325, \ 325, 326, 326, 326, 326, 326, 326, 326, 326, 326, \ 326, 326, 326, 326, 326, 326, 326, 327, 327, 327, \ 327, 327, 327, 327, 327, 327, 327, 327, 327, 327, \ 327, 327, 327, 327, 327, 327, 328, 328, 328, 328, \ 328, 328, 328, 328, 328, 328, 328, 328, 328, 328, \ 328, 328, 328, 328, 328, 329, 329, 329, 329, 329, \ 329, 329, 329, 329, 329, 329, 329, 329, 329, 329, \ 329, 329, 329, 329, 330, 331, 332, 332, 332, 332, \ 332, 332, 332, 332, 332, 332, 332, 332, 332, 332, \ 332, 332, 332, 332, 332, 333, 333, 333, 333, 333, \ 333, 333, 333, 333, 333, 333, 333, 333, 333, 333, \ 333, 333, 333, 333, 336, 336, 336, 336, 339, 339, \ 339, 339, 341, 341, 341, 342, 342, 342, 342, 342, \ 342, 342, 342, 342, 342, 342, 343, 343, 343, 344, \ 344, 345, 346, 348, 348, 348, 348, 352, 352, 354, \ 354, 354, 354, 354, 354, 358, 358, 359, 360, 360, \ 361, 361, 361, 361, 361, 361, 361, 361, 362, 363, \ 363, 363, 363, 363, 363, 363, 363, 363, 367, 371, \ 371, 377, 378, 378, 379, 379, 379, 380, 380, 381, \ 382, 382, 382, 382, 383, 383, 384, 386, 389, 391, \ 391, 392, 393, 395, 395, 398, 398, 402, 403, 404, \ 407, 407, 407, 408, 408, 408, 409, 410, 411, 414, \ 415, 415, 415, 417, 419, 420, 420, 420, 420, 420, \ 420, 420, 420, 420, 420, 420, 420, 420, 421, 421, \ 421, 421, 421, 421, 421, 421, 421, 422, 424, 425, \ 426, 426, 426, 426, 426, 426, 426, 426, 426, 426, \ 426, 427, 427, 427, 428, 430, 431, 432, 434, 437, \ 438, 438, 438, 438, 438, 438, 438, 438, 439, 441, \ 441, 441, 441, 443, 444, 444, 444, 446, 448, 450, \ 451, 453, 454, 455, 457, 457, 457, 459, 459, 459, \ 460, 460, 460, 461, 462, 463, 463, 464, 465, 465, \ 465, 466, 466, 467, 468, 469, 469, 470, 471, 475, \ 476, 477, 477, 477, 477, 478, 478, 478, 478, 479, \ 482, 483, 483, 484, 484, 484, 486, 488, 489, 490, \ 491, 492, 492, 492, 492, 492, 495, 496, 497, 498, \ 498, 498, 498, 499, 500, 500 ] ) v = np.ones ( 2636 ) # # Shift from one-based to zero-based indexing. # i = i - 1 j = j - 1 return i, j, v def incidence_to_transition ( A ): #*****************************************************************************80 # ## incidence_to_transition() converts an incidence matrix to a transition matrix. # # Licensing: # # This code is distributed under the MIT license. # # Modified: # # 07 August 2022 # # Author: # # John Burkardt # # Input: # # integer A(N,N), the incidence matrix. # # Output: # # real T(N,N): the transition matrix. # import numpy as np n = A.shape[0] # # Get the row sums. # s = np.sum ( A, axis = 1 ) # # Normalize each row so it sums to 1. # T = np.zeros ( [ n, n ] ) for i in range ( 0, n ): if ( s[i] != 0.0 ): T[i,:] = A[i,:] / s[i] else: T[i,i] = 1.0 # # Transpose the matrix. # T = np.transpose ( T ) return T def large_st ( ): #*****************************************************************************80 # ## large_st() returns the large web matrix in sparse triplet form. # # Discussion: # # 1458 nodes, 3546 links. # # Licensing: # # This code is distributed under the MIT license. # # Modified: # # 27 September 2022 # # Author: # # John Burkardt # # Output: # # integer i(3546), j(3546), v(3546): the sparse triplet information. # import numpy as np i = np.array ( [ \ 104, 553, 460, 12, 27, 34, 38, 42, 48, 68, \ 126, 131, 218, 294, 311, 326, 338, 391, 395, 457, \ 509, 521, 527, 532, 545, 549, 558, 592, 610, 617, \ 637, 687, 695, 708, 547, 643, 64, 110, 148, 645, \ 701, 237, 204, 391, 402, 417, 270, 286, 539, 315, \ 431, 7, 56, 59, 63, 224, 252, 329, 353, 361, \ 419, 425, 476, 530, 578, 685, 244, 164, 67, 127, \ 388, 622, 75, 602, 104, 179, 207, 226, 284, 363, \ 701, 48, 49, 55, 196, 210, 219, 315, 389, 431, \ 494, 512, 542, 143, 144, 202, 286, 395, 422, 489, \ 499, 600, 31, 43, 47, 92, 112, 113, 121, 141, \ 145, 152, 169, 176, 194, 233, 248, 255, 300, 325, \ 351, 371, 390, 397, 402, 408, 423, 439, 493, 528, \ 534, 551, 572, 578, 614, 624, 625, 630, 670, 681, \ 687, 649, 328, 78, 516, 539, 562, 597, 666, 672, \ 412, 457, 695, 323, 221, 250, 332, 345, 358, 379, \ 509, 689, 614, 71, 592, 609, 6, 19, 52, 53, \ 64, 82, 119, 134, 148, 188, 211, 216, 246, 258, \ 274, 276, 330, 340, 341, 342, 347, 382, 385, 391, \ 405, 426, 444, 468, 475, 484, 584, 647, 648, 671, \ 703, 351, 670, 457, 108, 386, 94, 124, 242, 416, \ 621, 29, 64, 65, 82, 87, 134, 246, 385, 447, \ 456, 475, 645, 188, 211, 341, 19, 50, 130, 173, \ 190, 280, 296, 299, 471, 482, 554, 588, 25, 210, \ 219, 378, 542, 546, 659, 106, 441, 661, 62, 643, \ 678, 699, 705, 58, 265, 13, 40, 70, 184, 252, \ 279, 334, 361, 470, 632, 6, 14, 37, 52, 82, \ 87, 110, 134, 181, 244, 246, 385, 405, 447, 456, \ 461, 475, 618, 647, 648, 701, 703, 421, 600, 699, \ 16, 388, 441, 538, 122, 157, 161, 513, 40, 138, \ 170, 287, 290, 334, 467, 476, 414, 594, 608, 615, \ 102, 616, 20, 90, 140, 267, 278, 511, 598, 652, \ 668, 269, 464, 688, 700, 703, 89, 153, 62, 459, \ 383, 459, 83, 375, 450, 611, 418, 54, 89, 97, \ 116, 117, 147, 160, 164, 182, 225, 266, 269, 271, \ 272, 278, 292, 299, 370, 375, 376, 385, 413, 448, \ 481, 511, 523, 525, 577, 598, 606, 611, 669, 673, \ 113, 411, 442, 183, 339, 100, 201, 239, 189, 465, \ 335, 95, 333, 538, 434, 707, 1, 284, 487, 642, \ 582, 57, 6, 64, 105, 149, 307, 468, 565, 582, \ 653, 681, 101, 203, 235, 414, 432, 462, 463, 608, \ 707, 709, 28, 47, 245, 270, 371, 402, 439, 670, \ 43, 92, 91, 182, 208, 271, 299, 485, 523, 525, \ 598, 606, 660, 673, 299, 448, 570, 196, 386, 145, \ 164, 84, 326, 462, 563, 676, 704, 382, 16, 185, \ 240, 409, 656, 187, 207, 554, 4, 48, 172, 250, \ 332, 345, 395, 534, 610, 695, 253, 316, 546, 426, \ 461, 647, 137, 241, 136, 186, 291, 387, 435, 290, \ 187, 350, 369, 492, 438, 9, 132, 155, 182, 243, \ 285, 26, 115, 489, 18, 121, 260, 658, 79, 278, \ 450, 570, 611, 682, 6, 53, 188, 347, 241, 352, \ 683, 644, 674, 230, 485, 142, 188, 281, 320, 435, \ 453, 484, 584, 601, 648, 60, 412, 427, 431, 511, \ 547, 647, 208, 502, 387, 581, 123, 495, 537, 645, \ 646, 227, 185, 268, 311, 319, 348, 409, 434, 483, \ 515, 537, 633, 691, 50, 280, 303, 368, 421, 490, \ 680, 146, 40, 70, 290, 334, 362, 228, 247, 309, \ 131, 345, 395, 604, 695, 166, 200, 227, 349, 469, \ 680, 194, 251, 321, 396, 517, 690, 380, 686, 87, \ 613, 686, 40, 63, 287, 293, 297, 353, 467, 561, \ 667, 244, 618, 118, 468, 498, 506, 562, 579, 582, \ 601, 139, 98, 536, 54, 283, 296, 471, 492, 588, \ 643, 699, 690, 198, 342, 120, 386, 22, 34, 45, \ 46, 119, 121, 135, 156, 178, 195, 214, 289, 322, \ 342, 349, 356, 386, 390, 392, 400, 420, 432, 445, \ 501, 513, 514, 524, 527, 532, 534, 545, 548, 584, \ 586, 592, 617, 623, 648, 651, 666, 672, 681, 686, \ 145, 185, 472, 604, 609, 173, 554, 660, 71, 388, \ 678, 422, 459, 477, 579, 635, 200, 208, 237, 271, \ 502, 116, 142, 160, 206, 237, 243, 502, 55, 120, \ 196, 219, 273, 310, 378, 381, 512, 541, 542, 546, \ 624, 697, 53, 364, 491, 573, 631, 22, 135, 169, \ 180, 289, 520, 552, 553, 574, 535, 562, 702, 25, \ 55, 133, 275, 343, 493, 542, 552, 697, 35, 39, \ 162, 312, 384, 387, 576, 581, 689, 12, 13, 56, \ 59, 109, 184, 252, 279, 290, 303, 319, 329, 334, \ 361, 362, 390, 453, 530, 632, 661, 663, 685, 85, \ 266, 403, 166, 559, 638, 154, 234, 504, 514, 660, \ 489, 657, 95, 100, 192, 306, 446, 454, 521, 634, \ 680, 16, 127, 129, 201, 202, 409, 462, 656, 29, \ 136, 149, 352, 490, 565, 380, 9, 624, 276, 340, \ 484, 146, 171, 580, 66, 199, 300, 304, 423, 436, \ 586, 604, 625, 646, 3, 460, 42, 221, 332, 379, \ 509, 689, 174, 529, 690, 13, 224, 254, 425, 578, \ 685, 132, 565, 419, 467, 310, 329, 404, 472, 480, \ 551, 701, 444, 433, 497, 566, 693, 97, 225, 272, \ 278, 282, 531, 536, 374, 480, 86, 510, 11, 203, \ 265, 575, 91, 182, 200, 206, 502, 523, 660, 120, \ 624, 697, 490, 393, 422, 678, 79, 83, 90, 97, \ 140, 147, 168, 223, 266, 282, 418, 437, 450, 531, \ 611, 652, 668, 682, 170, 287, 317, 482, 590, 105, \ 435, 683, 41, 223, 668, 674, 24, 272, 373, 11, \ 529, 22, 23, 180, 214, 322, 552, 553, 574, 138, \ 264, 352, 642, 302, 571, 577, 365, 708, 54, 190, \ 283, 471, 588, 401, 437, 451, 325, 406, 547, 404, \ 117, 292, 370, 473, 503, 518, 571, 673, 369, 675, \ 705, 231, 247, 316, 504, 528, 201, 417, 105, 356, \ 255, 488, 601, 434, 393, 260, 680, 115, 133, 231, \ 455, 139, 195, 420, 445, 640, 651, 427, 601, 396, \ 690, 2, 23, 52, 180, 214, 289, 307, 330, 444, \ 520, 553, 233, 248, 344, 436, 500, 514, 560, 460, \ 564, 628, 255, 322, 396, 587, 8, 42, 221, 250, \ 379, 509, 689, 32, 100, 620, 649, 70, 109, 170, \ 566, 102, 358, 549, 412, 53, 188, 336, 340, 461, \ 706, 46, 195, 198, 328, 347, 400, 417, 651, 706, \ 128, 441, 31, 145, 233, 256, 263, 305, 324, 436, \ 452, 556, 560, 602, 629, 646, 172, 459, 148, 167, \ 258, 327, 367, 426, 483, 505, 515, 580, 618, 631, \ 691, 173, 28, 47, 304, 371, 561, 603, 360, 482, \ 307, 359, 358, 415, 138, 170, 314, 334, 425, 476, \ 24, 274, 303, 328, 401, 424, 491, 62, 580, 451, \ 544, 705, 30, 207, 292, 302, 376, 413, 577, 605, \ 669, 673, 28, 112, 175, 231, 247, 351, 402, 439, \ 504, 24, 285, 469, 267, 370, 673, 301, 506, 242, \ 114, 286, 358, 408, 449, 494, 506, 541, 466, 19, \ 280, 398, 647, 12, 49, 108, 120, 176, 196, 273, \ 310, 320, 326, 532, 555, 60, 162, 191, 197, 643, \ 67, 365, 357, 459, 66, 394, 397, 10, 597, 27, \ 277, 313, 446, 516, 655, 676, 602, 26, 131, 144, \ 172, 363, 472, 600, 636, 578, 533, 29, 41, 52, \ 78, 105, 110, 124, 139, 141, 168, 181, 187, 195, \ 198, 258, 261, 307, 320, 342, 349, 352, 356, 373, \ 411, 421, 445, 488, 490, 519, 552, 582, 601, 613, \ 640, 651, 653, 681, 298, 675, 10, 14, 23, 52, \ 87, 189, 211, 246, 261, 276, 330, 385, 442, 444, \ 453, 484, 550, 587, 612, 703, 270, 309, 575, 650, \ 11, 521, 472, 339, 72, 101, 111, 176, 212, 432, \ 543, 608, 615, 676, 709, 14, 51, 165, 169, 423, \ 500, 514, 522, 560, 574, 613, 617, 645, 90, 318, \ 65, 600, 540, 389, 104, 364, 407, 479, 533, 642, \ 650, 677, 362, 431, 606, 403, 451, 478, 544, 675, \ 108, 217, 16, 67, 75, 129, 256, 263, 301, 308, \ 377, 441, 497, 519, 556, 557, 629, 630, 693, 102, \ 281, 31, 129, 169, 199, 240, 248, 324, 344, 656, \ 701, 85, 298, 403, 428, 478, 495, 544, 123, 140, \ 557, 359, 573, 261, 318, 400, 651, 192, 239, 277, \ 306, 393, 454, 589, 634, 30, 117, 130, 473, 503, \ 525, 570, 616, 157, 381, 541, 568, 89, 298, 428, \ 20, 75, 305, 324, 344, 394, 556, 602, 625, 629, \ 8, 303, 175, 192, 446, 589, 634, 365, 657, 14, \ 185, 537, 78, 699, 422, 540, 3, 134, 341, 707, \ 80, 98, 323, 383, 186, 264, 336, 491, 498, 582, \ 642, 648, 314, 54, 190, 296, 350, 492, 588, 363, \ 480, 396, 690, 57, 59, 70, 106, 184, 314, 329, \ 353, 362, 603, 667, 544, 118, 274, 424, 650, 669, \ 486, 552, 631, 691, 564, 540, 310, 29, 168, 241, \ 274, 372, 190, 350, 369, 49, 315, 378, 381, 506, \ 639, 158, 623, 159, 433, 26, 117, 160, 206, 208, \ 237, 271, 523, 85, 398, 403, 448, 569, 605, 644, \ 231, 234, 304, 363, 654, 167, 242, 258, 295, 327, \ 348, 474, 483, 488, 501, 526, 631, 686, 691, 114, \ 186, 498, 579, 42, 221, 250, 332, 86, 269, 568, \ 659, 66, 69, 108, 126, 215, 331, 335, 336, 367, \ 526, 535, 548, 562, 612, 672, 233, 695, 228, 1, \ 571, 214, 587, 408, 439, 178, 337, 389, 416, 423, \ 499, 617, 79, 91, 97, 107, 116, 117, 147, 164, \ 173, 182, 186, 206, 271, 427, 485, 502, 511, 570, \ 635, 86, 510, 558, 607, 664, 215, 535, 45, 78, \ 294, 337, 383, 592, 707, 286, 13, 56, 224, 293, \ 361, 266, 375, 27, 128, 212, 326, 477, 545, 555, \ 564, 24, 37, 41, 132, 149, 189, 241, 285, 364, \ 399, 401, 424, 479, 536, 565, 644, 650, 683, 121, \ 178, 556, 630, 709, 62, 193, 215, 367, 526, 98, \ 150, 189, 418, 619, 674, 472, 618, 49, 108, 114, \ 120, 133, 210, 273, 310, 326, 381, 386, 432, 449, \ 493, 494, 512, 542, 568, 639, 659, 676, 55, 210, \ 219, 506, 101, 414, 163, 428, 478, 675, 529, 532, \ 637, 709, 5, 60, 159, 260, 300, 417, 529, 613, \ 213, 338, 702, 2, 135, 180, 214, 322, 130, 283, \ 488, 359, 308, 61, 203, 229, 270, 406, 408, 638, \ 217, 84, 125, 153, 209, 378, 538, 704, 76, 19, \ 253, 650, 337, 443, 449, 512, 541, 624, 639, 659, \ 686, 85, 503, 302, 518, 213, 633, 22, 23, 289, \ 500, 422, 692, 481, 485, 397, 62, 443, 105, 74, \ 616, 12, 20, 36, 44, 57, 75, 92, 99, 248, \ 251, 256, 259, 311, 335, 343, 390, 394, 433, 452, \ 456, 463, 496, 620, 625, 629, 637, 672, 330, 405, \ 442, 520, 574, 645, 54, 190, 296, 350, 471, 277, \ 454, 498, 538, 620, 16, 45, 67, 294, 463, 527, \ 555, 597, 609, 637, 372, 615, 216, 227, 183, 606, \ 50, 65, 139, 421, 107, 20, 56, 57, 394, 452, \ 61, 127, 143, 185, 199, 218, 308, 388, 18, 598, \ 86, 510, 524, 111, 414, 78, 176, 699, 4, 38, \ 42, 103, 131, 172, 250, 332, 395, 404, 457, 509, \ 527, 689, 79, 83, 89, 90, 91, 97, 119, 147, \ 159, 223, 225, 266, 267, 272, 278, 282, 298, 364, \ 368, 373, 418, 428, 437, 450, 451, 511, 523, 531, \ 536, 619, 626, 635, 652, 674, 680, 682, 242, 327, \ 348, 356, 405, 513, 684, 696, 181, 426, 72, 594, \ 74, 12, 27, 34, 154, 259, 337, 338, 391, 404, \ 416, 432, 522, 527, 555, 566, 586, 244, 41, 90, \ 150, 189, 536, 674, 32, 333, 649, 242, 383, 466, \ 496, 20, 28, 31, 43, 75, 92, 113, 121, 129, \ 143, 145, 165, 169, 178, 194, 199, 233, 240, 248, \ 251, 256, 300, 304, 305, 319, 324, 327, 333, 343, \ 344, 390, 391, 409, 423, 436, 447, 452, 456, 474, \ 501, 522, 528, 534, 537, 551, 556, 560, 572, 586, \ 599, 602, 604, 609, 614, 620, 629, 630, 646, 656, \ 687, 697, 187, 327, 481, 492, 664, 669, 31, 43, \ 127, 256, 305, 308, 343, 344, 433, 436, 452, 497, \ 560, 614, 620, 625, 630, 646, 213, 483, 7, 40, \ 63, 170, 254, 279, 470, 667, 213, 573, 313, 128, \ 315, 494, 659, 60, 191, 6, 87, 165, 442, 129, \ 165, 319, 409, 37, 159, 319, 365, 401, 412, 8, \ 64, 82, 110, 126, 134, 156, 280, 320, 336, 382, \ 427, 453, 468, 516, 653, 703, 32, 118, 342, 668, \ 8, 363, 313, 240, 18, 144, 455, 622, 146, 171, \ 49, 55, 128, 210, 219, 343, 381, 449, 494, 512, \ 541, 568, 639, 57, 297, 365, 34, 249, 348, 367, \ 513, 526, 535, 580, 658, 59, 184, 287, 314, 353, \ 467, 470, 476, 632, 443, 652, 481, 628, 47, 112, \ 115, 152, 293, 388, 493, 513, 606, 24, 98, 150, \ 285, 465, 644, 428, 544, 262, 315, 357, 427, 431, \ 705, 355, 570, 149, 479, 612, 696, 13, 224, 425, \ 221, 174, 194, 251, 321, 396, 517, 636, 702, 38, \ 172, 514, 161, 215, 336, 564, 612, 672, 678, 684, \ 133, 546, 82, 453, 125, 262, 563, 679, 369, 478, \ 492, 4, 15, 88, 218, 294, 462, 534, 545, 592, \ 709, 71, 212, 413, 18, 144, 489, 622, 257, 122, \ 99, 483, 201, 239, 389, 634, 174, 107, 193, 116, \ 179, 694, 128, 697, 95, 100, 114, 175, 192, 239, \ 273, 277, 306, 393, 446, 454, 521, 586, 589, 634, \ 2, 61, 66, 374, 399, 374, 160, 489, 80, 464, \ 688, 493, 516, 558, 558, 136, 156, 584, 152, 682, \ 358, 127, 143, 202, 240, 656, 88, 103, 627, 92, \ 113, 126, 159, 165, 167, 268, 295, 442, 500, 505, \ 515, 551, 573, 633, 692, 469, 679, 424, 533, 683, \ 551, 112, 204, 402, 281, 392, 43, 295, 505, 39, \ 325, 368, 590, 595, 157, 202, 410, 168, 280, 282, \ 328, 662, 74, 93, 458, 45, 473, 216, 595, 379, \ 366, 177, 357, 226, 76, 226, 205, 671, 9, 133, \ 507, 507, 89, 123, 140, 450, 635, 675, 136, 137, \ 281, 58, 124, 474, 505, 612, 372, 384, 657, 429, \ 30, 495, 628, 122, 599, 464, 628, 664, 243, 32, \ 302, 360, 626, 652, 331, 317, 622, 209, 264, 485, \ 487, 518, 628, 275, 593, 694, 346, 458, 589, 68, \ 88, 320, 477, 627, 142, 155, 603, 162, 18, 571, \ 317, 455, 227, 150, 619, 96, 649, 576, 61, 177, \ 376, 26, 406, 217, 220, 160, 208, 626, 533, 479, \ 677, 51, 71, 696, 257, 583, 39, 251, 702, 283, \ 123, 355, 430, 438, 482, 682, 288, 688, 50, 94, \ 183, 339, 540, 349, 178, 295, 499, 501, 522, 566, \ 633, 191, 643, 662, 163, 526, 151, 217, 312, 74, \ 585, 616, 197, 309, 704, 397, 410, 142, 166, 291, \ 407, 434, 96, 125, 333, 238, 454, 110, 135, 314, \ 603, 345, 260, 229, 132, 285, 360, 410, 596, 440, \ 69, 666, 235, 118, 77, 265, 51, 161, 631, 366, \ 539, 5, 567, 4, 38, 131, 416, 522, 610, 617, \ 590, 238, 366, 171, 69, 563, 228, 517, 30, 374, \ 583, 318, 420, 640, 53, 66, 229, 33, 136, 137, \ 373, 211, 550, 579, 410, 76, 306, 439, 292, 370, \ 583, 669, 597, 114, 461, 58, 26, 499, 153, 563, \ 77, 353, 603, 227, 5, 193, 147, 223, 355, 375, \ 430, 438, 473, 639, 197, 447, 238, 291, 309, 470, \ 141, 572, 581, 399, 197, 581, 448, 132, 253, 374, \ 399, 93, 561, 69, 99, 157, 316, 562, 487, 638, \ 44, 264, 155, 355, 661, 61, 360, 635, 33, 694, \ 103, 98, 253, 372, 550, 207, 226, 163, 1, 104, \ 518, 636, 487, 585, 554, 698, 531, 679, 298, 437, \ 595, 429, 236, 267, 268, 174, 321, 517, 599, 649, \ 702, 313, 655, 46, 288, 382, 549, 587, 671, 706, \ 376, 559, 621, 15, 555, 455, 291, 232, 44, 394, \ 73, 238, 591, 475, 525, 598, 354, 234, 257, 698, \ 166, 176, 21, 179, 183, 486, 161, 607, 23, 36, \ 141, 146, 171, 194, 204, 234, 260, 324, 389, 411, \ 474, 500, 504, 505, 520, 574, 613, 654, 655, 658, \ 382, 610, 479, 366, 228, 163, 39, 430, 146, 351, \ 371, 109, 33, 264, 564, 576, 666, 684, 2, 558, \ 28, 255, 451, 46, 77, 119, 156, 168, 198, 200, \ 253, 274, 281, 303, 307, 328, 349, 352, 364, 373, \ 392, 400, 401, 424, 490, 491, 519, 533, 565, 584, \ 593, 653, 683, 706, 596, 621, 236, 1, 166, 109, \ 205, 550, 50, 164, 230, 438, 495, 508, 559, 297, \ 661, 37, 554, 641, 230, 257, 375, 491, 15, 154, \ 123, 438, 585, 187, 561, 496, 623, 316, 150, 619, \ 399, 309, 175, 677, 142, 557, 262, 229, 455, 196, \ 21, 179, 63, 106, 224, 252, 254, 279, 287, 419, \ 425, 530, 578, 685, 67, 81, 700, 95, 100, 192, \ 239, 273, 306, 316, 393, 446, 521, 589, 236, 408, \ 593, 354, 429, 27, 218, 477, 354, 58, 180, 398, \ 34, 124, 175, 666, 47, 351, 96, 21, 51, 19, \ 119, 137, 312, 444, 519, 653, 357, 284, 212, 255, \ 463, 235, 478, 661, 21, 179, 498, 340, 576, 232, \ 235, 245, 415, 83, 623, 198, 482, 107, 504, 161, \ 209, 378, 149, 241, 232, 220, 249, 663, 95, 201, \ 277, 263, 297, 301, 377, 433, 497, 693, 154, 205, \ 317, 17, 148, 347, 288, 486, 575, 232, 440, 225, \ 503, 569, 415, 692, 93, 660, 195, 318, 400, 445, \ 640, 200, 206, 243, 662, 177, 217, 115, 293, 670, \ 321, 466, 665, 698, 81, 135, 539, 81, 663, 700, \ 205, 537, 559, 665, 202, 486, 540, 684, 3, 60, \ 325, 411, 443, 460, 529, 567, 77, 636, 331, 596, \ 265, 507, 267, 418, 93, 367, 580, 627, 641, 458, \ 130, 435, 585, 51, 124, 371, 507, 573, 407, 155, \ 372, 151, 79, 223, 282, 626, 668, 216, 595, 569, \ 322, 638, 143, 152, 323, 557, 384, 665, 245, 36, \ 103, 496, 627, 22, 216, 607, 91, 676, 226, 96, \ 291, 460, 318, 420, 116, 370, 448, 525, 577, 594, \ 236, 312, 158, 658, 130, 616, 3, 171, 228, 231, \ 247, 304, 383, 406, 466, 528, 623, 658, 144, 204, \ 222, 548, 622, 654, 407, 154, 663, 257, 156, 435, \ 591, 36, 234, 591, 599, 677, 561, 577, 80, 167, \ 181, 259, 380, 411, 480, 501, 515, 633, 688, 262, \ 37, 276, 641, 440, 275, 557, 213, 295, 480, 313, \ 655, 7, 177, 252, 279, 293, 329, 362, 419, 530, \ 632, 685, 270, 481, 568, 56, 275, 230, 203, 174, \ 357, 517, 508, 463, 590, 583, 17, 254, 707, 158, \ 73, 103, 14, 65, 430, 222, 94, 641, 225, 503, \ 569, 447, 209, 81, 700, 272, 621, 346, 236, 510, \ 524, 420, 692, 158, 36, 520, 657, 93, 429, 461, \ 1, 30, 518, 571, 94, 183, 191, 508, 125, 704, \ 229, 312, 678, 380, 230, 469, 430, 397, 404, 539, \ 15, 44, 68, 69, 88, 99, 122, 157, 259, 335, \ 417, 449, 474, 76, 265, 290, 416, 547, 112, 495, \ 567, 341, 468, 583, 81, 366, 96, 7, 106, 684, \ 524, 339, 426, 618, 410, 80, 346, 688, 595, 546, \ 543, 4, 38, 48, 218, 457, 610, 708, 48, 141, \ 151, 21, 44, 3, 8, 311, 687, 9, 237, 243, \ 33, 76, 664, 45, 68, 88, 627, 637, 10, 222, \ 698, 111, 543, 63, 70, 184, 254, 530, 667, 151, \ 59, 361, 17, 317, 84, 125, 704, 83, 531, 611, \ 626, 355, 473, 644, 654, 232, 137, 524, 15, 549, \ 29, 392, 356, 681, 599, 222, 138, 559, 638, 17, \ 261, 331, 670, 392, 58, 464, 25, 245, 545, 467, \ 641, 9, 706, 155, 207, 665, 72, 25, 245, 46, \ 469, 139, 350, 284, 696, 65, 421, 600, 249, 368, \ 384, 567, 590, 379, 550, 596, 104, 186, 284, 488, \ 579, 109, 115, 663, 140, 205, 261, 249, 80, 464, \ 215, 5, 443, 567, 476, 636, 71, 294, 496, 708, \ 68, 126, 259, 311, 338, 532, 549, 597, 692, 708, \ 238, 152, 35, 220, 387, 380, 74, 487, 275, 337, \ 39, 73, 102, 113, 167, 181, 258, 300, 325, 335, \ 348, 368, 456, 515, 519, 547, 572, 691, 339, 359, \ 412, 299, 11, 406, 548, 572, 575, 621, 268, 173, \ 465, 419, 415, 10, 346, 458, 72, 101, 111, 212, \ 414, 543, 594, 608, 615, 77, 263, 301, 377, 497, \ 566, 693, 33, 209, 508, 429, 671, 596, 107, 193, \ 657, 138, 73, 102, 268, 434, 575, 288, 7, 106, \ 632, 199, 305, 604, 614, 687, 609, 86, 269, 510, \ 321, 441, 466, 607, 292, 445, 508, 516, 72, 101, \ 111, 543, 594, 608, 615, 585, 605, 289, 655, 197, \ 694, 203, 148, 211, 347, 671, 413, 593, 607, 35, \ 162, 220, 387, 158, 548, 32, 84, 153, 333, 41, \ 323, 465, 619, 346, 345, 302, 696, 440, 662, 94, \ 384, 569, 11, 286, 193, 263, 301, 377, 693, 331, \ 605, 5, 288, 640, 308, 677, 475, 85, 403, 269, \ 296, 471, 588, 177, 581, 35, 220, 118, 297, 2, \ 553, 354, 360, 10, 204, 249, 499, 576, 262, 99, \ 698, 462, 163, 665, 235, 591, 413, 458, 398, 151, \ 664, 244, 486, 470, 667, 654, 662, 538, 700, 73, \ 694, 162, 35, 591, 283, 246, 276, 330, 340, 405, \ 407, 484, 587, 465, 535, 247, 376, 440, 122, 679, \ 341, 642, 25, 477, 323, 191, 338, 354, 605, 679, \ 437, 507, 369, 705, 377, 398, 222, 528, 17, 415, \ 84, 153, 563, 359, 593,1458 ] ) j = np.array ( [ \ 1, 2, 3, 4, 4, 4, 4, 4, 4, 4, \ 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, \ 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, \ 4, 4, 4, 4, 5, 5, 6, 6, 6, 6, \ 6, 9, 10, 10, 10, 10, 11, 11, 11, 12, \ 12, 13, 13, 13, 13, 13, 13, 13, 13, 13, \ 13, 13, 13, 13, 13, 13, 14, 15, 16, 16, \ 16, 18, 20, 20, 21, 21, 21, 21, 21, 22, \ 22, 25, 25, 25, 25, 25, 25, 25, 25, 25, \ 25, 25, 25, 26, 26, 26, 26, 26, 26, 26, \ 26, 26, 28, 28, 28, 28, 28, 28, 28, 28, \ 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, \ 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, \ 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, \ 31, 32, 33, 34, 34, 34, 34, 34, 34, 34, \ 37, 38, 38, 41, 42, 42, 42, 42, 42, 42, \ 42, 42, 43, 45, 45, 45, 46, 46, 46, 46, \ 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, \ 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, \ 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, \ 46, 47, 47, 48, 49, 49, 50, 51, 51, 51, \ 51, 52, 52, 52, 52, 52, 52, 52, 52, 52, \ 52, 52, 52, 53, 53, 53, 54, 54, 54, 54, \ 54, 54, 54, 54, 54, 54, 54, 54, 55, 55, \ 55, 55, 55, 55, 55, 57, 57, 57, 58, 60, \ 60, 60, 60, 62, 62, 63, 63, 63, 63, 63, \ 63, 63, 63, 63, 63, 64, 64, 64, 64, 64, \ 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, \ 64, 64, 64, 64, 64, 64, 64, 65, 65, 66, \ 67, 67, 67, 67, 68, 69, 69, 69, 70, 70, \ 70, 70, 70, 70, 70, 70, 72, 72, 72, 72, \ 73, 74, 75, 79, 79, 79, 79, 79, 79, 79, \ 79, 80, 80, 80, 81, 82, 83, 84, 87, 87, \ 88, 88, 89, 89, 89, 89, 90, 91, 91, 91, \ 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, \ 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, \ 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, \ 92, 92, 92, 94, 94, 95, 95, 95, 98, 98, \ 99, 100, 100, 100, 102, 103, 104, 104, 104, 104, \ 105, 106, 110, 110, 110, 110, 110, 110, 110, 110, \ 110, 110, 111, 111, 111, 111, 111, 111, 111, 111, \ 111, 111, 112, 112, 112, 112, 112, 112, 112, 112, \ 113, 113, 116, 116, 116, 116, 116, 116, 116, 116, \ 116, 116, 116, 116, 117, 117, 117, 120, 120, 121, \ 123, 125, 125, 125, 125, 125, 125, 126, 127, 129, \ 129, 129, 129, 130, 130, 130, 131, 131, 131, 131, \ 131, 131, 131, 131, 131, 131, 132, 133, 133, 134, \ 134, 134, 136, 136, 137, 137, 137, 137, 137, 138, \ 139, 139, 139, 139, 140, 142, 142, 142, 142, 142, \ 142, 143, 143, 143, 144, 145, 146, 146, 147, 147, \ 147, 147, 147, 147, 148, 148, 148, 148, 149, 149, \ 149, 150, 150, 154, 154, 155, 156, 156, 156, 156, \ 156, 156, 156, 156, 156, 159, 159, 159, 159, 159, \ 159, 159, 160, 160, 162, 162, 164, 164, 165, 165, \ 165, 166, 167, 167, 167, 167, 167, 167, 167, 167, \ 167, 167, 167, 167, 168, 168, 168, 168, 168, 168, \ 168, 169, 170, 170, 170, 170, 170, 171, 171, 171, \ 172, 172, 172, 172, 172, 173, 173, 173, 173, 173, \ 173, 174, 174, 174, 174, 174, 174, 178, 178, 181, \ 181, 181, 184, 184, 184, 184, 184, 184, 184, 184, \ 184, 185, 185, 186, 186, 186, 186, 186, 186, 186, \ 186, 187, 189, 189, 190, 190, 190, 190, 190, 190, \ 191, 192, 194, 195, 195, 196, 196, 198, 198, 198, \ 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, \ 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, \ 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, \ 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, \ 199, 199, 199, 199, 199, 200, 200, 200, 201, 201, \ 201, 202, 202, 204, 205, 205, 206, 206, 206, 206, \ 206, 208, 208, 208, 208, 208, 208, 208, 210, 210, \ 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, \ 210, 210, 211, 211, 211, 213, 213, 214, 214, 214, \ 214, 214, 214, 214, 214, 214, 215, 217, 218, 219, \ 219, 219, 219, 219, 219, 219, 219, 219, 220, 220, \ 220, 220, 220, 220, 220, 220, 221, 224, 224, 224, \ 224, 224, 224, 224, 224, 224, 224, 224, 224, 224, \ 224, 224, 224, 224, 224, 224, 224, 224, 224, 225, \ 225, 225, 227, 229, 229, 230, 231, 231, 233, 237, \ 238, 238, 239, 239, 239, 239, 239, 239, 239, 239, \ 239, 240, 240, 240, 240, 240, 240, 240, 240, 241, \ 241, 241, 241, 241, 241, 242, 243, 245, 246, 246, \ 246, 247, 247, 247, 248, 248, 248, 248, 248, 248, \ 248, 248, 248, 248, 249, 249, 250, 250, 250, 250, \ 250, 250, 251, 251, 251, 252, 252, 252, 252, 252, \ 252, 253, 253, 254, 254, 255, 255, 256, 258, 258, \ 258, 258, 261, 263, 263, 263, 263, 266, 266, 266, \ 266, 266, 266, 266, 267, 268, 269, 269, 270, 270, \ 270, 270, 271, 271, 271, 271, 271, 271, 271, 273, \ 273, 273, 274, 277, 277, 277, 278, 278, 278, 278, \ 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, \ 278, 278, 278, 278, 279, 279, 280, 280, 280, 281, \ 281, 281, 282, 282, 282, 282, 285, 285, 285, 286, \ 286, 289, 289, 289, 289, 289, 289, 289, 289, 290, \ 291, 291, 291, 292, 292, 292, 293, 294, 296, 296, \ 296, 296, 296, 298, 298, 298, 300, 300, 300, 301, \ 302, 302, 302, 302, 302, 302, 302, 302, 303, 303, \ 303, 304, 304, 304, 304, 304, 305, 306, 307, 307, \ 310, 310, 310, 311, 313, 315, 315, 316, 316, 316, \ 316, 318, 318, 318, 318, 318, 318, 320, 320, 321, \ 321, 322, 322, 322, 322, 322, 322, 322, 322, 322, \ 322, 322, 324, 324, 324, 324, 324, 324, 324, 325, \ 327, 327, 329, 330, 330, 330, 331, 332, 332, 332, \ 332, 332, 332, 333, 333, 333, 333, 334, 334, 334, \ 337, 338, 338, 338, 339, 341, 341, 341, 341, 341, \ 341, 342, 342, 342, 342, 342, 342, 342, 342, 342, \ 343, 343, 344, 344, 344, 344, 344, 344, 344, 344, \ 344, 344, 344, 344, 344, 344, 345, 345, 347, 348, \ 348, 348, 348, 348, 348, 348, 348, 348, 348, 348, \ 348, 349, 351, 351, 351, 351, 353, 353, 354, 355, \ 356, 358, 359, 359, 362, 362, 362, 362, 362, 362, \ 364, 364, 364, 364, 364, 364, 364, 367, 367, 368, \ 368, 369, 370, 370, 370, 370, 370, 370, 370, 370, \ 370, 370, 371, 371, 371, 371, 371, 371, 371, 371, \ 371, 373, 373, 373, 374, 376, 376, 377, 378, 380, \ 381, 381, 381, 381, 381, 381, 381, 381, 383, 385, \ 385, 385, 385, 386, 386, 386, 386, 386, 386, 386, \ 386, 386, 386, 386, 386, 387, 387, 387, 387, 387, \ 388, 388, 389, 389, 390, 390, 390, 391, 392, 393, \ 393, 393, 393, 393, 393, 393, 394, 395, 395, 395, \ 395, 395, 395, 395, 396, 397, 399, 400, 400, 400, \ 400, 400, 400, 400, 400, 400, 400, 400, 400, 400, \ 400, 400, 400, 400, 400, 400, 400, 400, 400, 400, \ 400, 400, 400, 400, 400, 400, 400, 400, 400, 400, \ 400, 400, 400, 400, 401, 401, 402, 405, 405, 405, \ 405, 405, 405, 405, 405, 405, 405, 405, 405, 405, \ 405, 405, 405, 405, 405, 405, 406, 406, 406, 407, \ 408, 408, 409, 412, 414, 414, 414, 414, 414, 414, \ 414, 414, 414, 414, 414, 416, 416, 416, 416, 416, \ 416, 416, 416, 416, 416, 416, 416, 416, 418, 420, \ 421, 421, 422, 423, 424, 424, 424, 424, 424, 424, \ 424, 424, 425, 427, 427, 428, 428, 428, 428, 428, \ 432, 432, 433, 433, 433, 433, 433, 433, 433, 433, \ 433, 433, 433, 433, 433, 433, 433, 433, 433, 434, \ 435, 436, 436, 436, 436, 436, 436, 436, 436, 436, \ 436, 437, 437, 437, 437, 437, 437, 437, 438, 438, \ 439, 441, 442, 444, 445, 445, 445, 446, 446, 446, \ 446, 446, 446, 446, 446, 448, 448, 448, 448, 448, \ 448, 448, 448, 449, 449, 449, 449, 450, 451, 451, \ 452, 452, 452, 452, 452, 452, 452, 452, 452, 452, \ 453, 453, 454, 454, 454, 454, 454, 455, 455, 456, \ 456, 456, 457, 457, 459, 459, 460, 461, 461, 462, \ 464, 465, 465, 466, 468, 468, 468, 468, 468, 468, \ 468, 468, 470, 471, 471, 471, 471, 471, 471, 472, \ 474, 475, 475, 476, 476, 476, 476, 476, 476, 476, \ 476, 476, 476, 476, 478, 479, 479, 479, 479, 481, \ 483, 483, 483, 483, 485, 486, 488, 490, 490, 490, \ 490, 490, 492, 492, 492, 494, 494, 494, 494, 494, \ 494, 496, 496, 497, 497, 499, 502, 502, 502, 502, \ 502, 502, 502, 503, 503, 503, 503, 503, 503, 503, \ 504, 504, 504, 504, 504, 505, 505, 505, 505, 505, \ 505, 505, 505, 505, 505, 505, 505, 505, 505, 506, \ 506, 506, 506, 509, 509, 509, 509, 510, 510, 512, \ 512, 513, 513, 513, 513, 513, 513, 513, 513, 513, \ 513, 513, 513, 513, 513, 513, 514, 514, 517, 518, \ 518, 520, 520, 521, 521, 522, 522, 522, 522, 522, \ 522, 522, 523, 523, 523, 523, 523, 523, 523, 523, \ 523, 523, 523, 523, 523, 523, 523, 523, 523, 523, \ 523, 524, 524, 524, 524, 524, 526, 526, 527, 527, \ 527, 527, 527, 527, 527, 529, 530, 530, 530, 530, \ 530, 531, 531, 532, 532, 532, 532, 532, 532, 532, \ 532, 533, 533, 533, 533, 533, 533, 533, 533, 533, \ 533, 533, 533, 533, 533, 533, 533, 533, 533, 534, \ 534, 534, 534, 534, 535, 535, 535, 535, 535, 536, \ 536, 536, 536, 536, 536, 537, 537, 541, 541, 541, \ 541, 541, 541, 541, 541, 541, 541, 541, 541, 541, \ 541, 541, 541, 541, 541, 541, 541, 541, 542, 542, \ 542, 542, 543, 543, 544, 544, 544, 544, 545, 545, \ 545, 545, 547, 547, 547, 547, 547, 547, 547, 547, \ 549, 549, 549, 553, 553, 553, 553, 553, 554, 554, \ 555, 556, 557, 559, 559, 559, 559, 559, 559, 559, \ 562, 563, 563, 563, 563, 563, 563, 563, 564, 565, \ 565, 565, 566, 567, 568, 568, 568, 568, 568, 568, \ 568, 569, 569, 571, 571, 573, 573, 574, 574, 574, \ 574, 575, 575, 577, 577, 578, 580, 581, 582, 585, \ 585, 586, 586, 586, 586, 586, 586, 586, 586, 586, \ 586, 586, 586, 586, 586, 586, 586, 586, 586, 586, \ 586, 586, 586, 586, 586, 586, 586, 586, 587, 587, \ 587, 587, 587, 587, 588, 588, 588, 588, 588, 589, \ 589, 589, 589, 589, 592, 592, 592, 592, 592, 592, \ 592, 592, 592, 592, 593, 594, 595, 597, 598, 598, \ 600, 600, 600, 600, 601, 602, 602, 602, 602, 602, \ 604, 604, 604, 604, 604, 604, 604, 604, 606, 606, \ 607, 607, 607, 608, 608, 609, 609, 609, 610, 610, \ 610, 610, 610, 610, 610, 610, 610, 610, 610, 610, \ 610, 610, 611, 611, 611, 611, 611, 611, 611, 611, \ 611, 611, 611, 611, 611, 611, 611, 611, 611, 611, \ 611, 611, 611, 611, 611, 611, 611, 611, 611, 611, \ 611, 611, 611, 611, 611, 611, 611, 611, 612, 612, \ 612, 612, 612, 612, 612, 612, 613, 613, 615, 615, \ 616, 617, 617, 617, 617, 617, 617, 617, 617, 617, \ 617, 617, 617, 617, 617, 617, 617, 618, 619, 619, \ 619, 619, 619, 619, 620, 620, 620, 621, 623, 623, \ 623, 625, 625, 625, 625, 625, 625, 625, 625, 625, \ 625, 625, 625, 625, 625, 625, 625, 625, 625, 625, \ 625, 625, 625, 625, 625, 625, 625, 625, 625, 625, \ 625, 625, 625, 625, 625, 625, 625, 625, 625, 625, \ 625, 625, 625, 625, 625, 625, 625, 625, 625, 625, \ 625, 625, 625, 625, 625, 625, 625, 625, 625, 625, \ 625, 625, 628, 628, 628, 628, 628, 628, 629, 629, \ 629, 629, 629, 629, 629, 629, 629, 629, 629, 629, \ 629, 629, 629, 629, 629, 629, 631, 631, 632, 632, \ 632, 632, 632, 632, 632, 632, 633, 633, 634, 639, \ 639, 639, 639, 643, 643, 645, 645, 645, 645, 646, \ 646, 646, 646, 647, 647, 647, 647, 647, 647, 648, \ 648, 648, 648, 648, 648, 648, 648, 648, 648, 648, \ 648, 648, 648, 648, 648, 648, 649, 650, 651, 652, \ 653, 654, 655, 656, 657, 657, 657, 657, 658, 658, \ 659, 659, 659, 659, 659, 659, 659, 659, 659, 659, \ 659, 659, 659, 661, 661, 661, 666, 666, 666, 666, \ 666, 666, 666, 666, 666, 667, 667, 667, 667, 667, \ 667, 667, 667, 667, 668, 668, 669, 669, 670, 670, \ 670, 670, 670, 670, 670, 672, 673, 674, 674, 674, \ 674, 674, 674, 675, 675, 679, 680, 680, 680, 680, \ 680, 682, 682, 683, 683, 684, 684, 685, 685, 685, \ 689, 690, 690, 690, 690, 690, 690, 690, 690, 695, \ 695, 695, 696, 696, 696, 696, 696, 696, 696, 696, \ 697, 697, 703, 703, 704, 704, 704, 704, 705, 705, \ 705, 708, 708, 708, 708, 708, 708, 708, 708, 708, \ 708, 709, 709, 710, 711, 711, 711, 711, 712, 713, \ 714, 714, 715, 715, 715, 715, 716, 717, 717, 718, \ 719, 720, 721, 721, 722, 722, 722, 722, 722, 722, \ 722, 722, 722, 722, 722, 722, 722, 722, 722, 722, \ 723, 723, 723, 724, 725, 726, 727, 728, 729, 729, \ 729, 730, 731, 731, 732, 733, 733, 733, 734, 735, \ 736, 737, 737, 737, 737, 737, 738, 738, 738, 739, \ 739, 739, 739, 739, 739, 739, 739, 739, 739, 739, \ 739, 739, 739, 739, 739, 740, 741, 742, 742, 742, \ 743, 744, 744, 744, 745, 745, 746, 746, 746, 747, \ 747, 747, 748, 749, 750, 751, 752, 753, 753, 753, \ 753, 754, 755, 756, 757, 758, 759, 760, 760, 761, \ 762, 763, 764, 765, 766, 767, 768, 769, 770, 771, \ 772, 773, 774, 774, 774, 774, 774, 775, 776, 776, \ 776, 777, 777, 777, 777, 777, 778, 779, 780, 781, \ 782, 782, 782, 783, 784, 785, 786, 786, 787, 788, \ 789, 790, 791, 791, 792, 793, 793, 794, 795, 795, \ 795, 795, 795, 796, 797, 798, 799, 799, 800, 801, \ 801, 801, 801, 801, 802, 802, 802, 803, 804, 804, \ 805, 806, 807, 808, 808, 809, 810, 811, 812, 812, \ 813, 814, 815, 816, 817, 818, 818, 819, 820, 821, \ 821, 822, 822, 822, 823, 824, 825, 826, 826, 827, \ 828, 828, 828, 828, 828, 828, 829, 830, 831, 831, \ 831, 831, 831, 832, 833, 833, 833, 833, 833, 833, \ 833, 834, 834, 835, 836, 837, 838, 839, 840, 841, \ 841, 841, 842, 843, 844, 845, 846, 847, 848, 849, \ 850, 851, 852, 853, 853, 854, 854, 855, 855, 856, \ 856, 857, 858, 859, 860, 860, 860, 860, 861, 862, \ 863, 863, 864, 865, 866, 867, 868, 868, 868, 869, \ 870, 871, 871, 872, 872, 872, 872, 872, 872, 872, \ 873, 874, 875, 876, 877, 878, 879, 879, 880, 881, \ 882, 883, 883, 884, 885, 886, 886, 887, 888, 888, \ 888, 889, 889, 889, 890, 891, 892, 892, 893, 893, \ 893, 893, 894, 895, 896, 897, 898, 898, 899, 899, \ 900, 900, 900, 901, 902, 903, 904, 904, 904, 904, \ 904, 904, 904, 905, 906, 907, 908, 909, 910, 911, \ 912, 912, 913, 914, 915, 915, 916, 917, 917, 917, \ 917, 918, 919, 920, 920, 920, 921, 922, 923, 924, \ 925, 926, 927, 928, 929, 930, 931, 931, 932, 933, \ 934, 935, 935, 935, 935, 936, 936, 937, 938, 938, \ 938, 939, 940, 941, 942, 943, 944, 945, 946, 946, \ 947, 948, 949, 950, 951, 952, 952, 952, 953, 954, \ 955, 956, 956, 957, 957, 957, 957, 957, 957, 957, \ 958, 959, 960, 961, 961, 962, 963, 964, 965, 966, \ 967, 968, 968, 969, 970, 970, 971, 972, 973, 974, \ 975, 976, 977, 977, 978, 978, 979, 980, 981, 981, \ 981, 981, 981, 981, 981, 981, 981, 981, 981, 981, \ 981, 981, 981, 981, 981, 981, 981, 981, 981, 981, \ 982, 983, 984, 985, 986, 987, 988, 989, 990, 990, \ 990, 991, 992, 992, 993, 994, 994, 994, 995, 996, \ 997, 998, 999,1000,1000,1000,1000,1000,1000,1000, \ 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, \ 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, \ 1000,1000,1000,1000,1001,1002,1003,1004,1005,1006, \ 1007,1007,1008,1008,1008,1008,1008,1009,1010,1011, \ 1011,1012,1013,1013,1014,1014,1014,1014,1015,1015, \ 1016,1016,1017,1018,1019,1020,1020,1021,1022,1023, \ 1024,1025,1026,1027,1028,1029,1030,1031,1031,1032, \ 1033,1033,1034,1034,1034,1034,1034,1034,1034,1034, \ 1034,1034,1034,1034,1035,1036,1036,1037,1037,1037, \ 1037,1037,1037,1037,1037,1037,1037,1037,1038,1038, \ 1039,1040,1041,1042,1042,1042,1043,1044,1045,1046, \ 1047,1047,1047,1048,1049,1049,1050,1051,1052,1053, \ 1053,1053,1053,1053,1053,1053,1054,1055,1056,1056, \ 1056,1057,1058,1058,1059,1059,1059,1060,1061,1062, \ 1063,1064,1065,1066,1067,1068,1069,1070,1070,1071, \ 1072,1072,1073,1073,1074,1075,1075,1076,1077,1077, \ 1077,1078,1078,1078,1078,1078,1078,1078,1079,1080, \ 1081,1082,1083,1083,1084,1084,1084,1085,1086,1087, \ 1087,1087,1088,1088,1089,1090,1091,1091,1091,1091, \ 1091,1092,1092,1092,1093,1094,1095,1096,1096,1096, \ 1097,1098,1099,1100,1101,1102,1103,1104,1104,1104, \ 1105,1106,1107,1108,1109,1109,1109,1110,1111,1111, \ 1111,1111,1111,1111,1111,1111,1112,1113,1114,1115, \ 1116,1116,1117,1117,1118,1119,1119,1119,1120,1121, \ 1122,1122,1122,1123,1123,1124,1125,1126,1127,1128, \ 1129,1130,1131,1131,1131,1131,1131,1132,1132,1133, \ 1134,1135,1136,1137,1138,1139,1140,1141,1142,1143, \ 1143,1143,1143,1144,1144,1144,1145,1146,1147,1148, \ 1149,1150,1151,1151,1152,1152,1152,1152,1152,1153, \ 1154,1155,1156,1156,1157,1157,1158,1158,1158,1158, \ 1158,1158,1158,1158,1158,1158,1158,1158,1159,1159, \ 1159,1159,1159,1159,1160,1161,1162,1163,1164,1164, \ 1165,1166,1166,1167,1168,1169,1170,1171,1172,1172, \ 1172,1172,1172,1172,1172,1172,1172,1172,1172,1173, \ 1174,1174,1174,1175,1176,1176,1177,1178,1178,1179, \ 1179,1180,1180,1180,1180,1180,1180,1180,1180,1180, \ 1180,1180,1181,1182,1183,1184,1185,1186,1187,1188, \ 1188,1188,1189,1190,1191,1192,1193,1194,1195,1196, \ 1197,1198,1199,1199,1200,1201,1202,1202,1203,1203, \ 1203,1204,1205,1206,1206,1207,1208,1209,1210,1211, \ 1211,1212,1213,1214,1215,1215,1216,1217,1217,1218, \ 1219,1219,1219,1219,1220,1220,1221,1222,1223,1223, \ 1224,1224,1225,1226,1227,1227,1228,1229,1229,1230, \ 1231,1231,1231,1231,1231,1231,1231,1231,1231,1231, \ 1231,1231,1231,1232,1233,1234,1235,1235,1236,1237, \ 1238,1239,1239,1240,1241,1242,1243,1244,1244,1245, \ 1246,1247,1247,1248,1249,1250,1250,1250,1251,1252, \ 1253,1254,1254,1254,1254,1254,1254,1254,1255,1255, \ 1256,1257,1258,1259,1259,1259,1259,1260,1260,1260, \ 1261,1262,1263,1264,1264,1264,1264,1264,1265,1266, \ 1267,1268,1268,1269,1269,1269,1269,1269,1269,1270, \ 1271,1271,1272,1273,1274,1274,1274,1275,1275,1275, \ 1275,1276,1276,1276,1277,1278,1279,1280,1281,1281, \ 1282,1282,1283,1283,1284,1285,1286,1287,1287,1288, \ 1289,1289,1289,1290,1291,1292,1293,1293,1293,1294, \ 1295,1296,1297,1298,1299,1300,1301,1302,1302,1303, \ 1304,1305,1305,1306,1307,1308,1308,1308,1309,1309, \ 1309,1309,1310,1311,1312,1313,1314,1314,1314,1314, \ 1314,1315,1315,1315,1316,1316,1317,1318,1319,1319, \ 1320,1321,1321,1321,1322,1323,1324,1324,1324,1324, \ 1325,1325,1325,1325,1325,1325,1325,1325,1325,1325, \ 1326,1327,1328,1328,1328,1329,1330,1330,1331,1332, \ 1333,1333,1333,1333,1333,1333,1333,1333,1333,1333, \ 1333,1333,1333,1333,1333,1333,1333,1333,1334,1334, \ 1334,1335,1336,1336,1336,1336,1336,1336,1337,1338, \ 1338,1339,1340,1341,1342,1342,1343,1343,1343,1343, \ 1343,1343,1343,1343,1343,1344,1345,1345,1345,1345, \ 1345,1345,1346,1347,1348,1349,1350,1351,1352,1352, \ 1352,1353,1354,1354,1354,1354,1354,1355,1356,1356, \ 1356,1357,1357,1357,1357,1357,1358,1359,1359,1359, \ 1360,1361,1362,1363,1364,1365,1366,1367,1368,1368, \ 1368,1368,1368,1368,1368,1369,1369,1370,1370,1371, \ 1372,1373,1374,1374,1374,1374,1375,1376,1377,1378, \ 1378,1378,1378,1379,1379,1380,1380,1380,1380,1381, \ 1381,1381,1381,1382,1383,1384,1385,1386,1386,1387, \ 1388,1389,1390,1390,1391,1392,1392,1392,1392,1393, \ 1394,1395,1395,1396,1397,1398,1399,1400,1400,1401, \ 1401,1401,1401,1402,1403,1404,1404,1405,1406,1407, \ 1407,1408,1408,1409,1409,1409,1409,1409,1410,1411, \ 1412,1413,1414,1414,1415,1415,1416,1417,1418,1419, \ 1420,1421,1421,1422,1422,1423,1424,1425,1426,1427, \ 1428,1429,1430,1431,1432,1433,1433,1433,1433,1433, \ 1433,1433,1433,1434,1435,1436,1437,1438,1439,1440, \ 1441,1441,1442,1443,1444,1445,1446,1447,1447,1447, \ 1448,1449,1450,1450,1451,1452,1453,1453,1454,1455, \ 1456,1456,1456,1457,1458,1458 ] ) v = np.ones ( 3546 ) # # Shift from one-based to zero-based indexing. # i = i - 1 j = j - 1 return i, j, v def mac1_st ( ): #*****************************************************************************80 # ## mac1_st() returns the mac1 web matrix in sparse triplet form. # # Discussion: # # 5 nodes, 5 links. # # Licensing: # # This code is distributed under the MIT license. # # Modified: # # 27 September 2022 # # Author: # # John Burkardt # # Reference: # # John MacCormick, # Nine Algorithms That Changed the Future: The Ingenious Ideas that # Drive Today's Computers, # Princeton University Press, # ISBN-13: 978-0691158198. # # Output: # # integer i(5), j(5), v(5): the sparse triplet information. # import numpy as np i = np.array ( [ 1, 2, 3, 4, 5 ] ) j = np.array ( [ 2, 5, 1, 1, 1 ] ) v = np.ones ( 5 ) # # Shift from one-based to zero-based indexing. # i = i - 1 j = j - 1 return i, j, v def mac2_st ( ): #*****************************************************************************80 # ## mac2_st() returns the mac2 web matrix in sparse triplet form. # # Discussion: # # 16 nodes, 27 links. # # This matrix appears on page 33 of the reference. # # Licensing: # # This code is distributed under the MIT license. # # Modified: # # 27 September 2022 # # Author: # # John Burkardt # # Reference: # # John MacCormick, # Nine Algorithms That Changed the Future: The Ingenious Ideas that # Drive Today's Computers, # Princeton University Press, # ISBN-13: 978-0691158198. # # Output: # # integer i(27), j(27), v(27): the sparse triplet information. # import numpy as np i = np.array ( [ \ 1, 1, 1, 2, 3, 3, 4, 5, 5, 6, \ 6, 7, 8, 8, 8, 9, 10, 10, 10, 10, \ 10, 11, 12, 13, 14, 15, 16 ] ) j = np.array ( [ \ 2, 3, 6, 4, 4, 5, 5, 7, 8, 5, \ 7, 15, 7, 9, 10, 10, 7, 11, 12, 13, \ 14, 15, 15, 15, 15, 16, 1 ] ) v = np.ones ( 27 ) # # Shift from one-based to zero-based indexing. # i = i - 1 j = j - 1 return i, j, v def medium_st ( ): #*****************************************************************************80 # ## medium_st() returns the medium web matrix in sparse triplet form. # # Discussion: # # 316 nodes, 431 links. # # Licensing: # # This code is distributed under the MIT license. # # Modified: # # 27 September 2022 # # Author: # # John Burkardt # # Output: # # integer i(431), j(431), v(431): the sparse triplet information. # import numpy as np i = np.array ( [ \ 74, 34, 49, 15, 18, 21, 22, 46, 54, 79, \ 84, 37, 82, 38, 57, 71, 6, 9, 37, 55, \ 60, 33, 46, 73, 74, 33, 56, 7, 69, 70, \ 14, 58, 61, 83, 85, 27, 2, 14, 43, 45, \ 48, 71, 19, 20, 60, 79, 6, 35, 48, 45, \ 86, 44, 71, 21, 78, 35, 43, 11, 15, 46, \ 79, 81, 84, 78, 7, 25, 29, 19, 82, 21, \ 30, 35, 43, 48, 67, 73, 86, 34, 24, 29, \ 58, 28, 70, 80, 28, 36, 69, 76, 45, 83, \ 37, 11, 12, 14, 17, 21, 22, 29, 30, 35, \ 42, 43, 44, 45, 46, 48, 62, 63, 67, 72, \ 74, 78, 81, 82, 86, 1, 49, 16, 55, 80, \ 41, 46, 73, 12, 19, 37, 60, 71, 54, 2, \ 4, 44, 45, 78, 9, 63, 81, 50, 9, 47, \ 30, 28, 69, 2, 10, 75, 51, 36, 52, 4, \ 19, 55, 60, 27, 31, 6, 13, 14, 71, 24, \ 18, 35, 43, 44, 86, 75, 12, 19, 25, 37, \ 55, 60, 78, 80, 82, 41, 15, 3, 10, 38, \ 39, 75, 49, 7, 50, 8, 53, 76, 23, 22, \ 38, 65, 13, 42, 54, 84, 1, 7, 12, 80, \ 69, 75, 65, 67, 59, 13, 18, 44, 86, 62, \ 39, 25, 56, 42, 53, 32, 58, 27, 66, 47, \ 38, 85, 4, 10, 40, 68, 52, 65, 76, 79, \ 33, 26, 20, 34, 34, 66, 82, 29, 58, 53, \ 10, 22, 62, 26, 85, 66, 61, 26, 77, 33, \ 30, 52, 36, 57, 68, 5, 76, 70, 39, 57, \ 61, 23, 4, 32, 73, 81, 1, 5, 74, 3, \ 32, 40, 80, 5, 32, 81, 70, 68, 6, 23, \ 41, 17, 36, 29, 58, 64, 83, 85, 17, 53, \ 50, 11, 2, 85, 39, 3, 70, 68, 72, 4, \ 54, 84, 63, 59, 8, 41, 33, 51, 25, 56, \ 61, 83, 2, 65, 51, 27, 77, 84, 72, 3, \ 9, 47, 77, 57, 42, 72, 8, 41, 13, 9, \ 26, 16, 63, 56, 23, 52, 59, 17, 40, 67, \ 7, 25, 56, 61, 16, 8, 38, 63, 59, 8, \ 24, 47, 31, 51, 52, 55, 74, 16, 51, 1, \ 76, 31, 18, 6, 21, 62, 73, 77, 14, 10, \ 49, 24, 32, 77, 40, 40, 53, 68, 50, 5, \ 24, 28, 5, 16, 20, 66, 11, 79, 75, 18, \ 64, 83, 26, 20, 28, 72, 1, 31, 12, 3, \ 20, 31, 65, 17, 67, 39, 30, 22, 64, 49, \ 54, 64, 13, 66, 50, 11, 15, 48, 62, 59, \ 23, 69, 15, 42, 27, 34, 64, 57, 47, 36, \ 316 ] ) j = np.array ( [ \ 1, 2, 10, 11, 11, 11, 11, 11, 11, 11, \ 11, 12, 12, 13, 13, 14, 18, 18, 19, 19, \ 19, 21, 21, 21, 21, 25, 25, 28, 28, 28, \ 29, 29, 29, 29, 29, 31, 34, 35, 35, 35, \ 35, 35, 37, 37, 37, 41, 43, 43, 43, 44, \ 44, 45, 45, 46, 46, 48, 48, 54, 54, 54, \ 54, 54, 54, 55, 56, 56, 58, 60, 60, 62, \ 62, 62, 62, 62, 62, 62, 62, 63, 64, 64, \ 64, 69, 69, 69, 70, 70, 70, 70, 71, 71, \ 72, 73, 73, 73, 73, 73, 73, 73, 73, 73, \ 73, 73, 73, 73, 73, 73, 73, 73, 73, 73, \ 73, 73, 73, 73, 73, 74, 77, 78, 78, 78, \ 79, 81, 81, 82, 82, 82, 82, 83, 84, 86, \ 86, 86, 86, 86, 87, 88, 88, 89, 90, 90, \ 91, 92, 92, 93, 93, 93, 94, 95, 96, 97, \ 98, 98, 98, 99, 99, 100, 100, 100, 100, 101, \ 102, 102, 102, 102, 102, 103, 104, 104, 104, 104, \ 104, 104, 104, 104, 104, 105, 106, 107, 108, 109, \ 110, 111, 112, 113, 114, 115, 116, 116, 117, 118, \ 119, 120, 121, 122, 123, 123, 124, 125, 126, 127, \ 128, 129, 130, 131, 132, 133, 134, 134, 134, 135, \ 136, 137, 137, 138, 139, 140, 141, 142, 143, 144, \ 145, 146, 147, 147, 147, 148, 149, 149, 149, 150, \ 151, 152, 153, 153, 154, 155, 155, 156, 156, 157, \ 158, 159, 159, 160, 160, 161, 162, 163, 164, 165, \ 166, 167, 168, 169, 170, 171, 171, 172, 173, 174, \ 175, 176, 177, 177, 178, 178, 179, 179, 179, 180, \ 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, \ 191, 192, 193, 194, 194, 194, 194, 194, 195, 196, \ 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, \ 207, 207, 208, 209, 210, 211, 212, 213, 214, 214, \ 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, \ 224, 224, 225, 226, 227, 227, 228, 229, 230, 231, \ 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, \ 242, 243, 243, 243, 244, 245, 246, 247, 248, 249, \ 250, 251, 252, 253, 254, 254, 255, 256, 257, 258, \ 258, 259, 260, 261, 261, 261, 261, 262, 263, 264, \ 264, 265, 266, 267, 268, 269, 270, 271, 272, 273, \ 274, 275, 276, 277, 278, 279, 280, 280, 281, 282, \ 283, 283, 284, 285, 286, 287, 288, 289, 290, 291, \ 292, 293, 294, 295, 296, 297, 298, 299, 300, 301, \ 302, 303, 304, 305, 306, 307, 307, 307, 307, 308, \ 309, 310, 311, 312, 313, 313, 313, 314, 315, 316, \ 316 ] ) v = np.ones ( 431 ) # # Shift from one-based to zero-based indexing. # i = i - 1 j = j - 1 return i, j, v def moler_st ( ): #*****************************************************************************80 # ## moler_st() returns the moler web matrix in sparse triplet form. # # Discussion: # # 6 nodes, 10 links. # # This matrix appears on page 5 of the reference. # # A self-link was added for node 5, which otherwise has no outlinks. # # Licensing: # # This code is distributed under the MIT license. # # Modified: # # 27 September 2022 # # Author: # # John Burkardt # # Reference: # # Cleve Moler, # Experiments with Matlab, # Chapter 7: Google PageRank, # https://www.mathworks.com/moler/exm/chapters/pagerank.pdf # # Output: # # integer i(10), j(10), v(10): the sparse triplet information. # import numpy as np i = np.array ( [ 1, 1, 2, 2, 3, 3, 3, 4, 5, 6 ] ) j = np.array ( [ 2, 6, 3, 4, 4, 5, 6, 1, 5, 1 ] ) v = np.ones ( 10 ) # # Shift from one-based to zero-based indexing. # i = i - 1 j = j - 1 return i, j, v def power_rank ( A ): #*****************************************************************************80 # ## power_rank() uses the power method to seek an eigenvector of a directed graph. # # Licensing: # # This code is distributed under the MIT license. # # Modified: # # 27 September 2022 # # Author: # # John Burkardt # # Input: # # integer A(N,N): the incidence matrix. # import numpy as np print ( '' ) print ( 'power_rank():' ) print ( ' Given an NxN incidence matrix A,' ) print ( ' compute the transition matrix T,' ) print ( ' Then start with a vector of N values 1/N,' ) print ( ' and repeatedly compute x <= T*x' ) print ( '' ) print ( ' After many steps, compare last three iterates.' ) print ( ' If they are close, we are probably at an eigenvector' ) print ( ' associated with the eigenvalue 1.' ) n = A.shape[0] # # Compute the transition matrix. # T = incidence_to_transition ( A ) # # Carry out many iterations. # Normalization is not necessary because T is a transition matrix. # it_num = 100 for i in range ( 0, it_num + 1 ): if ( i == 0 ): x = np.ones ( n ) / n else: x = np.matmul ( T, x ) # # Compare three successive iterates. # Tx = np.matmul ( T, x ) TTx = np.matmul ( T, Tx ) Output = np.column_stack ( [ x, Tx, TTx ] ) print ( '' ) print ( ' x, T*x, T*T*x' ) print ( Output ) return def sauer_st ( ): #*****************************************************************************80 # ## sauer_st() returns the sauer web matrix in sparse triplet form. # # Discussion: # # 15 nodes, 34 links. # # This matrix appears on page 564 of the reference. # # Licensing: # # This code is distributed under the MIT license. # # Modified: # # 27 September 2022 # # Author: # # John Burkardt # # Reference: # # Timothy Sauer, # Numerical Analysis, # Pearson, 2006, # ISBN: 0-321-26898-9, # LC: QA297.S348 # # Output: # # integer i(34), j(34), v(34): the sparse triplet information. # import numpy as np i = np.array ( [ \ 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, \ 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, \ 9, 10, 11, 12, 12, 12, 13, 13, 14, 14, \ 14, 14, 15, 15 ] ) j = np.array ( [ \ 2, 9, 3, 5, 7, 2, 6, 8, 3, 12, \ 1, 10, 10, 11, 10, 11, 4, 11, 5, 6, \ 10, 13, 15, 7, 8, 11, 9, 14, 10, 11, \ 13, 15, 12, 14 ] ) v = np.ones ( 34 ) # # Shift from one-based to zero-based indexing. # i = i - 1 j = j - 1 return i, j, v def six_st ( ): #*****************************************************************************80 # ## six_st() returns the six node matrix in sparse triplet format. # # Discussion: # # 6 nodes, 9 links. # # Licensing: # # This code is distributed under the MIT license. # # Modified: # # 27 September 2022 # # Author: # # John Burkardt # # Output: # # integer i(9), j(9), v(9), the sparse triplet information. # import numpy as np i = np.array ( [ 1, 2, 2, 3, 3, 4, 5, 5, 6 ] ) j = np.array ( [ 2, 3, 5, 1, 4, 1, 2, 6, 4 ] ) v = np.ones ( 9 ) # # Shift from one-based to zero-based indexing. # i = i - 1 j = j - 1 return i, j, v def small_st ( ): #*****************************************************************************80 # ## small_st() returns the small web matrix in sparse triplet form. # # Discussion: # # 93 nodes, 196 links. # # Licensing: # # This code is distributed under the MIT license. # # Modified: # # 27 September 2022 # # Author: # # John Burkardt # # Output: # # integer i(196), j(196), v(196): the sparse triplet information. # import numpy as np i = np.array ( [ \ 25, 31, 6, 5, 16, 23, 24, 29, 30, 35, \ 3, 10, 11, 12, 14, 19, 30, 33, 35, 38, \ 2, 7, 10, 27, 32, 39, 6, 2, 9, 11, \ 18, 20, 21, 22, 35, 38, 39, 8, 18, 27, \ 39, 12, 5, 10, 1, 8, 17, 26, 29, 34, \ 5, 33, 30, 2, 8, 9, 11, 20, 22, 24, \ 27, 18, 32, 26, 2, 3, 4, 6, 9, 10, \ 12, 14, 16, 18, 20, 22, 27, 28, 32, 33, \ 37, 38, 1, 31, 36, 2, 6, 9, 18, 22, \ 24, 33, 34, 3, 16, 30, 3, 5, 16, 19, \ 24, 29, 14, 20, 26, 27, 35, 36, 11, 14, \ 34, 39, 26, 13, 28, 8, 13, 17, 23, 28, \ 22, 19, 4, 21, 14, 28, 34, 10, 12, 33, \ 38, 15, 24, 32, 37, 35, 36, 39, 17, 34, \ 1, 25, 31, 15, 4, 4, 7, 7, 13, 25, \ 20, 37, 7, 21, 21, 26, 36, 23, 13, 29, \ 12, 38, 4, 8, 17, 3, 5, 9, 15, 16, \ 21, 23, 29, 30, 37, 15, 7, 11, 25, 1, \ 25, 6, 23, 17, 19, 19, 31, 1, 15, 31, \ 13, 37, 28, 32, 36, 95 ] ) j = np.array ( [ \ 1, 1, 2, 3, 3, 3, 3, 3, 3, 3, \ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, \ 6, 6, 6, 6, 6, 6, 7, 8, 8, 8, \ 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, \ 9, 10, 12, 12, 13, 13, 13, 13, 13, 13, \ 14, 14, 16, 18, 18, 18, 18, 18, 18, 18, \ 18, 22, 22, 23, 24, 24, 24, 24, 24, 24, \ 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, \ 24, 24, 25, 25, 26, 27, 27, 27, 27, 27, \ 27, 27, 27, 29, 29, 29, 30, 30, 30, 30, \ 30, 30, 33, 34, 34, 34, 34, 34, 35, 35, \ 35, 35, 36, 40, 41, 42, 42, 42, 43, 44, \ 45, 46, 47, 47, 48, 49, 50, 51, 51, 51, \ 51, 52, 53, 53, 53, 54, 54, 54, 55, 56, \ 57, 57, 57, 58, 59, 60, 61, 62, 63, 64, \ 65, 65, 66, 67, 68, 69, 70, 71, 72, 72, \ 73, 73, 74, 75, 75, 76, 76, 76, 76, 76, \ 76, 76, 76, 76, 76, 77, 78, 79, 80, 81, \ 81, 82, 83, 84, 85, 86, 87, 88, 88, 88, \ 89, 90, 91, 92, 93, 95 ] ) v = np.array ( [ \ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, \ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, \ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, \ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, \ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, \ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, \ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, \ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, \ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, \ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, \ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, \ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, \ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, \ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, \ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, \ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, \ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, \ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, \ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, \ 1, 1, 1, 1, 1, 0 ] ) # # Shift from one-based to zero-based indexing. # i = i - 1 j = j - 1 return i, j, v def timestamp ( ): #*****************************************************************************80 # ## timestamp() prints the date as a timestamp. # # Licensing: # # This code is distributed under the MIT license. # # Modified: # # 21 August 2019 # # Author: # # John Burkardt # import time t = time.time ( ) print ( time.ctime ( t ) ) return def tiny_st ( ): #*****************************************************************************80 # ## tiny_st() returns the tiny web matrix in sparse triplet form. # # Discussion: # # 5 nodes, 8 links. # # Licensing: # # This code is distributed under the MIT license. # # Modified: # # 27 September 2022 # # Author: # # John Burkardt # # Output: # # integer i(8), j(8), v(8): the sparse triplet information. # import numpy as np i = np.array ( [ 2, 2, 3, 4, 4, 4, 5, 5 ] ) j = np.array ( [ 1, 3, 4, 1, 2, 3, 4, 5 ] ) v = np.array ( [ 1, 1, 1, 1, 1, 1, 1, 0 ] ) # # Shift from one-based to zero-based indexing. # i = i - 1 j = j - 1 return i, j, v if ( __name__ == "__main__" ): timestamp ( ) web_matrix_test ( ) timestamp ( )