Разложение специальных чисел

Еремин Геннадий
публикация 28 Sep 2015
редакция 17 Feb 2016

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

Известны работы по факторизации специальных чисел, например, классическое разложение чисел Ферма. Факторизуют числа Мерсенна и числа Фибоначчи. Разложению чисел Каталана посвящено не очень много работ, и здесь сошлемся на исторический обзор Игоря Пака.

Числа Каталана встречаются во многих комбинаторных задачах (см. недавнюю монографию Р. Стенли). Приведем начало последовательности Каталана (элементы индексируются с нуля):

    \[ \begin{array}{cccccccccccccccc} n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 \\ c_n & 1 & 1 & 2 & 5 & 14 & 42 & 132 & 429 & 1430 & 4862 & 16796 & 58786 &  208012 & 742900 & 2674440 \end{array}\]

При факторизации специальных чисел работают с аналитическими формулами, в которых фигурируют индексы элементов. Число Каталана с индексом  n  вычисляется следующим образом:

(1)   \begin{equation*}   c_n= \frac {1} {n+1} \binom{2n}n = \frac {(2n)!} {n!(n+1)!} \label{fcn0} \end{equation*}

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

В разложении числа Каталана много мелких множителей, все простые числа меньше 2n. Обозначим  P – ряд простых чисел. Факторной базой n-го числа Каталана назовем простой интервал    {_\mathrm p}  (1, 2n)  \subset P, т.е. открытое множество всех простых чисел в указанных границах. Вне факторной базы нет простых делителей числа Каталана.

Непосредственно из формулы (1) следует, что простой интервал  {_\mathrm p} (n{+}1, 2n)  полностью содержится в разложении  n-го числа Каталана. В таком интервале кратность множителей равна 1. Аналогичный интервал  {_\mathrm p} (n, 2n)  в разложении центрального биномиального коэффициента  \binom{2n}n  отмечал Чебышев в 1850 году, когда исследовал распределение простых чисел в натуральном ряде (см. здесь). По-видимому, подобные интервалы или сегменты не единственные в разложении чисел Каталана и центрального биномиального коэффициента.

Функционал Куммера

Разложение натуральных чисел сводится к определению кратности простых делителей. Трудоемкость такой переборной (комбинаторной) задачи зависит от размерности обрабатываемых величин и используемых методов. Выражения с факториалами подобно (1) удобно факторизовать с помощью методики Э. Куммера, с которой можно ознакомиться в этой статье.

Рассмотрим функционал Куммера  v_p(m), который равен кратности простого числа  p  в разложении натурального m.  Например,  v_2(6){=}1, v_2(7){=}0, v_2(8){=}3.  Ниже описаны некоторые свойства функционала для простого  p  и натуральных чисел  a, b, k, m. Каждое свойство в той или иной степени снижает трудоемкость определения кратности путем сокращения числа операндов и/или уменьшения их размерности в функционале Куммера.

Функционал Куммера, свойство 1.  v_p(m) = 0  для всех  m<p.

Функционал Куммера, свойство 2.  v_p(ab) = v_p(a) {+} v_p(b)  .

Функционал Куммера, свойство 2a.  v_p(a^k) = v_p(a) {+} v_p(a^{k-1}) = \ldots =  k v_p(a).

Функционал Куммера, свойство 2b.  v_p(p^k) = k v_p(p) = k.

Функционал Куммера, свойство 3.  v_p(a/b) = v_p(a) {-} v_p(b)  (расширение на область рациональных чисел).

Функционал Куммера, свойство 4.  v_p((pm)!) = m {+} v_p(m!). Проверим сначала это свойство для  p{=}2. Отделим в факториале  (2m)!  четные и нечетные множители:

(2)   \begin{equation*}   (2m)! = 2\cdot 4\cdot 6\cdots 2m \times 1\cdot 3\cdot 5\cdots (2m{-}1) = 2^m \times m! \times (2m{-}1)!!. \end{equation*}

В двойном факториале только нечетные числа, поэтому на основании свойств 2 и 2b получим требуемый результат  v_2((2m)!) = m {+} v_2(m!).

Аналогично распишем факториал  (pm)!  для произвольного  p \in P:

    \begin{equation*} \begin{split} (pm)! &= p\cdot 2p\cdot 3p\cdots mp \; \times \\ &\times 1 \cdot 2 \cdot 3 \cdots (p{-}1) \; \times \\ &\times (p{+}1) \cdot  (p{+}2) \cdot  (p{+}3) \cdots  (2p{-}1) \; \times \\ &\times (2p{+}1)\cdot (2p{+}2)\cdot (2p{+}3)\cdots (3p{-}1)\; \times \\ & \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \\ &\times ((m{-}1)p{+}1) \cdot ((m{-}1)p{+}2) \cdot ((m{-}1)p{+}3) \cdots (mp{-}1). \end{split} \end{equation}

В полученном выражении только множители первой группы кратны  p, поэтому

    \[v_p((pm)!) = v_p(p^m(m!)) = v_p(p^m) + v_p(m!) = m + v_p(m!).\]

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

    \[v_p((pm{+}\delta)!) = m+v_p(m!), \;\; \delta \in \{0,1,2, \ldots,p{-}1 \}.\]

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

Функционал Куммера, свойство 4a.  v_p(p^k!) =  v_p((pp^{k-1})!) =  p^{k-1} + v_p(p^{k-1}!) =
p^{k{-}1} + p^{k{-}2} + v_p(p^{k{-}2}!) = 1 {+} p + p^2 + \ldots + p^{k{-}1} = (p^k{-}1)/(p{-}1).

В свойстве 4a аргумент функционала допускает девиацию:

    \[v_p((p^k{+} \delta)!)=(p^k{-}1)/(p{-}1), \;\; \delta\in \{0,1,2, \ldots,p{-}1 \}.\]

Очевидно,  v_2(2^k!) = v_2((2^k{+}1)!) = 2^k{-}1.

Функционал Куммера, свойство 4b.  v_p((p^km)!) = m  (p^k{-}1)/(p{-}1) + v_p(m!).  Это свойство доказывается аналогично свойству 4a. Очевидно, свойства 4 и 4a являются частными случаями свойства 4b. Соответственно и в свойстве 4b аргумент допускает смещение:

    \[v_p((p^km {+} \delta)!) = m(p^k{-}1)/(p{-}1)+v_p(m!), \;\; \delta \in \{0,1,2, \ldots,p{-}1 \}.\]

Функционал Куммера, свойство 4c.  Для натурального  m < p

    \[ v_p((p^k{+}mp)!) = v_p(p^k!) + m. \]

Следующие ниже равенства достаточно очевидны:

    \begin{equation*} \begin{split} v_p((p^k{+}mp)!) &= v_p((p(p^{k-1}{+}m))!)=(p^{k-1}{+}m) + v_p((p^{k-1}{+}m)!)=p^{k-1}+m+v_p(p^{k-1}!) = \\ &= m + p^{k-1} + \frac{p^{k-1}{-}1} {p{-}1} = m + \frac{p^k{-}1} {p{-}1}. \end{split} \end{equation}

Запишем свойство 4с в общем виде с учетом допустимой девиации:

    \[ v_p((p^k{+}mp{+}\delta)!)=m+ \dfrac{p^k{-}1}{p{-}1}, \;\; m, \delta \in\{0,1,2, \ldots, p{-}1\} . \]

В следующем свойстве усложним аргумент факториала, рассмотрим более общий случай.

Функционал Куммера, свойство 4d.  Для натуральных  m < p  и  l < k

    \[ v_p((p^k{+}mp^l)!) = v_p(p^k!) + m v_p(p^l!). \]

Сначала воспользуемся свойством 4b а затем свойством 4a:

    \begin{equation*} \begin{split} v_p((p^k{+}mp^l)!) &=v_p((p^l(p^{k-l}{+}m))!) =(p^{k-l}{+}m)\, \frac{p^l{-}1}{p{-}1}+ v_p((p^{k-l}{+}m)!) = \\ &= m \, \frac{p^l{-}1} {p{-}1} + p^{k-l} \, \frac{p^l{-}1} {p{-}1} + v_p(p^{k-l}\,!) = m \frac{p^l{-}1} {p{-}1} + \frac{p^k{-}1} {p{-}1}. \end{split} \end{equation}

Как и в свойстве 4с, здесь также допустима девиация, и вид свойства 4d в общем виде идентичен. Следующее свойство функционала является логическим продолжением и завершением свойств 4a–4d.

Функционал Куммера свойство 4e.  Для   m_0, m_1, \ldots, m_k \in \{0, 1, 2,\ldots, p{-}1 \}

    \[v_p((m_kp^k + m_{k-1}p^{k-1} + \ldots + m_1p + m_0)!) = \sum_{i=1}^{k} m_i v_p(p^i\,!).\]

Обратим внимание, свободный член полинома  m_0  играет роль параметра девиации.

Функционал Куммера, свойство 5.  v_p(m!){=}\lfloor m/p\rfloor {+} v_p(\lfloor m/p\rfloor !). Равенство очевидно, если  m\!\le p.  Пусть  k{=}\lfloor m/p \rfloor >1, в этом случае

    \[v_p(m!) = v_p((kp)! \cdot (kp{+}1)(kp{+}2) \cdots m)) = v_p((kp)!) = k +  v_p(k!).\]

