Сегментация  

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

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

Порог кратности  g_n \!=\! \sqrt {2n}  разбивает факторную базу на два непересекающихся подмножества: из нижней области отбираются все кратные множители разложения, из верхней области можно выбрать только неповторяющиеся множители. Поскольку 2n – четное число, то порог кратности, будучи целым (в этом случае  n  четное число), также будет четным числом. Поэтому порог кратности никогда не принадлежит факторной базе. Кратные простые множители всегда меньше  g_n, а все простые множители, превышающие  g_n, не могут повториться.

В этом разделе мы рассмотрим метод сегментации, который успешно применяется при факторизации больших чисел Каталана (с индексами 10000 и более). Распределение и состав множителей в факторной базе определяется формулой Кэли

    \[ c_n = 2^n \times \frac {1\! \cdot \!3\! \cdot  \!5  \cdots   (2n-3)(2n-1)} {1\! \cdot  \!2\! \cdot  \!3 \cdots  n(n+1)} . \]

Все простые числа числителя, превышающие  n{+}1, гарантировано попадают в разложение  c_n. Поэтому верхний (первый) сегмент факторной базы  S_1\!\!= {_\mathrm p} (n{+}1, 2n)  полностью включен в разложение числа Каталана. К сегменту снизу примыкает запретная зона – закрытый простой отрезок  {_\mathrm p} [2n/3, n{+}1]. Все простые числа из этого множества, включая граничные значения, не могут попасть в разложение  n-го числа Каталана. Таким образом, верхняя область факторной базы «нарезается» на сегменты, разделенные зонами запрета.

Сделаем небольшое отступление. Когда мы говорим, например, о четном числе  2n/3  или о натуральном  (n{+}1)/2, то имеются в виду вероятные (возможные) величины при определенных значениях индекса  n, а именно: в первом случае  n  кратно 3, во втором  n – нечетное число. В таких очевидных случаях пояснения будем опускать.

Верхние грани сегментов

В запретной зоне нижняя грань  2n/3  может быть либо дробным, либо целым и, соответственно, четным числом. Такое число не может оказаться в факторной базе  n-го числа Каталана, поэтому ближайшие простые числа выше этой границы входят в зону запрета, а ближайшие простые числа снизу принадлежат следующему 2-му сегменту. По аналогии с 1-ым сегментом будем рассматривать 2-ой и остальные сегменты как открытые простые интервалы.

Итак, число  2n/3  является нижней закрытой гранью зоны запрета, и эта же величина является верхней открытой гранью 2-го сегмента. Если число  2n/3  окажется целым и, следовательно, четным, то предшествующее нечетное число  \dfrac{2n}{3}\!-\!1, будучи простым, обязательно попадет в разложение.

Пример 5. Пусть  n =300, число  2×300/3–1 = 199 простое, и в разложении такой множитель есть. Все объясняется просто на основании формулы Кэли. Действительно, в числителе дроби двойной факториал 599!! (произведение нечетных чисел), содержит наш множитель в двух экземплярах: непосредственно 199 и дополнительно в составном нечетном числе 597=199×3. В знаменателе обычный факториал 301! содержит простое число 199 лишь один раз. Обратим внимание, следующее простое число 211 превышает нижнюю границу запретной зоны и не попадает в разложение.

Таким образом, для первого и второго сегментов верхние грани равны соответственно  2n  и  2n/3. Если записать грань первого сегмента в виде  2n/1, возникает подозрение, что верхняя грань третьего сегмента равна  2n/5. Проверим и это на примере.

Пример 6. Для  n =7500  верхняя грань третьего сегмента равна 2×7500/5  = 3000. В разложении есть простое число 2999, но отсутствует следующее простое число 3001.  Налицо не только третий сегмент, но и запретная зона между 2-ым и 3-им сегментами. Обратимся снова к формуле Кэли.

В числителе дроби множитель 2999 обнаруживается в трех экземплярах, а именно: 2999,  3×2999, 5×2999. В знаменателе только два экземпляра 2999 и 2×2999. Но для следующего простого числа 3001 в числителе в наличии лишь два экземпляра, поскольку составное число 5×3001 выходит за пределы факторной базы. Напомним, числитель дроби состоит из нечетных множителей двойного факториала 14999!!, в знаменателе обычный факториал 7501!.

Очевидно, верхняя грань следующего 4-го сегмента равна  2n/7. Обобщим полученные результаты.

Утверждение 2. В факторной базе  n-го числа Каталана верхняя грань  k-го сегмента равна  2n/(2k{-}1).

Доказать это утверждение несложно по аналогии с методикой, использованной в последних примерах. Предоставим это сделать читателю.

Забегая вперед, отметим одно обстоятельство, которое ограничивает возможности метода сегментации. По мере приближения к порогу кратности верхние грани соседних сегментов быстро сходятся, и вблизи порога многие сегменты практически «схлопываются», т.е оказываются пустыми, без простых чисел.

Нижние грани сегментов

В первом сегменте факторной базы нижняя грань  n{+}1  определяется просто, достаточно проанализировать множители факториалов в формуле Кэли. Запишем открытый простой интервал первого сегмента в виде  {_\mathrm p} \!\left( \dfrac {n{+}1}{1}, \dfrac {2n}{1} \right). Подобную запись мы уже использовали для верхней грани, когда определялись с  k-ым сегментом. Если найдем общий вид нижней грани, то получим в результате выражение для простого интервала произвольного сегмента.

