数列を有理式にする

NISHIO Hirokazu [Translate]

数列を有理式にする
数列と形式的べき級数は対応し、それぞれの世界での畳み込みと掛け算が対応する
数列の畳み込みは簡単に実験できる(np.convolve)
適当な畳み込みを繰り返して数列をシンプルな形にできれば、無限の項がある形式的べき級数を、有限の項の有理式にできる
有理式のN次の項はO(log N)で求められる
つまり数列の第N項がO(log N)で求められる see Two Snuke#5f0afb00aff09e00009b591e



pythonIn [43]: xs
Out[43]: 
array([   0,    1,    2,    4,    6,    9,   12,   16,   20,   25,   30,
         36,   42,   49,   56,   64,   72,   81,   90,  100,  110,  121,
        132,  144,  156,  169,  182,  196,  210,  225,  240,  256,  272,
        289,  306,  324,  342,  361,  380,  400,  420,  441,  462,  484,
        506,  529,  552,  576,  600,  625,  650,  676,  702,  729,  756,
        784,  812,  841,  870,  900,  930,  961,  992, 1024, 1056, 1089,
       1122, 1156, 1190, 1225, 1260, 1296, 1332, 1369, 1406, 1444, 1482,
       1521, 1560, 1600, 1640, 1681, 1722, 1764, 1806, 1849, 1892, 1936,
       1980, 2025, 2070, 2116, 2162, 2209, 2256, 2304, 2352, 2401, 2450,
       2500])

pythonIn [44]: import numpy as np
In [45]: from functools import reduce

In [48]: reduce(np.convolve, [[1, -1]] * 1, xs)[:10]
Out[48]: array([0, 1, 1, 2, 2, 3, 3, 4, 4, 5])

In [49]: reduce(np.convolve, [[1, -1]] * 2, xs)[:10]
Out[49]: array([0, 1, 0, 1, 0, 1, 0, 1, 0, 1])

In [52]: reduce(np.convolve, [[1, -1]] * 2 + [[1, 0, -1]], xs)[:10]
Out[52]: array([0, 1, 0, 0, 0, 0, 0, 0, 0, 0])

pythonIn [53]: reduce(np.convolve, [[1, -1]] * 2 + [[1, 0, -1]], [1])
Out[53]: array([ 1, -2,  0,  2, -1])

"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]

(C)NISHIO Hirokazu / Converted from [Scrapbox] at 11/23/2025, 5:15:52 PM[Edit]

Related Pages