Наименьший общий неделитель

11

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

Обозначим n=|S|и C=max(S) . Рассмотрим функцию F(x)= наименьшее простое число, не делящее x . Легко видеть, что F(x)logx . А для множества S , пусть F(S)= наименьшее простое число , что не разделяет какой - либо элемент S . У нас есть верхняя граница

F(S)F(lcm(S))F(Cn)nlogC.

Поэтому простой алгоритм перебора, который перечисляет все числа от 1 до nlogC и проверяет, не разделяет ли он какой-либо элемент из S , является полиномиальным и имеет временную сложность O(n2logC) .

Другой способ решить эту проблему - вычислить все факторы для каждого элемента S и использовать их в алгоритме перебора, чтобы проверить, является ли x ответом за O(1) времени. Этот алгоритм имеет временную сложность O(nmin(C,nlogC)+nlogC) и использует O(nlogC) память, потому что нам не нужно вычислять и магазин факторов больше , чем nlogC . Для малых n и C это работает лучше.

Подробно алгоритм состоит из двух частей:

  1. Построить множество S^ составленное из всех факторов всех элементов S , т.е.

    xS fnlogC, (fxfS^)
    Это можно сделать за O(nmin(C,nlogC)) и O(nlogC) памяти. (Откуда это берется? Для любого элемента S мы можем разложить его, используя либо пробную факторизацию со всеми числами до C либо со всеми простыми числами до nlogC , в зависимости от того, что меньше; таким образом, каждый элемент из S может быть учтено во времени O(min(C,nlogC)) время.)
  2. Найдите минимальное число . Этот шаг требует времени, если проверяется, можно ли выполнить за время.dS^O(|S^|)=O(nlogC)xS^O(1)

У меня есть два вопроса, которые меня интересуют:

  1. Есть ли более быстрый алгоритм для решения проблемы?
  2. Для данных и , как мы можем построить множество с максимальным наименьшим общим неделителем?nCS
SkyterX
источник
1. Под «предварительным вычислением» я подразумевал перед запуском алгоритм перебора. 2. Сложность факторинга действительно субэкспоненциальна см Definiton из . C
SkyterX
@DW в точке 2, сложность факторинга является субэкспоненциальной по длине цепочки битов, представляющей число, но SkyterX правильно говорит, что это , то есть пропорционально квадратному корню из размера номер. O(C)
Лиуве Винхуйзен
@LieuweVinkhuijzen, мне это не кажется правильным. Сложность факторинга с использованием GNFS будет примерно равна , что значительно меньше, чем . См. En.wikipedia.org/wiki/… . O(exp{1.9(logC)1/3(loglogC)2/3})O(C)
DW
Утверждение, что второй метод работает лучше «для малых и », не совсем верно. Это работает лучше, только если . Таким образом, должно быть большим, чтобы второй метод работал лучше (не маленький). nCnC/log(C)n
DW
@DW Вы правы, я не знал о сложности GNFS.
Лиуве Винхуйзен

Ответы:

6

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

Есть два алгоритма для целочисленной факторизации, которые здесь важны:

  • GNFS может целое число со временем выполнения .CO(LC[0.33,1.92])

  • ECM может найти факторы (если таковые имеются) со временем выполнения ; нахождение всех факторов займет раз (что относительно мало по сравнению с временем работы ECM).nlogCO(LnlogC[0.5,1.41])O(logC/log(nlogC))

Здесь .Ln[α,c]=exp{c(logn)α(loglogn)1α}

Это довольно ужасно выглядящее выражение для времени выполнения, но важным фактом является то, что это быстрее, чем методы, которые вы упомянули. В частности, асимптотически намного меньше, чем , т. намного быстрее, чем пробует все возможные факторы . Также асимптотически значительно меньше , то есть ECM гораздо быстрее , чем пытаться все возможные факторы .LC[0.33,1.92]CCLnlogC[0.5,1.41]nlogCnlogC

Таким образом, общее время выполнения этого метода примерно равно , и это асимптотически лучше, чем ваш Первый метод и асимптотически лучше, чем ваш второй метод. Я не знаю, возможно ли сделать еще лучше.O~(nmin(LC[0.33,1.92],LnlogC[0.5,1.41]))

