Задача по дискретной математике

nozanin

Есть интересная задача. Ваши идеи?
Число N разложить на n слагаемых, так, чтобы НОК этих слагаемых был максимален...
Любые идеи очень нужны!

114ttr

Чем же она интересна ?

nozanin

Возникает из другой очень важной задачи.
Вообще, кто поможет ссылками -- спасибо! Схлду такое не решить, очевидно...
Интересен алгоритм, ес-но. Любые идеи...

margo11

Взять первые простые числа, сколько получится, чтобы в сумме было n (если ровно не получается, то добавить что угодно). Это НЕ метод получить максимальный НОК. Имхо, максимальный получить не получится. Но предложенный метод позволяет оценить максимальный НОК снизу. имхо, получить более хорошую оценку будет малореально.

margo11

И при чем тут дискра?

Xephon

очевидно, что все слагаемые можно взять простыми (ну и еще единицы)

nozanin

Совсем не очевидно. Честно...

Xephon

пусть в лучшем разложении есть число X, отличное от 1 и не простое
тогда X=ab, где у a и b вместе те же делители, но a+b<=X

nozanin

=7+4
NOK(7,4)=28
11=6+5
NOK(6,5)=30
Какая связь с проостыми числами, я не вижу...
Нужно коцать на определенное число слагаемых.

Xephon

да. неправду сказал. степени простых там, а не сами простые...

margo11

Можно показать, что существует с > 1 такая что HOK(n) > c^(sqrt(n*ln(n. Доказать что-то лучшее вряд ли получится, так рекомендую взять это и на этом остановиться.

Sanych

Это оценка для чего-то вроде НОК(1,2,3...n)?
Всё таки ищем мы f(N,n и не надо об этом забывать.

margo11

да, это оценка, когда число n слагаемых не фиксировано.

filippov2005

Первое, что в голову пришло - слагаемые должны быть, наверно, взаимно простые. А n - мало по сравнению с N, а может вообще мало (фиксировано - 2, 3 там, например)? Можно действовать так: разбивать N примерно на равные части, так чтобы они были бы попарно взаимны просты - тогда их НОК равен их произведению, а оно близко к максимальному произведению n частей, которое, ясно, не меньше f(N,n).

vln2

Какая связь с проостыми числами, я не вижу...

Alessio правильно говорит. Разлагаться должно в сумму степеней простых чисел + сколько то 1 (может быть).
Алгоритм такой: возьмем любую сумму a1+a2+..an и вынесем из слагаемых максимальную степени 2-ки в отдельное слагаемое -> 2^k + b1 + .. + bn. Если ни одно из чисел на 2 не делится, то k=0 и под 2^0 будем иметь ввиду 0, а не 1. Получившееся число будет обязательно меньше или равно начальному, а НОК слагаемых останется прежним. Разность компенсируем суммой 1-чных слагаемых 1+1...+1. Т.е. получили 2^k+b1+..bn+1+..+1 = a1+..+an. Тоже самое делаем для 3-ки, 5-ки и т.д. В результате получится сумма (1+..+1)+2^k1+3^k2+..., где ki >= 0 (x^0 = 0). Ее НОК равен начальному, но она в нужной форме.

filippov2005

Но количество слагаемых фиксировано. А в этом методе их может получится больше, чем нужно.

sirp

А нельзя решить задачу методом динамического программирования? Т.е. считать f(N, n) через ее значения при меньших аргументах. Сложность порядка N^3. Ненамного сложнее, чем работать с простыми числами, ИМХО

filippov2005

Точнее O(n*N^3) - мы же не знаем пока о малости n. Но если оно мало по сравнению с N, то действительно получается O(N^3). По-моему неплохо. Динамическое программирование рулит. А ведь НОК(f(N-x_k, k-1x_k) вроде ищется быстрее, чем О(N) (по краней мере, почти всегда так что реально получится меньше.

sirp

Похоже тут метод динамического программирования вообще не подходит - принцип Беллмана не работает
Сорри, что сбил с толку

nozanin

Спасибо всем за советы, но я не понимаю, почему у Анонимуса будет получаться максимальный из возможных НОК...

filippov2005

Да, к сожалению. Я про динамическое программирование мало слышал. Как я понамаю надо действовать так: Пусть мы знаем f(I,k-1) для 2 < I < N. Далее f(I, k)=max_(1<=x_k<=I){НОК(f(I - x_k, k-1x_k)} То, что получится искомая функция, скорее всего, неверно. Получим только нижнюю оценку.

Xephon

вначале задача была без фиксирования числа слагаемых
Оставить комментарий
Имя или ник:
Комментарий: