Factorials

[whitefox]

dimkadimon в сообщении #702876 писал(а):

Гипотеза: количество шагов для N! приближается к N/2 для больших N.

При $\mathrm N$ стремящемся к бесконечности число шагов для $\mathrm N !$ оценивается как $\mathrm O(\log \mathrm N)$

[dimkadimon]

whitefox в сообщении #702889 писал(а):

dimkadimon в сообщении #702876 писал(а):

Гипотеза: количество шагов для N! приближается к N/2 для больших N.

При $\mathrm N$ стремящемся к бесконечности число шагов для $\mathrm N !$ оценивается как $\mathrm O(\log \mathrm N)$

Как так мало?!?

[whitefox]

dimkadimon в сообщении #702909 писал(а):

Как так мало?!?

Извините, пропустил слово "гипотеза"

[dimkadimon]

whitefox в сообщении #702956 писал(а):

dimkadimon в сообщении #702909 писал(а):

Как так мало?!?

Извините, пропустил слово "гипотеза"

Не понял. Уже доказано что количество шагов приближается к O(log N) или это ваша гипотеза?

[whitefox]

dimkadimon в сообщении #702964 писал(а):

Не понял. Уже доказано что количество шагов приближается к O(log N) или это ваша гипотеза?

Гипотеза, но не моя.

macroxue писал(а):

I've noticed that 4lnln n! is pretty close to the minimum sequence length

[dimkadimon]

macroxue писал(а):

I've noticed that 4lnln n! is pretty close to the minimum sequence length

А но это он говорил про N<=37.

[Nataly-Mak]

Nataly-Mak в сообщении #701520 писал(а):

Алгоритм №1 допускает многочисленные вариации, основанные не только на $(n!)^2$, но и на таких разложениях:

$n! =K \cdot m!$ , где $m<n$

В принципе ничего нового: тот же самый "ход вперёд" --- от m! к n!

Удивительно: применила этот метод при переходе от 26! к 33!
Достала!
Совсем не надеялась что-то получить. Тут число K довольно большое:
$K=27 \cdot 28 \cdot 29 ... \cdot 33$

Получилось!
Ну, не оптимальное, конечно, решение получила - всего в 21 шаг, но у меня было вообще очень плохое решение - 24 шага. Улучшение на 3 шага - это совсем не плохо.
Немножко улучшила свои решения для N>30, они у меня пока плоховатенькие (плюс три - плюс шесть шагов от оптимальных).

31 32 33 34 35 36 37
18 18 18 17 19 18 20
21 21 21 23 24 23 25

[Pavlovsky]

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

[Nataly-Mak]

Xaositect в сообщении #675739 писал(а):

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

Pavlovsky
что-то ваша последняя задачка очень напоминает мне эту эвристику, озвученную давным-давно

Кстати, здесь:

Цитата:

Let G(n) be the cost of computing Г(n). Then, such a equation would yield that
G(n)\leq G(n/2)+ O({\log}^{O(1)} n)
This implies a fast method of computing n!.

не говорится ли о длине последовательности для любого натурального числа n?
Я не понимаю по-английски.

[dimkadimon]

Pavlovsky в сообщении #703380 писал(а):

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

Эта задача называется balanced partition problem: http://en.wikipedia.org/wiki/Partition_problem
В вашем случае надо заменить сумму на произведение. Хоть задача NP-complete для нее есть псевдополиномиальный DP алгоритм который ее решит в O(nK^n), где n это количество цифр и K это размер самого большого числа. Ну теперь вы меня точно обгоните :)

[Pavlovsky]

dimkadimon Спасибо. Задачу partition problem я знал, но не подумал, что нет никакой разницы сумму мы считаем или произведение.

dimkadimon в сообщении #703458 писал(а):

Ну теперь вы меня точно обгоните

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

Очередная бредовая идея такая. Труднее всего строить числа содержащие большие простые числа. Есть простое свойство, которое заметил еще Эйлер.
Произведение нечетных чисел, можно представить как разность квадратов.
Пример: 31*29*23*19=628^2-39^2.
Как это применять понятно. Для выше приведенного примера, мы хотим построить число 31*29*23*19. Тогда ищем начальную последовательность в которой есть числа 628 и 39 добавляем к ней числа 628^2,39^2,(628^2-39^2).

Смысл идеи: затратив три операции мы строим число с заданными свойствами.

[Nataly-Mak]

(Оффтоп)

Pavlovsky
да бросьте вы эти факториалы пожалейте свою машину.
Посмотрите, если интересно, какие решения пришли к головоломке о квадратах Стенли (в теме "Антимагические квадраты").
Это грандиозно! Подтверждена минимальность индекса (1597) квадрата Стенли 7-го порядка из простых чисел, что мы очень долго не могли сделать. Приведено ещё много квадратов Стенли с минимальными и не минимальными индексами.
Надо всё это внимательно рассмотреть.
Умеют же люди решать задачи! Когда захотят

[Nataly-Mak]

Ещё чуть-чуть подправила свой хвостик

31 32 33 34 35 36 37
18 18 18 17 19 18 20
20 21 21 22 23 23 25

Теперь нет хотя бы плюс 6 от оптимального решения.

[Nataly-Mak]

Чего-то все замолчали?
Творческий кризис?
У меня напротив всё замечательно есть второе оптимальное решение - для 30!
И всё тем же алгоритмом №1, никаких ухищрений!

$30! = K \cdot (15!)^2$

-- Вс мар 31, 2013 14:35:27 --

Nataly-Mak в сообщении #703402 писал(а):

Кстати, здесь:

Цитата:

Let G(n) be the cost of computing Г(n). Then, such a equation would yield that
G(n)\leq G(n/2)+ O({\log}^{O(1)} n)
This implies a fast method of computing n!.

не говорится ли о длине последовательности для любого натурального числа n?
Я не понимаю по-английски.

И об этом ни гу-гу
Это цитата из какой-то статьи, приведённой выше Pavlovsky.
Я статью, конечно, не стала смотреть, что смотреть, если всё равно ни черта не понимаю.
А перевод... все прекрасно знают, как Гугл переводит.
Ну, вот, например, перевожу эту цитату:

Цитата:

Пусть G (п) затраты на вычислительную Г (п). Затем, такие уравнения даст, что
G(n)\leq G(n/2)+ O({\log}^{O(1)} n)
Это означает быстрый метод вычисления N!.

Ну всё понятно...

Предположила, что приведённое равенство как-то оценивает длину последовательности для любого натурального n. Но это только предположение.

Далее, что означает: "Это означает быстрый метод вычисления N!"
[извините за каламбур]

Что это за быстрый метод такой? Он в статье той, наверное, описан, да?
Ну, правильно: не все методы тут выкладывать, надо что-то и для домашнего пользования оставить

[dimkadimon]

Допустим a(n) это минимальное количество шагов чтобы набрать n. Тогда нас интересует b(n):=a(n!). Формулы для a(n) можно найти тут: http://oeis.org/A173419

Из этих формул имеем (примерно):

b(n) <= 2n
b(n) >= lg(n)+1
b(n) >= n/lg(n),

где lg() бинарный логарифм. Если сможем доказать что существует C так чтобы b(n)<=(log(log n))^C для всех n тогда NP != P.