В случае  k{>}p  свойство 5 можно повторить для  k!. В конечном итоге, выполняя простые итерации, приходим к известной формуле Лежандра:

(3)   \begin{equation*}  v_p(m!)=\sum_{j>0}{\left\lfloor\frac{m}{p^j}\right\rfloor}. \end{equation*}

На основании формул (1) и (3) получаем функционал для  n-го числа Каталана:

(4)   \begin{equation*}   v_p(c_n) = \sum_{j>0} {\left( \left\lfloor \frac{2n}{p^j} \right\rfloor -  \left\lfloor \frac{n}{p^j} \right\rfloor -  \left\lfloor \frac{n+1}{p^j} \right \rfloor \right)}. \end{equation*}

Простой множитель 2. Рассмотренные свойства функционала позволяют прояснить ситуацию с четностью чисел Каталана. Действительно, для нечетных чисел Каталана

    \[v_2(c_n) = v_2((2n)!) - v_2(n!) - v_2((n{+}1)!) = n - v_2((n{+}1)!) = 0.\]

Как известно, числа Каталана с индексами  n\!=\! 2^k{-}1  (числа Мерсенна) нечетны, и это согласуется со свойством 4a:  v_2((n{+}1)!) \!=\! v_2(2^k!) \!=\! 2^k{-}1. Остальные числа четные, поэтому последовательность Каталана часто рассматривают как блоковую структуру (см. здесь), в которой блоки четных чисел разделены одиночными нечетными элементами.

Длину блоков, в которых группируются четные числа, нетрудно определить. Нечетное число Каталана с индексом   2^k{-}1, \; k\!>\!1,  является границей нижнего блока длиной  2^{k-1}{-}1  и верхнего блока длиной  2^k{-}1.  Каждый блок начинается элементом с кратностью двойки 1. Действительно, в последовательности после граничного элемента с индексом  2^k{-}1  следует число Каталана с кратностью двойки

2^k-v_2((2^k{+}1)!) = 2^k- v_2(2^k! \cdot (2^k{+}1)) = 2^k-(v_2(2^k!) {+}0) = 1.

Вычислим кратность двойки в разложении числа Каталана, которое предшествует граничному элементу с индексом  2^k{-}1, \; k\!>\!1  (максимальный элемент блока снизу):

(2^k{-}2)-v_2((2^k{-}1)!) = 2^k-2- v_2(2^k!/2^k) = 2^k-2-(v_2(2^k!) {-}k) = k-1.

В формуле (2) проявился двойной нечетный факториал. Подобные факториалы часто возникают при расчете кратности простых чисел в разложении специальных чисел. В связи с этим определенный интерес представляют соответствующие свойства функционала Куммера.

Функционал Куммера, свойство 6. Для нечетного натурального  m  и простого  p > 2  упростим выражение  v_p((pm)!!). Распишем двойной факториал:

    \begin{equation*} \begin{split} (pm)!! &= p \cdot 3p \cdot 5p \cdots mp \; \times \\ & \times 1 \cdot 3 \cdot 5 \cdots (p{-}2) \; \times \\ & \times (p{+}2) \cdot (p{+}4) \cdot (p{+}6) \cdots (2p{-}1) \cdot (2p{+}1) \cdots (3p-2) \; \times \\ & \times (3p{+}2) \cdot (3p{+}4) \cdot (3p{+}6) \cdots (4p{-}1) \cdot (4p{+}1) \cdots (5p-2) \; \times \\ & \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \\ & \times ((m{-}2)p{+}2) {\cdot} ((m{-}2)p{+}4) {\cdot} ((m{-}2)p{+}6) \cdots ((m{-}1)p{-}1) {\cdot} ((m{-}1)p{+}1) \cdots (mp{-}2). \end{split} \end{equation}

В первой строке собраны все множители кратные  p, поэтому

    \[v_p((pm)!!) = v_p(p \cdot 3p \cdot 5p \cdots mp) = v_p(p^{\lceil m/2 \rceil}(m!!)) = (m{+}1)\!/2 + v_p(m!!).\]

Здесь мы воспользовались очевидным равенством для нечетного натурального  m\lceil m/2 \rceil \!=\! (m{+}1)\!/2.

В свойстве 6 допустима девиация аргумента функционала, и в общем виде свойство выглядит следующим образом:

    \[v_p((pm{+}\delta)!!) = (m{+}1)\!/2 + v_p(m!!), \;\; \delta \in \{0,2, \ldots, p{-}1, p{+}1, \ldots, 2p{-}2 \}.\]

