Какие существуют алгоритмы для нахождения функции закрытой формы по целочисленной последовательности? - PullRequest
Новая
       41

Какие существуют алгоритмы для нахождения функции закрытой формы по целочисленной последовательности?

6 голосов
/ 25 июня 2009

Я ищу программный способ взять целочисленную последовательность и выплюнуть функцию закрытой формы. Что-то вроде:

Дано: 1,3,6,10,15

Возврат: n (n + 1) / 2

Образцы могут быть полезны; язык не важен.

Ответы [ 7 ]

17 голосов
/ 25 июня 2009

Это касается чрезвычайно глубокой, сложной и активной области математики. Решение чертовски почти тривиально в некоторых случаях (линейные рецидивы), а чертовски почти невозможно в других (подумайте 2, 3, 5, 7, 11, 13, ....). Вы можете начать с рассмотрения генерации функций , например, и глядя на невероятную книгу Херба Уилфа (см. Стр. 1 (2e)) по этому вопросу, но это только покажет вам.

Но я думаю, что вам лучше всего сдаться, запросить у Слоана всестороннюю Энциклопедию целочисленных последовательностей , когда вам нужно узнать ответ, и вместо этого потратить время на чтение мнений из одна из самых эксцентричных личностей в этом глубоком предмете.

Любой, кто говорит вам, что эта проблема разрешима, продает вам змеиное масло (см. Стр. 118 книги Уилфа (2e).)

10 голосов
/ 25 июня 2009

В общем случае одна функция отсутствует.

Для указанной вами последовательности, Онлайн-энциклопедия целочисленных последовательностей находит 133 совпадений в своей базе данных интересных целочисленных последовательностей. Я скопировал первые 5 здесь.

A000217 Треугольные числа: a (n) = C (n + 1,2) = n (n + 1) / 2 = 0 + 1 + 2 + ... + n.
0, 1, 3, 6, 10, 15 , 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210, 231, 253, 276, 300, 325, 351, 378, 406, 435, 465, 496, 528, 561, 595, 630, 666, 703, 741, 780, 820, 861, 903, 946, 990, 1035, 1081, 1128, 1176, 1225, 1275, 1326, 1378, 1431

A130484 Сумма {0 <= k <= n, k mod 6} (Частичные суммы <a href="http://oeis.org/A010875" rel="nofollow noreferrer"> A010875 ).
0, 1, 3, 6, 10, 15 , 15, 16, 18, 21, 25, 30, 30, 31, 33, 36, 40, 45, 45, 46, 48, 51, 55, 60, 60, 61, 63, 66, 70, 75, 75, 76, 78, 81, 85, 90, 90, 91, 93, 96, 100, 105, 105, 106, 108, 111, 115, 120, 120, 121, 123, 126, 130, 135, 135, 136, 138, 141, 145, 150, 150, 151, 153

A130485 Сумма {0 <= k <= n, k mod 7} (Частичные суммы <a href="http://oeis.org/A010876" rel="nofollow noreferrer"> A010876 ).
0, 1, 3, 6, 10, 15 , 21, 21, 22, 24, 27, 31, 36, 42, 42, 43, 45, 48, 52, 57, 63, 63, 64, 66, 69, 73, 78, 84, 84, 85, 87, 90, 94, 99, 105, 105, 106, 108, 111, 115, 120, 126, 126, 127, 129, 132, 136, 141, 147, 147, 148, 150, 153, 157, 162, 168, 168, 169, 171, 174, 178, 183

A104619 Запишите натуральные числа в базе 16 в треугольнике с k цифрами в k-й строке, как показано ниже. Последовательность дает начальную диагональ.
1, 3, 6, 10, 15 , 2, 1, 1, 14, 3, 2, 2, 5, 12, 4, 4, 4, 13, 6, 7, 11, 6, 9, 9, 10, 7, 12, 13, 1, 0, 1, 10, 5, 1, 12, 8, 1, 1, 14, 1, 9, 7, 1, 4, 3, 1, 2, 2, 1, 3, 4, 2, 7, 9, 2, 14, 1, 2, 8, 12, 2, 5, 10, 3, 5, 11, 3, 8, 15, 3, 14, 6, 3, 7, 0, 4, 3, 13, 4, 2, 13, 4, 4, 0, 5, 9, 6, 5, 1, 15, 5, 12, 11, 6