Пусть простое число  m < \dfrac {2n}{3}  и одновременно  m > \dfrac {n{+}1}{2}. В этом случае  m  попадает в разложение  c_n, поскольку в разложении факториала  (n{+}1)!  число  m  будет в единственном экземпляре, а в разложении двойного факториала  (2n{-}1)!!  множитель  m  содержится дополнительно в составном числе  3m<2n. Четное составное число  2m  нам не подходит, поскольку в двойном факториале только нечетные числа. Таким образом,  m \in S_2.

Очевидно, все простые числа  m'  из диапазона  (n{+}1)/2 < m' < 2n/3  также принадлежат второму сегменту. Но целое число  m'\!=\!(n{+}1)/2,  будучи простым, уже попадает в запретную зону, поскольку в разложении факториала  (n{+}1)!  появляется второй экземпляр этого множителя в составном числе  2m'\!=\!n{+}1.

Таким образом, для верхней области факторной базы  n-го числа Каталана у нас есть два открытых простых интервала  S_1\!\!= {_\mathrm p} \!\left(\dfrac {n{+}1}{1}, \dfrac {2n}{1} \right)S_2\!\!= {_\mathrm p} \!\left(\dfrac {n{+}1}{2}, \dfrac {2n}{3} \right). Аналогичным образом нетрудно обосновать существование третьего сегмента  S_3\!\!= {_\mathrm p} \!\left(\dfrac {n{+}1}{3}, \dfrac {2n}{5} \right). Каждый следующий сегмент приближается к порогу кратности g_n. Очевидно, нижняя грань последнего  k-го сегмента не должна перейти порог g_n, иначе говоря,  k_{max} < n/g_n = \sqrt{n/2}.

Итак, можно сформулировать еще одно и, надеюсь, очевидное утверждение.

Утверждение 3. В факторной базе  n-го числа Каталана  k-ый сегмент имеет вид

    \[S_k\!= \; {_\mathrm p} \!\left(\frac {n{+}1}{k}, \frac {2n}{2k{-}1} \right), \;\;\; k < \sqrt{n/2}.\]

Как видим, количество сегментов в верхней области факторной базы определяется индексом числа Каталана. Например, для миллионного числа Каталана  k_{max} \!=\! 707.

Границы сегментов по большей части дробные числа, но удобнее, конечно, работать с целыми величинами. При округлении открытые границы простых интервалов желательно сохранить, поэтому в нижней грани сегмента будем отбрасывать дробную часть (округление снизу – «пол»), а для верхней грани берется ближайшее целое сверху (округление «потолок»). Таким образом работают все прилагаемые программы из прилагаемого сервиса.

Особенности сегментации

Начальные сегменты выхватывают существенные куски ряда простых чисел, напомним, только первый сегмент выбирает больше половины всех множителей разложения числа Каталана. Сегменты с большими порядковыми номерами (ближе к порогу кратности), часто оказываются пустыми, без простых чисел. С увеличением порядковых номеров границы сегментов смыкаются, и процедура нарезки сегментов работает, можно сказать, «вслепую». У каждого сегмента фиксированные грани, и что попадет внутрь заранее определить невозможно. (Вспомним рыбалку: и заброшенный невод может прийти лишь с тиной морскою.)

Пример 7. Рассмотрим факторизацию миллионного числа Каталана (пользователь может получить разложение здесь). Натуральный вид числа  c1000000  вряд ли кого заинтересует, все-таки сплошной массив из 600 тысяч десятичных знаков мало что может сказать. Другое дело множители разложения, даже если их очень много. В разложении миллионного числа Каталана 101543 элемента (с учетом кратности). Все простые числа выбираются из факторной базы  p(1,2000000). Множитель 2 имеет кратность 7, максимальный множитель равен 1999993.

Факторная база разделена порогом кратности  g1000000 = 1414.21 на две непересекающиеся части. Нижняя область – «вотчина» кратных множителей, для максимального числа этой области 1409 функционал Куммера равен 2. Неповторяющиеся простые числа верхней области распределены по 707 сегментам. Первые сегменты объединяют подавляющую часть элементов разложения. Сегмент  S1 = p(1000001,2000000)  включает 70435 простых чисел, сегмент S2 = p(500000,666667)  объединяет 12531 простое число (открытые границы второго сегмента округлены до целых чисел: нижняя грань «пол», верхняя – «потолок»). Суммарно оба сегмента охватывают почти 82% множителей.

Ближайшее простое число выше порога кратности 1423, и этот множитель есть в разложении, поскольку попадает в сегмент S703 = p(1422,1424). Следовательно, четыре сегмента с номерами 704–707 пустые, т.е. не содержат множителей разложения миллионного числа Каталана. Следующее простое число 1433 также попадает в разложение и выбирается из факторной базы сегментом S698 = p(1432,1434). В результате обнаружена еще одна группа пустых сегментов с порядковыми номерами 699– 702. Как видим, вблизи порога кратности в данном случае лишь только пятый сегмент «приносит добычу». И что-то с этим надо делать.

В связи с примером 7 возникает вопрос, не напрасно ли мы теряем время (уточним, машинное время) на обработку пустых сегментов вблизи порога кратности? Может быть, в приграничной зоне проще непосредственно тестировать простые числа как в случае с кратными множителями. Расчеты показывают, что целесообразно поднять границу между областями факторной базы до величины 5gn и даже более, т.е. расширить зону алгоритма выборки кратных множителей. В этом случае мы гарантированно избавляемся от перебора пустых приграничных сегментов.

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

Очевидно, если хранить только множители кратной зоны, то существенно сократится натуральный вид чисел Каталана. В следующем и последнем разделе мы рассмотрим Легкие числа Каталана.

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

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

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