Функционал Куммера, свойство 6a. Вычислим выражение  v_p(p^k!!), \; p{>}2.  Воспользуемся свойством 6:

    \begin{equation*} \begin{split} v_p(p^k!!) &= \; v_p((pp^{k-1})!!) = (p^{k-1}{+}1)\!/2 + v_p(p^{k-1}!!) = \\ &= (p^{k-1}{+}1)\!/2 + (p^{k-2}{+}1)\!/2 + \ldots + (p{+}1)\!/2 + v_p(p!!) = \\ &= 1 + \frac12 (p{+}1) + \frac12 (p^2{+}1) + \ldots + \frac12 (p^{k-1}{+}1) = \; \frac12 \left( k + \frac{p^k{-}1}{p{-}1} \right). \end{split} \end{equation}

Нетрудно видеть, девиация аргумента функцианала допустима и в свойстве 6a:

    \[v_p((p^k{+}\delta)!!) = \dfrac 12 \left(k + \dfrac{p^k{-}1}{p{-}1} \right), \;\;  \delta \in \{0,2, \ldots, p{-}1, p{+}1, \ldots, 2p{-}2 \}.\]

Функционал Куммера, свойство 6b. Рассмотренные выражения в свойствах 6 и 6a являются частными случаями общего выражения  v_p((p^km)!!), в котором, напомним, простое p{>}2,  m – нечетно, а  k – произвольное натуральное число. С учетом девиации аргумента функционала нетрудно получить следующую зависимость:

    \[v_p((p^km{+}\delta)!!)= \frac12 \left( k+m \frac{p^k{-}1}{p{-}1} \right)+ v_p(m!!), \;\; \delta \in \{0,2, \ldots, p{-}1, p{+}1, \ldots, 2p{-}2 \}.\]

Функционал Куммера, свойство 7. Снизим размерность двойного факториала в выражении  v_p(m!!).  По-прежнему  m – нечетное число и  m\!>\!p\!>\!2  (в других случаях значение функционала Куммера тривиально).

Для положительного  a  обозначим  \lfloor a \rfloor{_\mathrm{odd}} – округление «пол» до ближайшего снизу нечетного натурального числа, т.е. при таком округлении отбрасываем дробную часть числа  a  с дополнительным уменьшением на 1, если результат окажется четным числом. Например, \lfloor 25/7 \rfloor{_\mathrm{odd}} {=} \lfloor 33/7 \rfloor{_\mathrm{odd}} {=} 3. Пусть k{=} \lfloor m/p \rfloor{_\mathrm{odd}} \!>\! 0, тогда

(5)   \begin{equation*}  v_p(m!!) = v_p((kp)!! \cdot (kp{+}2) \cdot (kp{+}4) \cdots m) = v_p((kp)!!) = (k{+}1)\!/2 + v_p(k!!). \end{equation*}

Очевидно, в случае  k \!>\! p  размерность факториала v_p(k!!)  можно дополнительно снизить, повторив процедулу. С помощью формулы (5) нетрудно составить итерационный алгоритм расчета кратности простых чисел в двойных факториалах. Выполняя итерации, приходим к следующей формуле:

(6)   \begin{equation*}  v_p(m!!)= \frac{1}{2} \left(\lfloor\log_p m \rfloor + \sum_{j>0}{\left\lfloor\frac{m}{p^j}\right\rfloor} {_\mathrm{odd}} \right). \end{equation*}

