数列を有理式にする

数列と形式的べき級数は対応し、それぞれの世界での畳み込みと掛け算が対応する

数列の畳み込みは簡単に実験できる(np.convolve)

適当な畳み込みを繰り返して数列をシンプルな形にできれば、無限の項がある形式的べき級数を、有限の項の有理式にできる

有理式のN次の項はO(log N)で求められる

つまり数列の第N項がO(log N)で求められる see Two Snuke#5f0afb00aff09e00009b591e

https://gyazo.com/2060b6bfdb5a263b0096e09cd076395f

code:python

In 43: xs

Out43:

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

code:python

In 44: import numpy as np

In 45: from functools import reduce

In 48: reduce(np.convolve, 1, -1 * 1, xs):10

In 49: reduce(np.convolve, 1, -1 * 2, xs):10

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

code:python

In 53: reduce(np.convolve, 1, -1 * 2 + 1, 0, -1, 1)