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

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

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

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

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

 Brian25 июн. 2009 г., 03:56
Это может быть просто недостаток математических знаний, но эта проблема не кажется достаточно ограниченной.
 wkf25 июн. 2009 г., 04:33
Моей главной заботой было то, что я переосмыслил проблему, и что был какой-то хорошо известный способ решить эту проблему. Оказывается, дело не в этом, и на самом деле мне нужно гораздо больше обдумать, чем я уже вложи
 Sev25 июн. 2009 г., 04:30
Предлагать для границ: найти функцию закрытой формы, заданную ровно 10 целыми числами, если возможно, иначе вернуть ноль. К сожалению, что-то подобное значительно упрощает эту проблему. Настолько, что это становится почти бесполезным.

Ответы на вопрос(7)

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

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

 wkf25 июн. 2009 г., 04:18
Все виды последовательностей. Возможно, «последовательность» задается там, где нет генерирующей функции. Я бы тоже хотел иметь возможность заняться этим делом. Прямо сейчас я нахожусь на первом месте, поэтому, если вы думаете, что я должен каким-то образом пересмотреть вопрос, я был бы признателен за ваш вклад.

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

Решение Вопроса

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

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

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

 wkf25 июн. 2009 г., 04:25
Некоторые фантастические ссылки; именно то, что я искал. У меня было чувство, что ответ будет сложным. Я думаю, что, возможно, мне нужно больше знаний по предмету, прежде чем я могу задать правильные вопросы. Благодарность
 John D. Cook25 июн. 2009 г., 04:54
Возможно, вы захотите взглянуть на книгу «Конкретная математика». Вы можете найти его более доступным, чем книга Уилфа.
 ephemient25 июн. 2009 г., 04:43
Вау, я слишком долго писал свое решение. Ты побил меня на милю
 j_random_hacker26 июн. 2009 г., 13:24
Проблема с этим ответом состоит в том, что он неявно предполагает, что естьоди правильная функция, когда на самом деле существует бесконечное число функций замкнутой формы, которые проходят через любой указанный конечный набор точек - как всего 1 пример, многочлен степени n будет проходить через любые n + 1 заданных точек. Но большая проблема заключается в том, что нет способа выбрать, какая функция этих функций «лучшая». Зачем? Одна из причин в том, что следующий номер в последовательности может быть что угодно. Я жду, пока вы не упомянули об этом заранее.

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

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

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

 Bill Lynch25 июн. 2009 г., 04:07
Вы можете сформировать полином, взяв все заданные корни, скажем, a, b и c, и записать его в виде f (x) = (x-a) * (x-b) * (x-c). Но это не значит, что они не являются другими полиномами, которые бы его удовлетворяли.

оди функция в целом.

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

A000217 Треугольные числа: a (n) = C (n + 1,2) = n (n + 1) / 2 = 0 + 1 + 2 + ... + n.
0, 1, 3, 6, 10, 151, 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, 143

A130484 Sum {0 <= k <= n, k mod 6} (Частичные суммы 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, 15

A130485 Sum {0 <= k <= n, k mod 7} (Частичные суммы 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, 18

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

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

Позволять для неизвестного

Теперь решай уравнения





которая просто система линейных уравнений.

 ephemient25 июн. 2009 г., 22:57
Небольшая поправка: многочлен степени n всегда можно уместить в конечный набор из n + 1 точек.
 Martin Hock25 июн. 2009 г., 06:02
Вы привели пример алгоритма, а «правильный» ответ утверждал, что такого алгоритма не существует. Интересный. Ваш ответ предполагает, что последовательность конечна, что я считаю правильным предположением.
 Autoplectic25 июн. 2009 г., 09:08
@ Martin: ephemient четко заявил, что состояние решения ограничено полиномами степени n, которые всегда можно подогнать к конечному набору из n точек.
 j_random_hacker26 июн. 2009 г., 13:29
+ 1. Это должен быть правильный ответ IHMO. Самым важным моментом является то, что проблема крайне недооценена, и я думаю, что список из 5 различных вероятных функций для 1, 3, 6, 10, 15, который вы дали, демонстрирует это довольно хорошо.

жете читать документацию здесь.

Вот вывод для вашего примера последовательности в 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))

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

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

Ваш ответ на вопрос