Напомним, в формуле (6m – нечетное число и  m\!>\!p\!>\!2. Очевидно,  \log_p m = \ln m / \ln p. Зависимость (6) проверена на достаточно большом массиве натуральных нечетных чисел – более 10^6.

Для всех  p  из сегмента  S \!=\! {_\mathrm p} (n{+}1, 2n)  v_p(c_n) {=} 1. Поэтому для факторизации  n-го числа Каталана достаточно с помощью формулы (4) просчитать кратность всех простых чисел в интервале  {_\mathrm p}(1, n{+}2).  Однако сегмент  S, скорее всего, не единственный, и тогда между сегментами в факторной базе неизбежны запретные зоны, т.е. отрезки ряда  P, в которых невозможны простые множители  n-го числа Каталана. Работа с зонами запрета может оказаться более перспективной.

Формула Кэли

Количество операндов в формуле (1) можно сократить, если воспользоваться зависимостью (2):

(7)   \begin{equation*}    c_n = 2^n \times \frac {(2n{-}1)!!} {(n{+}1)!}. \end{equation*}

Формула (7) встречается в сети, например, здесь. Идентичное выражение в 1859 году опубликовал Артур Кэли, подсчитывая количество бинарных деревьев (см. здесь), поэтому будем называть зависимость (7) формулой Кэли.

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

(8)   \begin{equation*}  v_2(c_n)= n - v_2((n{+}1)!). \end{equation*}

С помощью зависимости (8) и свойства 4a нетрудно вычислить индексы нечетных чисел Каталана, и эти индексы совпадают с числами Мерсенна:

    \[n = v_2((n{+}1)!) = 2^k {-} 1\]

В формуле Кэли просматривается кратность и нечетных простых множителей:

(9)   \begin{equation*}  v_p(c_n) = v_p((2n{-}1)!!) - v_p((n{+}1)!), \;\; p\!>\!2. \end{equation*}

Нечетные простые множители. Последовательность Каталана разбивается на блоки (сегменты) четных чисел одиночными нечетными числа с индексами  2^k{-}1. Рассмотрим ситуацию с нечетными простыми множителями. Нетрудно проверить, начальные числа Каталана с аналогичными индексами  p^k{-}1  некратны  p. И если это справедливо на всей последовательности, то на основании равенства (9) можно записать

    \[v_p((2(p^k{-}1){-}1)!!) - v_p(p^k!) = 0, \;\; p\!>\!2.\]

Применяя свойство 4a, получаем выражение

(10)   \begin{equation*}  v_p((2p^k{-}3)!!) =  v_p(p^k!) = \frac{p^k{-}1}{p{-}1}, \;\; p\!>\!2. \end{equation*}

Равенство (10) будем рассматривать как свойство 8 функционала Куммера. Докажем это свойство в следующей теореме.

Теорема 0.1. Для каждого простого p число Каталана с индексом  n \!=\! p^k{-}1, \; k\ge1, некратно  p, иначе говоря,  v_p(c_n) \!=\! 0  в случае n\!=\! p^k{-}1.

Доказательство. Случай  p\!=\!2  рассматривался ранее. Пусть, p – нечетное простое число. Вычислим функционал Куммера в левой части равенства (10). Подставим в формулу (6) значение индекса:

    \[v_p((2p^k{-}3)!!) =  \frac{1}{2} \left(\lfloor\log_p(2p^k{-}3) \rfloor + \sum_{j>0}{\left\lfloor\frac{2p^k{-}3}{p^j}\right\rfloor} {_\mathrm{odd}} \right).\]

Сначала определимся с логарифмом. Поскольку  p  нечетно (p>2), то справедливы неравенства  p^k \le 2p^k{-}3 < p^{k{+}1}, и тогда  \lfloor \log_p(2p^k{-}3) \rfloor \!=\! k.

Далее найдем сумму:

    \begin{equation*} \begin{split} \sum_{j>0}{\left\lfloor\frac{2p^k{-}3}{p^j}\right\rfloor} {_\mathrm{odd}} &=  \sum_{j=1}^{k}{\left\lfloor 2p^{k-j} - \frac{3}{p^j} \right\rfloor}{_\mathrm{odd}} = \sum_{j=1}^{k} (2p^{k-j}-1)= \\ &= 2(p^{k{-}1}+p^{k{-}2}+ \ldots + p + 1) - k = 2 \, \frac{p^k{-}1}{p{-}1} - k. \end{split} \end{equation}

Подставляя найденные величины, получаем равенство (10), что и доказывает теорему.  \;\;\;\; \blacksquare

Слои и блоки

С простым множителем 2  связывают разбиение последовательности Каталана на слои или пласты (layers). При этом  k-ый слой  Lk (k ≥ 1) начинается единственным в этом слое нечетным числом с индексом  2^k{-}1, мощность слоя равна 2^k. В случае нечетных множителей картина в чем-то повторяется: для простого числа  p  слой  L_k  начинается числом Каталана с индексом  p^k{-}1,  которое некратно  p, т.е.  v_p(p^k\!\!-\!\!1) \!=\! 0.  Мощность слоя равна  L_k \!=\! (p^{k+1}{-}1)-(p^k{-}1) \!=\! p^k(p{-}1).  Однако число Каталана с нулевой кратностью нечетного  p  далеко не единственное в слое.

Девиация и блоки. В формуле (10) возможна девиация параметра  p^k в обоих факториалах. Варьируемый параметр жестко связан с индексом числа Каталана, поэтому допустимый диапазон изменения величины  p^k фиксирует в  k-ом слое некоторый блок смежных чисел с нулевой кратностью  p, далее – нулевой блок или 0-блок. Вычислим размер нулевого блока. Добавим переменную девиации в факториалы формулы (10):

(11)   \begin{equation*}  v_p((2(p^k+ \delta){-}3)!!) = v_p((p^k+ \delta)!).  \end{equation*}

Область определения переменной δ по обеим сторонам знака равенства различна. Девиация в обычном факториале допустима в пределах  0\le \delta < p (см. свойство 4a). Распишем параметр двойного факториала:  2(p^k{+}\delta){-}3 \!=\! 2p^k{+}2\delta{-}3. В этом случае девиация ограничена более жестко:

2\delta{-}3<p  или  \delta<\frac12(p{+}3),  иначе говоря,  \delta\in\Delta\!=\! \{0,1,\ldots, \frac12(p{+}1) \}.

Таким образом, длина нулевого блока равна  |\Delta| =  \frac12(p{+}3). Будем  считать, что мы доказали еще одну теорему в связи с блочной структурой последовательности Каталана.

Теорема 0.2.  Для каждого нечетного простого  p  и натурального  k  смежные числа Каталана, начиная с индекса  p^k{-}1  и заканчивая индексом  p^k\!+\!\frac12(p{-}1)  включительно, некратны  p. Длина такого  0-блока равна  \frac12(p{+}3).

Рассмотренные теоремы дают лишь начальное представление о блочной структуре последовательности Каталана. В теореме 0.2 не отражены многие нулевые блоки. Например, числа Каталана с индексами 4-7, 9-12, 24-27, 29-32, 34-37, 49-52, 54-57, 59-62, 124-127 некратны 5. И только три выделенных блока начинаются с индексов вида 5^k{-}1, индексы других блоков смещены на величину кратную 5. Некоторые индексы удваиваются: 5 и 10, 25 и 50. Очевидно, возможны случаи утроения индексов и т.д.

Логично предположить, что в каждом слое последовательности Каталана для произвольного простого числа  p  существует определенная иерархия нулевых блоков (и не только нулевых), т.е. блоков, состоящих из смежных чисел Каталана некратных  p. В такой иерархической структуре каждый блок (нулевой или ненулевой) может быть идентифицирован уникальным образом.  Попробуем разобраться в распределении 0-блоков в слоях и подобрать для них удобную идентификацию.

Распределение нулевых блоков. Проверим сначала блоки, элементы которых начинаются с индексов  n\!=\!mp^k{-}1, \; m{<}p.  Если некоторые блоки окажутся нулевыми, то в обобщенном индексе переменная  m  исполняет роль дополнительного параметра девиации, который ответственен уже не за длину 0-блока, а за число его дублей. И эти дубли порождаются базовым блоком с начальным индексом  p^k{-}1. Определим допустимый разброс параметра  m. Подставим значение обобщенного индекса в уравнение (9) и обнулим его:

    \[v_p((2(mp^k{-}1){-}1)!!) - v_p((mp^k)!) = 0, \;\; p\!>\!2, \; m\!<\!p.\]

Применим свойство 4b:

(12)   \begin{equation*}  v_p((2mp^k{-}3)!!) = v_p((mp^k)!) = m(p^k{-}1)/(p{-}1). \end{equation*}

Распишем двойной факториал по формуле (6):

    \[v_p((2mp^k{-}3)!!) =  \frac{1}{2} \left(\lfloor\log_p(2mp^k{-}3) \rfloor + \sum_{j=1}^{k}{\left\lfloor 2mp^{k-j}{-}3/p^j\right\rfloor} {_\mathrm{odd}} \right)\!\!.\]

Нетрудно проверить, равенство (12) выполняется в случае  2m < p  или  m\!\le\! \lfloor p/2 \rfloor\!=\!\frac12(p{-}1).  Например, только при таком условии справедливо равенство  \lfloor\log_p(2mp^k{-}3)\rfloor\!=\!k.

Таким образом, для нечетного простого  p  мы получили в  k-ом слое семейство 0-блоков, элементы которых начинаются с индексов  mp^k{-}1,\; m \!\in\! \{1,2, \ldots, \frac12(p{-}1)\}.  Напомним, в одном нулевом блоке  \frac12(p{+}3)  чисел Каталана, поэтому всего отобрано  \frac14(p{-}1)(p{+}3)  элементов   k-ого слоя.

Работая с индексами вида  mp^k{-}1,  мы воспользовались свойством 4b для вывода формулы (12). С помощью других свойств 4c и 4d, которые оперируют аналогичными параметрами функционала Куммера, можно дополнить семейство 0-блоков. Однако более перспективно свойство 4e, в котором фигурирует полином k-ой степени. Очевидно, использование всех коэффициентов полинома в качестве параметров девиации позволит нам получить все нулевые блоки  k-ого слоя.

Представим индекс числа Каталана в виде  n\!=\!m(p){-}1,  где

(13)   \begin{equation*}  m(p) = m_kp^k + m_{k-1}p^{k-1} + \ldots  + m_1p + m_0. \end{equation*}

Определимся с допустимыми пределами изменения коэффициентов полинома (13), коэффициентов, значения которых позволяют получить индексы чисел Каталана некратных  p, т.е. индексов, которые обнуляют равенство (9).

Свободный член полинома  m_0 \in \{0,1,\ldots, \frac12(p{+}1) \}, он же переменная девиации  \delta, был рассмотрен в уравнении (11). Коэффициент  m_0  «отвечает» за длину 0-блока, которая равна  \frac12(p{+}3). Со старшим коэффициентом  m_k \in \{1,2,\ldots, \frac12(p{-}1)\}  мы определились из уравнения (12), но остальные коэффициенты могут принимать еще и нулевое значение, т.е.  0\!\le\! m_i \!\le\! \frac12(p{-}1), \; i \in \{1,2,\ldots,k{-}1\}.

Таким образом, можно сформулировать еще одно свойство функционала Куммера.

Функционал Куммера, свойство 9.  Для простого нечетного  p  и полинома (13) с коэффициентами, меняющимися в указанных выше пределах, справедливо следующее равенство:

    \[  v_p((2m(p){-}3)!!) = v_p((m(p)!) = \sum_{i=1}^{k} m_i v_p(p^i\,!).\]

Нетрудно подсчитать, количество нулевых блоков в  k-ом слое равно  2^{-k}(p{-}1)(p{+}1)^{k-1}.  Если дополнительно умножим на длину 0-блока, то получим количество чисел Каталана некратных  p.

Идентификация блоков.  В последовательности Каталана каждый  k-ый слой начинается базовым нулевым блоком с начальным индексом  p^k\!\!-\!\!1.  Базовому блоку соответствует следующий набор коэффициентов полинома (13):  m_k\!=\!1, \; m_{k-1}\!=\! m_{k-2}\!=\!\ldots\!=\!m_1\!=\!0  (мы не рассматриваем свободный член  m0, поскольку он не влияет на взаиморасположение блоков в слое, а лишь определяет их длину). Очевидно, базовому 0-блоку можно поставить в соответствие  k-раз­рядный числовой номер или идентификатор 100…0.

Произвольный нулевой блок логично кодировать в позиционной целочисленной системе с основанием  p. В таком  k-раз­рядном  p-ичном числе  i-ый разряд равен  i-ому коэффициенту полинома. Но систему счисления с основанием  p  реализовать практически невозможно, уже при  p\!>\!100  неясно, как подобрать набор уникальных цифр от 0 до  p–1 (или хотя бы до  p/2  для идентификации 0-блоков).

Идентификатор 0-блока в  десятичном виде вычисляется следующим образом:

    \[B{_\mathrm{id}} = m_kp^{k-1} + m_{k-1}p^{k-2} + m_2p + m_1.\]

Каждый набор коэффициентов полинома в допустимых границах соответствует определенному 0-блоку, и обратно, каждый 0-блок характеризуется однозначным набором коэффициентов полинома. По идентификатору просто вычисляется абсолютный адрес 0-блока в последовательности Каталана, начальный индекс числа Каталана в таком блоке равен  pB{_\mathrm{id}} \!-\! 1.

Карта кратности

Читателю предлагается воспользоваться прилагаемым программным сервисом и с помощью этой программы получить и проанализировать для произвольного простого числа  p\!<\!100  распределение кратности для первых 15-20 тысяч чисел Каталана. Программа строит карту кратности для нескольких слоев последовательности Каталана. Индексы чисел с одинаковой кратностью группируются в блоки, в скобках указана метка блока – величина кратности. Каждый блок с нулевой меткой (0-блок) выводится с начала строки.

Сдвоенные блоки. Числа Каталана объединяются в блоки двух видов: длинные блоки содержат  \frac12(p{+}3)  элементов, длина коротких блоков равна  \frac12(p{-}3). Длинные и короткие блоки строго чередуются, поэтому любые два смежных блока содержат ровно  p элементов. Длинный  i-блок и следующий за ним короткий  j-блок будем называть сдвоенным или парным блоком и обозначать  (i,\!j)-блок. После каждого сдвоенного блока программа выводит дополнительный разделительный символ.

В сдвоенном  (i,\!j)-блоке метка длинного блока  i  меньше метки короткого блока  j, поэтому  j\!>\!0, т.е. числа Каталана некратные простому числу попадают только в длинные блоки. Соответственно метка длинного блока всегда меньше максимально допустимой метки в текущем слое (в  k-ом слое максимально возможная метка равна  k\!\!+\!\!1). Таким образом, в  k-ом слое содержатся сдвоенные  (i,\!j)-блоки, где  0 \!\le\! i \!\le\! k  и  1 \!\le\! j \!\le\! k\!\!+\!\!1. Нетрудно подсчитать, число различных видов сдвоенных блоков равно  \frac12 (k\!\!+\!\!1)(k\!\!+\!\!2).

Две дополнительные программы позволяют выделить на карте кратности отдельные виды блоков. Первая программа выводит только сдвоенные (0,j)-блоки. Вторая программа в каждом  k-ом слое отбирает только сдвоенные (i,k\!\!+\!\!1)-блоки. Обратим внимание, в каждом k-ом слое есть единственный сдвоенный  (0,k\!\!+\!\!1)-блок. Назовем такой блок стыковочным или связующим.

Полиномиальные коэффициенты. Предлагаемый программный комплекс  позволяет выводить информацию карты кратности и в другом формате, более удобном для разработки алгоритмов распределения чисел Каталана по блокам. Данная программа ставит в  соответствие сдвоенным блокам наборы коэффициентов полинома (13). Информация по сдвоенному блоку из  k-го слоя выводится в следующем виде:

а) Первым указывается тот индекс из блока, который кратен  p. Напомним, сдвоенный блок содержит ровно  p  индексов чисел Каталана, первые  \frac12 (p{+}3)  индексов образуют длинный блок, остальные  \frac12 (p{-}3)  индексов составляют короткий блок. Очевидно, кратен  p  только второй по счету индекс из длинного блока, которому соответствует значение свободного члена полинома  m_0{=}1. Этот индекс можно рассматривать в качестве идентификатора сдвоенного блока.

б) Далее следует метка метка сдвоенного блока в виде  (i, j), где  i – кратность чисел Каталана из длинного блока и  j – кратность чисел Каталана из короткого блока.

