Around Euler's theorem on sums of divisors.pdf В настоящее время развивается экспериментальная математика: открытие новых математических закономерностей путем компьютерной обработки большого числа примеров. Такой подход не столь убедителен, как короткое доказательство, но может быть убедительнее длинного сложного доказательства и в некоторых случаях вполне приемлем. В прошлом данную концепцию отстаивали и Дьёрдь Пойа [1, 2], и Лакатос [3], убежденные сторонники эвристических методов и квазиэмпирической природы математики. Экспериментальной математики посвящены книги [4, 5]. Методы экспериментальной математики в естественно-научных дисциплинах, в первую очередь в физике, применяются и обосновываются в книге «Новый вид науки» Стивена Вольфрама [6]. Компьютеры иногда позволяют получить неформальные аргументы в пользу того или иного предположения, а иногда, наоборот, опровергнуть казавшиеся правдоподобными гипотезы. Компьютерные вычисления также поставляют первичную информацию, позволяющую обнаруживать новые свойства изучаемых объектов и выдвинуть новые гипотезы. Mathematica - одна из популярных систем компьютерной алгебры; используемый язык программирования носит название Wolfram [7, 8]. Применение Mathematica позволяет эффективно вычислять математические объекты, что проливает свет на используемые математические понятия. Причем использование Mathematica не требует глубоких знаний программирования. Теория формальных рядов в полной общности описана в [9, с. 64-81]. Частный случай - множество формальных степенных рядов. Формальным степенным рядом (от одной переменной) называется формальное выражение вида ад X akxk = a0 + ajx + a2x2 +..., к=0 где коэффициенты ak принадлежат числовому кольцу или полю R. Переменная x является формальной, и нас не интересует сходимость такого ряда. Вполне возможно, что, только подставив x = 0, в результате получим некоторое число. Множество формальных степенных рядов, определяемое числовым кольцом или полем R, будем обозначать как ад R[[x]] = (X akxk\ak e R}. к=0 Формальные степенные ряды являются обобщением многочленов от одной переменной, и поэтому в степенном ряду может быть и конечное число членов, т.е. только конечное число коэффициентов ak Ф 0. И так же как и для многочленов, можно ввести на множестве R[[x]] алгебраическую структуру коммутативного кольца с единицей. Определим операции сложения и умножения формальных степенных рядов посредством равенств ад ад ад X akxk + X bkxk = X (ak + Ьк) xk, к=0 к =0 к=0 ад ад ад к (X akx)(X ) = X ^, где ск = X aibк-tx'. к=0 к=0 к=0 i=0 Таким образом, чтобы найти коэффициент cn при xn в произведении двух рядов, нам не надо рассматривать эти ряды полностью, достаточно взять первые n + 1 членов в каждом из них. Во множестве R[[x]] роль нуля выполняет ряд, все коэффициенты которого равны нулю, а роль единицы - ряд, в котором первый коэффициент равен 1, а остальные равны 0. Известно, что множество R[[x]] с операциями сложения и умножения и элементами 0 и 1 является коммутативным кольцом, в котором элемент ад к Xa^ к=0 обратим тогда и только тогда, когда a0 Ф 0. ад Например, формальные степенные ряды 1 - x - x2 и X Fxk являются взаимно к=0 обратными F - к-е число Фибоначчи; F0 = Fj = 1, а для к > 1 имеем F^ = F^ + + F^). Действительно, имеем ад (1 - x - x2) X Fkx'c = (1 - x - x2 )(F0 + F x + F2 x2 +...) = к=0 = Fi + (F - F0) x+(F2 - F + F0) x2 +.... В силу начальных условий и рекуррентного соотношения для чисел Фибоначчи полученный ряд равен 1. В книге [10, с. 353-417] описана теория производящих функций и множество примеров применения. По-видимому, все, что алго-ритмизуемо в теории производящих функций, в частности разнообразные приемы преобразований производящих функций из указанной книги, реализовано в языке Wolfram. Определение производящей функции. Пусть а0, аь а2, ... - произвольная бесконечная последовательность чисел (они могут быть натуральными, целыми, рациональными, вещественными или комплексными). Производящей функцией для этой последовательности будем называть формальный степенной ряд X k аkx k=0 Производящая функция определяется и для конечной последовательности а0, аь а2, ..., ап. В этом случае в формальном степенном ряду все коэффициенты, начиная с ап + 1, полагают равным нулю. Ранее мы получили равенство 1 ад -Ч = X Fkxk. 1 _ x _ x k=0 Каков его смысл? Например, бессмысленно подставлять в него x = 1. Дело в том, что выражения ■] ад 1 2 и X Fkxk 1 _ x _ x k=0 равны как элементы кольца формальных степенных рядов. И в соответствии с предыдущим определением производящая функция последовательности чисел Фибоначчи 1, 1, 2, 3, 5, 8, 13, 21, ... представляется как в виде формального степенного ряда, так и в виде функции 1/(1 - x - x2). Про последнее выражение говорят, что оно является производящей функцией, записанной в «замкнутой форме» (содержит только элементарные функции и не содержит бесконечные суммы). Теория производящих функций дает аппарат для создания производящих функций в замкнутой форме для различных последовательностей. И возможно, поэтому производящие функции находят разнообразные применения, в первую очередь в комбинаторике и теории чисел. Ранее было дано определение последовательности Фибоначчи, и для этой последовательности была найдена производящая функция. Но числа последовательности Фибоначчи в языке Wolfram нумеруются другим образом (здесь и далее символ предшествует вычисляемому выражению, а на следующей строке показано полученное значение): ^ Fibonacci[Range[0, 10]] {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55} В соответствии с этим определением требуется заново найти производящую функцию в замкнутой форме для последовательности Фибоначчи. Воспользуемся полученным ранее равенством: 1 = 1x0 + be1 + 2x2 + 3x3 + 5x4 +.... 1 _ x _ x2 Умножая обе части на x, получаем " . = 0 x0 + 1x1 + 1x2 + 2 x3 + 3x4 + 5 x5 +.... 1 _ x _ x2 Таким образом, последовательность {Fibonacci[n] | n = 0, 1, 2, ...} имеет производящую функцию x/(1 - x - x2). В языке Wolfram имеется возможность для последовательности (в общем случае бесконечной) получить производящую функцию в замкнутом виде. Основная функция для этой цели GeneratingFunction[expr, n, x], где выражение expr представляет n-й член последовательности. Найдем производящую функцию для последовательности Фибоначчи: ^ GeneratingFunction[Fibonacci[n], n, x] x -1 + x + x2 Функция Seriesf ,{x, x0, n}] языка Wolfram создает конечный степенной ряд n (^ \к Yf(')(xo)k=0 k! где f(k)(x0) - значение k-й производной функции f в точке x0. Когда f является производящей функцией последовательности, то Series обычно вызывается в виде Seriesf ,{x, 0, n}]. Например, для производящей функции последовательности Фибоначчи получаем -1 + x + x2 ,{x,0,10} Series x + x2 + 2x3 + 3x4 + 5x5+ 8x6 +13x7 +21x8 + 34x9 + 55x10 + O[x]11 Функция SeriesCoefficient^eries, n] извлекает коэффициент при степени n из степенного ряда, созданного функцией Series: x ,{x,0,10} ■ f 10 = Series _ -1 + x + x2 ^ SeriesCoefficient[f10, 10] 55 Список всех коэффициентов из нужного диапазона можно получить следующим образом: ^ SeriesCoefficient[f10, #]& /@ Range[0, 10] {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55} 2. Разбиения Разбиением натурального числа n называется всякая невозрастающая последовательность натуральных чисел Х1, Х2, Х3, ..., Xm, для которых m Y^- = n. i =1 Пусть pn обозначает число разбиений для неотрицательного целого числа n (условимся считать, что p0 = 1), тогда последовательность p0,p1, p2, ... начинается с чисел 1, 1, 2, 3, 5, 7, 11, 15, ... . Достаточно просто найти производящую функцию для последовательности pn [11, с. 88]. Теорема 1 (Эйлер). Производящая функция для числа разбиения числа n имеет вид '(х)=1/ пда=0 (1 - xn+1). В языке Wolfram имеется функция PartitionsP для вычисления значений последовательности pn: ^ PartitionsP/@Range[0,10] {1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42} Mathematica знает, чему равна производящая функция для последовательности pn , и выдает ее в «замкнутом» виде: ^ GeneratingFunction[PartitionsP[n], n, х] _1_ QPochhammer [ х, х ] Функция QPochhammer[a, q] дает значение «q-символа Похгаммера» (a;q)M, который определяется как да (a; q )да=П(1 - aqk ). k=0 Этот символ был введен вскоре после обычных гипергеометрических функций; q-функции долгое время изучались как теоретические обобщения гипергеометрических и других функций. Язык Wolfram впервые дает возможность полностью вычислить числовые q-функции и также совершить символьные преобразования с ними, что позволяет использовать q-функции в замкнутом виде для сумм, произведений, решений рекуррентных уравнений и т. д. [12]. Можно получить q-символ Похгаммера при упрощении формального произведения со П(1 - х^1) Simplify n=0 QPochhammer[x, х] Можно явно получить конечный степенной ряд, коэффициенты которого являются начальными элементами последовательности p0, pi, p2, ...: ^ Series -1---т,(х,0,9} _ QPochhammer [ х, х] 1 + х + 2х2 + 3х3 +5х4 +7х5 + 11х6 + 15х7 +22 х8 + 30х9 + O[x]10 3. Последовательность с производящей функцией QPochhammer[x, x] Изучим сейчас последовательность a0, a1, a2, ..., для которой производящей функцией является QPochhammer[x, х]. Посмотрим на первые члены этой последовательности: ^ SeriesCoefficient[QPochhammer[x, х], {х, 0, #}]& /@ Range[0, 51] {1, -1, -1, 0, 0, 1, 0, 1, 0, 0, 0, 0, -1, 0, 0, -1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1} Впервые эту последовательность получил Эйлер [10, с. 117, 118], который вручную находил коэффициенты формального степенного ряда, получаемого в результате бесконечного произведения (1 - x)(1 - x2)(1 - x3) (1 - x4)(1 - x5) .... Сейчас это можно сделать быстрее: да П(1 - xn ),{x,0,51} ■ Series 1 - x - x2 + x5 + x7 - x12 - x15 + x22 + x26 - x35 - x40 + x51 + O[x]52 Рассмотрение последнего ряда привело Эйлера к гипотезе, которая сейчас известна как Теорема 2 (пентагональная теорема Эйлера). да да П(1 -xn) = 1 + X (-1)m(xm(3m-1)/2 + xm(3m+1)/2). n=1 m=1 Доказательство смотрите, например, в [13, с. 26; 11, с. 91, 92]. Найдем формулу для последовательности a0, a1, a2, ...в замкнутом виде. Если n = m(3m + 1)/2, то выразим m через n: -(-1 -V1 + 24n) иm = -(-1W1 + 24n). m = - -1 -■> 6V > 6' Таким образом, если 1 + 24n - точный квадрат, то an = ± 1, иначе an = 0. Отсюда получаем (при m = у/1 + 24n ) равенство (-1)(-m-1)/6, если m - целое и (-m- 1)mod6 = 0; (-1)(-m-1)/6, если m - целое и (m- 1)mod6 = 0; 0, в других случаях. a„ = Определим функцию произвольного натурального m: (-1)(m+1)/6, если m mod6 = 5; a(m) = i (-1)(m-1)/6, если m mod6 = 1; 0, иначе. Если m = V 1 + 24n - целое число, то an = a(m). Так как элементы последовательности a0, a1, a2, . являются только ±1 или 0, то естественно предположить, что они суть значения некоторого символа Якоби для m. Для нечетных m в качестве простейших кандидатов можно взять (mm) или (-3). Проверка показывает, что (mm) Ф a(m) в общем случае даже для нечетного m. Но следующая проверка подтверждает предположение (m) = a(m) для первой тысячи нечетных натуральных чисел: ^ AllTrue[(JacobiSymbol[3, #] == Piecewise[{{(-1)A((# + 1)/6), Mod[#, 6] == 5}, {(-1)Л((# - 1)/6), Mod[#, 6] == 1}}, 0])& /@ Select[Range[1000], OddQ], #&] True Лемма. Для нечетных натуральных m выполнено равенство a(m) = (-3). Доказательство. Если m не кратно 3, то по квадратичному закону взаимности и по критерию Эйлера квадратичного вычета по простому модулю имеем (^(^(-Ц^1^ =(ж)(-1)(m-i)/2 - m(3-1)/2(-1)(m-1)/2 -m(-1)(m-1)/2(mod3). Далее разберем два случая для m. 1. m = 6k + 5 (k - целое). В этом случае (m - 1)/2 = 3k + 2 и поэтому (m)- (6k + 5)(-1)3k+2 - (-1)3k+3(mod3). Величина (-1)3k+3 для четного k равна -1, а для нечетного k получаем 1. Теперь найдем значения a(6k + 5) для четного и нечетного k по отдельности. Если k = 2t (t - целое), то имеем a(6(2t) + 5) = (-1)(12t+5+1)/6 = -1. Если k = 2t + 1, то a(6(2t + 1) + +5) = (-1)(12t+11+1)/6 = 1. Независимо от четности k имеем ("gk3+J) = a(6k + 5). 2. m = 6k + 1 (k - целое). В этом случае (m - 1)/2 = 3k и поэтому (m)- (6k +1)(-1)3k - (-1)3k (mod3). Величина (- 1)3k для четного k равна 1, а для нечетного k получаем -1. Теперь найдем значения a(6k + 1) для четного и нечетного k по отдельности. Если k = 2t (t - целое), то имеем a(6(2t) + 1) = (-1)(12t)/6 = 1. Если k = 2t + 1, то a(6(2t + 1)+1) = = (-l)(12t+7-1)/6 = -1. Независимо от четности k имеем (-^k^) = a (6k +1). Осталось рассмотреть ситуацию, когда m кратно 3. Но в этом случае (-3) = 0 = a(m) по определению. ■ Теорема 3 (формула для последовательности a0, a1, a2, .в замкнутом виде). Для целого n > 0 положим m = л/1 + 24n. Тогда элементы последовательности a0, a1, a2, ... можно вычислить по правилу 3 то a -' - |(-), если m - целое число; ^ ч an = Л ' (1) [0, иначе. Доказательство. Из леммы следует, что если m - нечетное целое число, = ( -3). V m / Желательно было бы иметь такое x, чтобы an =( m) для всех натуральных m. Для этого достаточно взять x = 12, тогда (m ) = (m )2 (m) и (1) справедливо, так как для нечетных m символ Якоби (-^) = ±1, а для четных m выполнено (-) = 0. ■ m 4. Последовательность 1, 2, 5, 7, 12, 15, 22, 26, 35, 40, 51, ... Эйлер также рассматривал последовательность {bn | n = 0, 1, 2, .}: 1, 2, 5, 7, 12, 15, 22, 26, 35, 40, 51, ... , (2) состоящую из положительных показателей степеней ненулевых членов ряда 1 - x - x2 + x5 + x7 - x12 - x15 + x22 + x26 - x35 - x40 + x51 + ... . Эта последовательность с добавленным числом 0 в качестве первого члена называется последовательностью обобщенных пятиугольных чисел. Эйлер экспериментально обнаружил закономерность в построении последовательности (2). Далее цитируем Эйлера по книге [1, с. 114, 115]. «Закон чисел 1, 2, 5, 7, 12, 15, ... станет ясен, если мы возьмем их разности: Числа: 1, 2, 5, 7, 12, 15, 22, 26, 35, 40, 51, 57, 70, 77, 92, 100, ... Разности: 1, 3, 2, 5, 3, 7, 4, 9, 5, 11, 6, 13, 7, 15, 8, ... В самом деле, мы имеем здесь поочередно все целые числа 1, 2, 3, 4, 5, 6, ... и нечетные числа и поэтому мы можем продолжать последовательность этих чисел сколь угодно далеко». Слова Эйлера подсказывают, что члены последовательности (2) удовлетворяют следующему правилу: (3) На языке Wolfram рекурсивная программа с запоминанием уже вычисленных промежуточных значений выглядит следующим образом ^ b[0] = 1; ^ b[n_?EvenQ] := b[n] = b[n - 1] + n + 1 ^ b[n_?OddQ] := b[n] = b[n - 1] + (n + 1)/2 Проверим ^ b /@ Range[0, 15] {1, 2, 5, 7, 12, 15, 22, 26, 35, 40, 51, 57, 70, 77, 92, 100} Найдем производящую функцию для последовательности bn. Простое применение функции GeneratingFunction к b[n] в системе Mathematica выдает результат невычисленным. Поэтому будем применять способ решения рекуррентных соотношений в четыре шага, изложенный в [10, c. 364-376]. Шаг 1 требует записать рекуррентное соотношение (3) в виде «одного уравнения» для последовательности bn, т.е. нужна формула, не содержащая конструкций с перечислением случаев. Искомое уравнение имеет вид bn = bn_i [n > 0] + (n + 1)/2 [n нечетно] + (n + 1)[n > 0 и n четно] + [n = 0]. (4) Запись с квадратными скобками широко используется в [7] в соответствии с правилом: Если S - некоторое утверждение, которое может быть истинно или ложно, квадратно-скобочное обозначение [S] означает 1, если S истинно, и 0 в противном случае. Поэтому в правой части (4) присутствует только 1, когда n = 0, а при n > 0 справа всегда присутствует bn - j и еще одно слагаемое (n + 1)/2 или (n + 1) в зависимости от четности числа n. На шаге 2 умножаем обе части уравнения на xn и просуммируем по всем n. В левой части получается сумма Xbnxn , которая равна производящей функции B(x), а правую часть следует преобразовать с тем, чтобы она превратилась в какое-то другое выражение, включающее B(x). Слагаемое bn - i [п > 0] преобразуется в XI=o bn+ixn+: = xB(x) = xB, слагаемое [n = 0] становится 1. Слагаемое (n + 1)/2 [n нечетно] преобразуется в хад=0((п +1)/2)xn [п нечетно]. Из ряда XI=0((n +1)/2)xn получаем с помощью Mathematica производящую функцию C1 в замкнутой форме: ^ C1 = GeneratingFunction[(n + 1)/2, n, x] 1 2 (_1 + x )2 Но в ряде Х;П=0((п +1)/2)xn должны присутствовать члены только с нечетными n. Есть общий метод извлечение членов с нечетными номерами {0, g1, 0, g3, 0, g5, 0, ...} из любой последовательности g0, g1, g2, g3, ... . Имеем V g x2n+1 = G(x) _ G(_x) Xg2n+1x = 2 , n=0 2 где G(x) - производящая функция последовательности g0, g1, g2, g3, ... . В соответствии с этим преобразуем второе слагаемое в (4): ^ Simplify[(C1 - (C1 /. x ^ -x)) / 2] x (_1 + x2)2 Третье слагаемое в (4) (n + 1)[n > 0 и n четно] преобразуем сначала в выражение XI=0(n +1)xn [n четно]. Из ряда X ^=0(n +1)xn получаем с помощью Mathematica производящую функцию C2 в замкнутой форме: ^ C2 = GeneratingFunction[n + 1, n, x] 1 (_1 + x )2 Также имеется общий метод извлечение членов с четными номерами {g0, 0, g2, 0, g4, 0, ...} из любой последовательности g0, g1, g2, g3, ... . Имеем V g x2n = G(x) + G(_x) Zug2nx - 2 . n=0 2 При извлечении из ряда членов с четными n, заметим, что поскольку член 1xx° не нужен, то нужно отнять 1: ^ Simplify[(C2 + (C2/. x ^ - x))/2] - 1 1 + x2 _1 + - (_1 + x2)2 Проверим, что действительно сейчас получили члены с ненулевыми четными степенями x: ^ Series[%, {x, 0, 10}] 3x2 + 5x4 +7x6 + 9x8 + 11x10 + O[x]11 Последнее слагаемое [n = 0] в (4) дает просто 1. Суммируя все полученные выражения в правой части (4), получаем уравнение для производящей функции B: 1 + x2 B = xB +- (-1 + x2 )2 (-1 + x2 ) Шаг 3. Решая уравнение, получаем для производящей функции B(x) выражение в замкнутом виде. Таким образом, выражение -1 - x - x B( x) =- (-1 + x)3 (1 + x)2 является производящей функцией в замкнутом виде для последовательности Эйлера 1, 2, 5, 7, 12, 15, 22, 26, 35, 40, 51, 57, 70, 77, 92, 100, ... . На последнем, четвертом шаге, имея производящую функцию, в языке Wolfram легко получить выражение bn в замкнутом виде: , {x,0, n} 1 + x + x2 SeriesCoefficient _ (-1 + x)3 (1 + x)2 | -(13 + 3(-1)n + 2(9 + (-1)n)n + 6n2) n > 0 16 [0 True Определим bn в замкнутом виде b [n _] := -(13 + 3 (-1)n + 2(9 + (-1)n )n + 6n2) (5) Вычислим 20 первых членов последовательности ^ b /@ Range[0, 19] {1, 2, 5, 7, 12, 15, 22, 26, 35, 40, 51, 57, 70, 77, 92, 100, 117, 126, 145, 155} 5. Гипотеза Эйлера о законе чисел, относящемся к суммам их делителей Эйлер путем индуктивных рассуждений обнаружил удивительную рекуррентную закономерность, связывающую суммы делителей натуральных чисел. Начальное представление об этой связи дает следующая формула (ст(п) обозначает сумму положительных делителей натурального числа n): CT(n) = CT(n - 1) + CT(n - 2) - CT(n - 5) - CT(n - 7) + ст(п - 12) + ст(п - 15) -- a(n - 22) - a(n - 26) + a(n - 35) + ст(п - 40) - ст(п - 51) - ст(п - 57) + (6) + a(n - 70) + a(n - 77) - a(n - 92) - ст(п - 100) + ... . Как точно выглядит это выражение и как Эйлер пришел к своей догадке, все это хорошо изложено в [1, c. 111-127]. Там же имеется и библиографическая ссылка на оригинал. Важно следующее: в этом выражении встречаются последовательности (1) и (2). Члены последовательности (2) вычитаются из n в аргументах функции ст. Коэффициенты, стоящие перед ст в правой части выражения (6), совпадают с ненулевыми членами последовательности (1), умноженными на -1. Получим гипотезу Эйлера, используя систему Mathematica. Возьмем конечный ряд из 51 члена формального степенного ряда для последовательности (1). Производящая функция для последовательности (1) есть QPochhammer[x, x]. ^ t1 = Series[QPochhammer[x, x], (x, 0, 50}] 1 - x - x2 + x5 + x7 - x12 - x15 + x22 + x26 - x35 - x40 + O[x]51 Продифференцируем этот ряд по х и результат умножим на -x: ^ t2 = -x D[Series[QPochhammer[x, x], (x, 0, 50}], x] x + 2x2 - 5x5 -7x1 + 12x12 + 15x15 - XXxxx - X6xx6 + 35x35 + 40x40 + O[x]51 Как видим, коэффициенты ряда t2 отличаются от соответствующих коэффициентов ряда t1 для члена xn множителем -п. Это сохраняется и для расмотренных больших п. Определим новую последовательность сп = - nan для всех п = 0, 1, 2, ... . Теперь найдем частное двух рядов t3 = t2/t1, заметим, что мы учитываем в примере только степени, не превосходящие 50: ^ t3 = t2/t1 x + 3x2 + 4x3 + 7x4 + 6x5 + 12x6 + 8x7 + 15x8 +13x9 + 18x10 + 12xn + X8xlx + + 14x13 + 24x14 + 24x15 + 31x16 + 18x17 + 39x18 + 20x19 + 42xx0 + 3Xxx1 + 36xxx + + 24x23 + 60x24 + 31x25 + 4XxX6 + 40x27 + 56x28 + 30x29 + 72x30 + 32x31 + 63x32 + + 48x33 + 54x34 + 48x35 + 91x36 + 38x37 + 60x38 + 56x39 + 90x40 + 42x41 + 96x42 + + 44x43 + 84x44 + 78x45 + 72x46 + 48x47 + + 124x48 + 57x49 + 93x50 + O[x]51 Создадим список коэффициентов ряда: ^ list = SeriesCoefficient[t3, #]& /@ Range[50] (1, 3, 4, 7, 6, 12, 8, 15, 13, 18, 12, 28, 14, 24, 24, 31, 18, 39, 20, 42, 32, 36, 24, 60, 31, 42, 40, 56, 30, 72, 32, 63, 48, 54, 48, 91, 38, 60, 56, 90, 42, 96, 44, 84, 78, 72, 48, 124, 57, 93} Проверим, что эти числа являются суммами делителей первых 50 натуральных чисел (DivisorSigma[1, x] - встроенная функция в языке Wolfram для вычисления a(x)): ^ AllTrue[(list[[#]] == DivisorSigma[1, #])& /@ Range[50], #&] True Дополнительные проверки для конечных рядов t1 и t2 с большим количеством членов также показали, что t3 = t2/t1 есть конечный степенной ряд для соответствующей конечной последовательности а(1), а(2), а(3), ..., ст(да). Можно предположить, что частное рядов t3 = t2/t1, при расширении t1 и t2 до бесконечных, является формальным степенным рядом для последовательности а(1), а(2), ст(3), ... . Если это так, то произведение формальных степенных рядов t3 и t1 дает формальный степенной ряд для последовательности с0, сь с2, ..., которая является сверткой [10, с. 225] последовательностей a0, ab a2, ..., и 0, a(1), a(2), a(3), . . Следовательно, для n = 1, 2, 3, . имеем формулу n Cn =X ^CT(n - к). к=0 Отсюда получаем гипотезу Эйлера n-1 a(n) = nan -X al:a(n - к). (7) к=1 В соответствии с теоремой 3 члены последовательности an могут быть вычислены на языке Wolfram с помощью следующей функции: ^ a[n_] := With[{m = Sqrt[24n + 1]}, If[IntegerQ[m], JacobiSymbol[12, m], 0]] Напишем программу для вычисления -Ё ^=1 aka(n - k) + ncn в символьном виде n-1 ^ s0 [n _]:=-^(a [k]a[n - k]) + na [n] k=1 Посмотрим, как выглядит правая часть (7) для n = 100: ^ s0[100] -100 - ст(8) + ст(23) + ст(30) - ст(43) - ст(49) + ст(60) + ст(65) - ст(74) - ст(78) + + ст(85) + ст(88) - ст(93) - ст(95) + ст(98) + ст(99) Теперь определим функцию для численного вычисления правой части в (7) и проверим выполнения равенства для n = 100: n-1 ^ s [n _ ]:= na [n] + ^a [k ] DivisorSigma [1, n - k ] k=1 ^ {DivisorSigma[1, 100], s[100]} {217, 217} И наконец, проверим выполнения равенства (7) для всех n < 10000: ^ AllTrue[(s[#] == DivisorSigma[1, #])& /@ Range[1000], #&] True Эйлер не смог доказать найденную им закономерность, она была доказана значительно позже. 6. Рекуррентная формула для числа разбиений Из теоремы 1 следует, что ад ад (Ё anxn)(Ё P(n) хП ) = 1, n=0 n=0 гдеp(n) - количество разбиений числа n; a0, ab a2, a3, ... - последовательность (1). Таким образом, произведение формальных степенных рядов дает единичный ряд, следовательно, свертка последовательностей p(0), p(1), p(2), ... и a0, ai, a2, a3, ... дает последовательность 1, 0, 0, 0, ... . Поэтому для n > 0 получаем n Ё ampn-m = m=0 Следовательно, pn =-Ё m=1 ampn-m. (8) Напишем программу для вычисления правой части (8) в символьном виде: (n-1 \ ^ w0[n _] := - Ёa[m] p [n - m] + a [n] V m=1 у Посмотрим, как выглядит правая часть (8) для n = 50 и n = 51: ^ w0[50] p[10] + p[15] -p[24] -p[28] + p[35] + p[38] -p[43] -p[48] + p[49] ^ w0[51] -1 + p[11] + p[16] -p[25] -p[29] + p[36] + p[39] -p[44] -p[46] + p[49] + p[50] Теперь определим функцию для численного вычисления правой части в (8) и проверим выполнения равенства (8) для n = 1000: (n-1 Л ^ w [n _] := - Ya[m]PartitionsP[n - m] + a [n] V m=1 у ^ {PartitionsP[1000], w[1000]} {24061467864032622473692149727991, 24061467864032622473692149727991} И наконец, проверим выполнения равенства (8) для всех n < 10000. ^ AllTrue[(w[#] == PartitionsP[#])& /@ Range[1000], #&] True Формула (8) представляет собой весьма эффективный алгоритм для вычисления p(n).

Скачать электронную версию публикации