Распределение квадратов и проверка гипотез в нечетных разбиениях чисел
Автор: Самойлов А.А.
Статья в выпуске: 1 т.13, 2024 года.
Бесплатный доступ
В статье рассматриваются разбиения натурального числа n, части которого различны, нечетны и их произведение не является квадратом. Такие разбиения применимы для определения ранга группы центральных единиц целочисленного группового кольца знакопеременной группы. Количество разбиений растет экспоненциально, следовательно, задача перебора является вычислительно затратной. В статье предложен параллельный алгоритм в общей памяти для нахождения количества разбиений числа n с дополнительными условиями. Алгоритм основан на концепции распараллеливания по данным и использовании вложенного параллелизма. Выделяется множество длин K разбиения числа n, элементы которого обрабатываются параллельно. Во время обработки длины k разбиения числа n выделяется множество уровней L, рассмотрение которого также выполняется параллельно. Приемлемые значения ускорения и параллельной эффективности предложенного алгоритма получаются при использовании двух нитей на параллельный регион по длинам и двух - по уровням. Таким образом, ускорение при разных n превышает 2.1, а параллельная эффективность не опускается ниже 50 %. Полученные результаты использованы для проверки гипотез Каргаполова и анализа распределения значений нечетных разбиений на некоторых диапазонах. Предложен алгоритм поиска оптимального коэффициента c. С помощью этого алгоритма получена асимптотическая формула количества разбиения числа n, в котором части различны и нечетны, а их произведение является квадратом. Эта формула основана на экспериментальных данных и сформулирована как гипотеза.
Разбиение натурального числа, асимптотическая формула, параллельные вычисления, openmp
Короткий адрес: https://sciup.org/147243206
IDR: 147243206 | УДК: 004.021, | DOI: 10.14529/cmse240102
Distribution of squares and hypothesis verification in odd integer partitions
The article considers partitions of a natural number n whose parts are distinct, odd and their product is not a square. Such partitions are applicable for determining the rank of the group of central units of an integral group ring of an alternating group. The number of partitions grows exponentially, hence the enumeration task is computationally expensive. The article proposes a parallel algorithm in shared memory for finding the number of partitions of the n with additional conditions. The algorithm is based on the concept of data parallelism and the use of nested parallelism. A set of lengths K of the partition of the n is obtained, the elements of which are processed in parallel. During the processing of the length k of the partition of the n, the set of levels L is obtained, the elements of which are processed in parallel as well. Acceptable values of speedup and parallel efficiency of the proposed algorithm are obtained by using two threads per parallel length region and two threads per parallel level region. Thus, the speedup for distinct n increases to 2.1, and the parallel efficiency does not decrease below 50 %. The results obtained were used to check Kargapolov’s hypotheses and analyze the distribution of the number of odd partition in certain ranges. An algorithm for finding the optimal coefficient c is proposed. Using this algorithm, an asymptotic formula for the number of partitions of the n is obtained, in which the parts are distinct, odd and their product is a square. This formula is based on experimental data and formulated as a conjecture.
Список литературы Распределение квадратов и проверка гипотез в нечетных разбиениях чисел
- Ferraz R.A. Simple components and central units in group algebras // Journal of Algebra. 2004. Vol. 279, no. 1. P. 191-203. DOI: 10.1016/j . jalgebra.2004.05.005.
- Алеев Р.Ж., Каргаполов A.B., Соколов B.B. Ранги групп центральных единиц целочисленных групповых колец знакопеременных групп // Фундаментальная и прикладная математика. 2008. Т. 14, № 7. С. 15-21.
- Каргаполов A.B. Центральные единицы целочисленных групповых колец знакопеременных групп: дис. ... канд. / Каргаполов Андрей Валерьевич. Южно-Уральский Государственный Университет, Россия, 2012.
- Sagan В.Е. The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions. New York: Springer New York, 2001. XVI, 240 p. DOI: 10.1007/978-1-4757-6804-6.
- Doliskani J.N., Malekian E., Zakerolhosseini A. A Cryptosystem Based on the Symmetric Group Sn // IJCSNS International Journal of Computer Science and Network Security. 2008. Vol. 8, no. 2. P. 226-234.
- Эндрюс Г. Теория разбиений. Москва: Наука, 1982. 256 с.
- Постников А.Г. Введение в аналитическую теорию чисел. Москва: Наука, 1971. 416 с.
- Липский В. Комбинаторика для программистов. Москва: Мир, 1988. 200 с.
- Андерсон Д.А. Дискретная математика и комбинаторика. Москва: Вильяме, 2004. 960 с.
- Kelley С.Т. Iterative Methods for Optimization. University City, Philadelphia: Society for Industrial and Applied Mathematics, 1999. 196 p. DOI: 10.1137/1.9781611970920.
- Самойлов A.A. Исследование разбиений с дополнительными условиями. URL: https: //github.com/SashaSamoilov/qop-partitions (дата обращения: 25.09.2023).