DW
источник
Я думаю, что любой быстрый алгоритм для этой задачи должен включать в себя какое - то факторизации ввода множество . Я проверим эти алгоритмы факторизации, но все еще существует проблема их правильного тестирования, которая поднимает вторую проблему, о которой я упоминал, о построении множества с максимальным ответом. SS
SkyterX
ECM находит один фактор во времени, которое вы даете. Если все множители числа ≤ n log C, то вам нужно повторить алгоритм, до log C / log (n log C) раз.
gnasher729
3

Наименьший общий неделитель может быть таким же большим, как N log C, но если N чисел распределены случайным образом, то наименьший общий неделитель, вероятно, будет намного меньше, вероятно, намного меньше N. Я бы построил таблицы, из которых простые числа делители которых числа.

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

Тогда для d = 2, 3, 4, ... мы пытаемся найти число, делимое на d, или показать, что его нет. Мы берем наибольший простой множитель p of d. Затем мы проверяем все числа, которые делятся на p, делятся ли они также на d. Если ничего не найдено, то мы проверяем дальнейшие числа с индексами> на делимость на p, обновляем и список чисел , p, и проверяем, делится ли каждое число на d.kpkp

Чтобы проверить, существует ли число, делимое на p, мы проверяем в среднем число p. Позже, если мы проверим, есть ли число, делимое на 2p, есть 50% -ый шанс, что нам нужно проверить только одно число (то, которое делится на p), и 50% -ый шанс проверить в среднем на 2p больше чисел. Найти число, делимое на 3p, вполне вероятно, быстро и так далее, и мы никогда не проверяем делимость на p больше чем N чисел, потому что есть только N чисел.

Я надеюсь, что это с проверок делимости.N2/logN

PS. Насколько большим будет результат для случайных чисел?

Предположим, у меня есть N случайных чисел. Вероятность того, что одно из N чисел делится на d, равна 1 - (1 - 1 / d) ^ N. Я предполагаю, что вероятность того, что каждое из чисел 1 ≤ d ≤ k является фактором одного из случайных чисел, рассчитывается путем умножения этих вероятностей (хорошо, это немного хитроумно, потому что эти вероятности, вероятно, не совсем независимы).

С этим допущением, при N = 1000, есть 50% -ная вероятность того, что одно из чисел 1..244 не делит ни одного числа, и одно из миллиарда, что каждое число до 507 делит одно из чисел. При N = 10000 есть 50% вероятность того, что одно из чисел 1..1726 не делит ни одного числа, а одно на миллиард, что каждое число до 2979 делит одно из чисел.

Я хотел бы предложить, что для N случайных входов размер результата немного больше, чем N / ln N; может быть что-то вроде N / ln N * (ln ln N) ^ 2. Вот почему:

Вероятность того, что по меньшей мере один из N случайных чисел делятся на случайный д составляет . Если d около N, то составляет около 1 - exp (-1) ≈ 0,6321. Это для одного делителя; шансы того, что каждое из нескольких чисел d ≈ N является делителем хотя бы одного из N чисел, достаточно малы, поэтому максимальное значение d будет значительно меньше N.1(11/d)N1(11/d)N

Если d << N, то .1(11/d)N1exp(N/d)

Если d ≈ N / N , то пер .1exp(N/d)1exp(lnN)=11/N

Мы добавили бы эти вероятности для примерно N / ln N значений d, но для большинства d результат будет значительно больше, поэтому самый большой d будет как-то больше, чем N / ln N, но значительно меньше, чем N.

PS. Нахождение числа, делимого на d:

Мы выбираем наибольший простой фактор p из d, а затем сначала исследуем числа, которые, как известно, делятся на p. Скажи д = кп. Тогда в среднем мы проверяем только k чисел, которые делятся на p, при проверке этого конкретного d, и мы проверяем самое большее все N значений для делимости на p в целом, для всех d, делимых на p. На самом деле, мы, скорее всего, проверяем значения меньше N для большинства простых чисел p, потому что после проверки всех значений N алгоритм, скорее всего, заканчивается. Таким образом, если результат равен R, то я ожидаю, что меньше чем N значений будет делиться на каждое простое число меньше R. Предполагая, что R ≤ N, это примерно N ^ 2 / log N проверок.

PS. Выполнение некоторых тестов

Я запускал этот алгоритм несколько раз с N = 1 000 000 случайных чисел> 0. Наименее распространенный неделитель составлял от 68 000 до 128 000, причем подавляющее большинство прогонов - от 100 000 до 120 000. Количество делений составляло от 520 до 1800 миллионов, что намного меньше (N / ln N) ^ 2; В большинстве случаев используется от 1000 до 1500 миллионов делений.

gnasher729
источник