в) Замыкает информационный блок список значений  k  коэффициентов полинома в виде  m_k{+}m_{k-1}\!+ \ldots +\! m_1.

Каждый  k-ый слой начинается сдвоенным блоком c набором коэффициентов полинома 1+0+ …+0. В последнем блоке слоя все коэффициенты равны  p{-}1.

 В формате выдачи полиномиальных коэффициентов пользователь также может получить с помощью дополнительных программ отдельные виды блоков. Одна программа выводит сдвоенные блоки с длинным 0-блоком. В таких сдвоенных блоках коэффициенты полинома не превышают величину  \frac12(p{-}1).  Другая программа в каждом  k-ом слое отбирает сдвоенные блоки с коротким  (k\!\!+\!\!1)-блоком. Обратим внимание, во всех слоях карты кратности стыковочным  (0,k{+}1)-блокам соответствует идентичный набор (отличие лишь в длине кода) полиномиальных коэффициентов из чисел  \frac12(p{-}1).

Для простого числа  p=3  короткие блоки «схлопываются», поэтому карта кратности содержит только длинные блоки по 3 элемента. Однако визуально наблюдаются и блоки удвоенной длины 6 ­– это по сути два смежных длинных блока с элементами одинаковой кратности.

Формула факторизации

В формуле Кэли можно дополнительно снизить количество операндов. Отделим в знаменателе дроби (7) четные множители от нечетных:

    \[(n{+}1)! = 2 \cdot 4 \cdot 6 \cdots 2 \left\lceil \frac{n}{2} \right\rceil \times 1 \cdot 3 \cdot 5 \cdots  \left(2 \left\lfloor \frac{n}{2} \right\rfloor {+} 1 \right) = 2^{\lceil n/2 \rceil} \times \left\lceil \frac{n}{2} \right\rceil ! \times (2 \left\lfloor \frac{n}{2} \right\rfloor {+}1)!!\]

Очевидно,  2 \lceil n/2 \rceil  и  2 \lfloor n/2 \rfloor {+}1  – соответственно максимальное четное число и максимальное нечетное число, не превышающие  n{+}1.

Поскольку  \lceil n/2 \rceil {+} \lfloor n/2 \rfloor = n,  в конечном итоге получаем еще одну формулу

(14)   \begin{equation*}  c_n = 2^{\lfloor n/2 \rfloor} \times \frac {(2 \lfloor n/2 \rfloor {+}3)\cdot(2 \lfloor n/2 \rfloor {+}5) \cdots (2n{-}1)} {\lceil n/2 \rceil!}. \end{equation*}

Зависимость (14) более практична для факторизации, поэтому будем ее называть формулой факторизации чисел Каталана. К примеру, ускоряется подсчет кратности двоек:

    \[v_2(c_n) = \lfloor n/2 \rfloor - v_2( \lceil n/2 \rceil !). \]

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

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>