A037123 a (n) = a (n-1) + Сумма цифр n.
0, 1, 3, 6, 10, 15 , 21, 28, 36, 45, 46, 48, 51, 55, 60, 66, 73, 81, 90, 100, 102, 105, 109, 114, 120, 127, 135, 144, 154, 165, 168, 172, 177, 183, 190, 198, 207, 217, 228, 240, 244, 249, 255, 262, 270, 279, 289, 300, 312, 325, 330, 336, 343, 351, 360, 370, 381

Если вы ограничиваете себя полиномиальными функциями, это легко закодировать, а ручное решение лишь слегка утомительно.

Пусть f(x)=a_0+a_1x+a_2x^2+\cdots+a_{n-1}x^{n-1}+a_nx^n, для какого-то неизвестного a_0\ldots a_n

Теперь решите уравнения
y_0=f(0)=a_0
y_1=f(1)=a_0+a_1+a_2+\cdots+a_{n-1}+a_n
y_2=f(2)=a_0+2a_1+4a_2+\cdots+2^{n-1}a_{n-1}+2^na_n
& Hellip;
y_n=f(n)=a_0+na_1+n^2a_2+\cdots+n^{n-1}a_{n-1}+n^na_n
которая просто система линейных уравнений.

3 голосов
/ 25 июня 2009

Если ваши данные гарантированно будут выражены в виде полинома, я думаю, вы сможете использовать R (или любой набор, который предлагает регрессионную подгонку данных). Если ваша корреляция ровно 1, то линия идеально подходит для описания серии.

Существует множество статистических данных, которые входят в регрессионный анализ, и я недостаточно знаком даже с основами расчета, чтобы дать вам более подробную информацию.

Но, эта ссылка на регрессионный анализ в R может быть полезной

2 голосов
/ 26 июня 2009

Для этой цели в систему компьютерной алгебры Axiom входит пакет. Вы можете прочитать документацию здесь .

Вот вывод для вашего примера последовательности в FriCAS (форк аксиомы): 

(3) -> guess([1, 3, 6, 10, 15])

                 2
                n  + 3n + 2
(3)  [[function= -----------,order= 0]]
                     2
Type: List(Record(function: Expression(Integer),order: NonNegativeInteger))
1 голос
/ 25 июня 2009

Если ваша последовательность получена из полинома, то разделенные различия найдут этот полином, выраженный в терминах базиса Ньютона или биномиального базиса. Смотрите это .

1 голос
/ 25 июня 2009

Я думаю, что ваша проблема некорректна. Дано любое конечное число целых в последовательности с нет генерирующей функции, следующий элемент может быть чем угодно.

Вы должны предположить что-то о последовательности. Это геометрическое? Арифметика

0 голосов
/ 02 ноября 2015

нет общих ответов; простой метод может быть реализован с использованием аппроксимаций Паде ; в двух словах, предположим, что ваша последовательность представляет собой последовательность коэффициентов разложения Тейлора неизвестной функции, затем примените алгоритм (аналогичный алгоритму с непрерывной дробью), чтобы «упростить» это разложение Тейлора (точнее: найти рациональная функция, очень близкая к исходной (и усеченной) функции. Программа Maxima может сделать это: посмотрите на «pade» на странице: http://maxima.sourceforge.net/docs/manual/maxima_28.html

В другом ответе рассказывается о пакете «угадай» в форке FriCAS Axiom (см. Предыдущий ответ от jmbr). Если я не ошибаюсь; этот пакет сам вдохновлен программой Rate Кристианом Краттхалером; Вы можете найти его здесь: http://www.mat.univie.ac.at/~kratt/rate/rate.html Может быть, если посмотреть на его источник, вы могли бы рассказать о других методах.

...