Factorials

[Nataly-Mak]

Цитата:

43 23.15 Gennady Gusev Rybinsk, Russia 31 Mar 2013 16:57
44 23.03 Alexandra Chrysothemis Salzburg, Austria 5 Apr 2013 18:37

Фрау из Австрии ну очень активна
Уже наступает на пятки нашему Геннадию.
Интересно, одна играет или руководит командой

Из 410 конкурсантов активны не более 20. Это ж надо так притомиться!
Если честно, я очень устала, но... всё ещё продолжаю что-то искать.
Удача улыбается всё реже

[dimkadimon]

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

Из 410 конкурсантов активны не более 20. Это ж надо так притомиться!
Если честно, я очень устала, но... всё ещё продолжаю что-то искать.
Удача улыбается всё реже

Мои программы не перестают работать, но ничего не находят...

[Nataly-Mak]

Ну, если работают только программы, а вы в этом процессе уже не участвуете, - это одно.
Совсем другое у меня. Я постоянно ищу саму "формулу" решения, думать приходится

[dimkadimon]

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

Ну, если работают только программы, а вы в этом процессе уже не участвуете, - это одно.
Совсем другое у меня. Я постоянно ищу саму "формулу" решения, думать приходится

Не ну мозг тоже немного работает. Приходят маленькие идеи и я их проверяю. Видимо нужно кардинально изменить подход, но на это уже нет сил.

[dimkadimon]

Как я уже говорил, если найти число C так чтобы a(n!)<=(log n)^C для всех n тогда NP!=P. Вот что получается для 3<=n<=37:

(Оффтоп)

n C
3 2.3853797636157603
4 2.0
5 2.1269751923532634
6 1.8866365311700843
7 1.8851284589513904
8 1.8927892607143721
9 1.80239858793192
10 1.8301887124589067
11 1.770378662881449
12 1.8034765418398742
13 1.8326204587161594
14 1.7935769559007324
15 1.8234610731915566
16 1.7924812503605783
17 1.7649431814211418
18 1.7963112680018978
19 1.7732950739804714
20 1.8030022593734045
21 1.783319182201809
22 1.7652305673423851
23 1.7942428219387818
24 1.778357198169698
25 1.8056055329250045
26 1.7497752043616595
27 1.7782431177824582
28 1.7658147204387942
29 1.7924663187562535
30 1.7811777161575517
31 1.8062171091744643
32 1.7958889470453636
33 1.7860791281036692
34 1.7416089795898106
35 1.800917684725754
36 1.7593556094480969
37 1.8150728732902714

Значит самое большое C которое нужно это 2.38. Кстати для n=100 и 200 у меня C тоже меньше 2.38. А вот для n=500 C получилось чуть больше, но я особо не старался и думаю его можно уменьшить. Очевидно что с ростом n, C не растет так сильно. Может оно даже доходит до какого то предела (например 1.8).

На самом деле многие эксперты почти уверены что NP!=P. Если это доказать то будет конечно приятно, но в реальности ничего не изменится. А вот если доказать что NP=P тогда гораздо интереснее :)

[Xaositect]

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

Как я уже говорил, если найти число C так чтобы a(n!)<=(log n)^C для всех n тогда NP!=P.

Наоборот. Если $\tau(n!) \neq O(\log^k n)$ для любого $k$, то $\mathbf{P}\neq \mathbf{NP}$

[dimkadimon]

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

Наоборот. Если $\tau(n!) \neq O(\log^k n)$ для любого $k$, то $\mathbf{P}\neq \mathbf{NP}$

Да вы правы.

[Nataly-Mak]

У меня число, имеющее рекордное количество решений в 10 шагов (у меня больше не было ни для одного числа). Это число 3991680, оно имеет 3250 решений в 10 шагов.
Имеются и решения в 9 шагов - 8 штук.

Кто побьёт мой рекорд?

[dimkadimon]

Если представить n! как бинарное число m то можно найти решение состоящие только из операций +1 и *2. Например 5!=120=1111000. Значит 5!=((((1*2)+1)*2+1)*2+1)*2*2*2=1,2,3,6,7,14,15,30,60,120. Значит количество шагов для n! это количество раз мы делаем +1 плюс количество раз мы делаем *2 минус 1 (из за первого 1). +1 мы делаем столько раз сколько '1' в m, а *2 мы делаем на один раз меньше чем цифр в m.

Допустим d(k) это количество цифр в k, a(n!) количество шагов для получения n!. Тогда a(n!)<=2*d(n!)-2. d(m) можно найти с помощью формулы Стирлинга (http://en.wikipedia.org/wiki/Stirling%27s_approximation). d(n!) ~= floor[log(sqrt(2*pi*n)*(n/e)^n)]+1, где log бинарный логарифм. Имеем:

а(n!) растет как О(log(sqrt(2*pi*n)*(n/e)^n)). Это растет как О(log(n^(1/2)*n^n)) -> O(log(n^n)) -> O(n*logn). Не знаю как такой рост связан с O((log n)^C) ?

[Xaositect]

$n$ растет быстрее, чем любой $\log^k n$.

[dmd]

А нельзя ли подробнее пояснить взаимосвязь с проблемой P?=NP. Разве все NP-задачи сводятся к задаче этого конкурса? Если да, то где оно это доказательство сводимости? Если вдруг в данном контексте решение задачи сводимости не нужно делать, то это тоже надо отдельно пояснить - почему так?

[Nataly-Mak]

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

Допустим d(k) это количество цифр в k, a(n!) количество шагов для получения n!. Тогда a(n!)<=2*d(n!)-2.

Мне не понятна эта формула.

Пример
n=6!
d(6!)=3
a(6!)<=2*d(6!)-2
a(6!)<=4, но это же неверно!

Или под k имеется в виду его бинарное представление? Надо тогда уточнять при формулировании условий для формулы.
Может, я чего-то не понимаю, но если под k иметь в виду бинарное представление числа k, то приведённая формула для количества шагов a(k) является слишком грубой оценкой.

[dimkadimon]

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

Или под k имеется в виду его бинарное представление? Надо тогда уточнять при формулировании условий для формулы.
Может, я чего-то не понимаю, но если под k иметь в виду бинарное представление числа k, то приведённая формула для количества шагов a(k) является слишком грубой оценкой.

Верно, d(k) это количество цифр в бинарном представлении k, я забыл это пояснить. Оценка грубая, но позволяет нам найти решение для любого n!. Кстати можно использовать не только бинарное представление, a любую другую базу тоже. Например, будем использовать базу 6: 5!=120=320 в базе 6 = (3*6+2)*6 = 1, 2, 3, 6, 18, 20, 120. Иногда с другой базой получается лучше оценка. Конечно в плане большой О ничего не меняется.

-- 07.04.2013, 17:45 --

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

$n$ растет быстрее, чем любой $\log^k n$.

Да. Что дальше?

[Nataly-Mak]

Цитата:

13 24.42 Valery Pavlovsky Ekaterinburg, Russia 7 Apr 2013 04:37

Pavlovsky
получится из меня предсказательница?

Фрау из Австрии прямо жуть какая активная

Цитата:

43 23.15 Gennady Gusev Rybinsk, Russia 31 Mar 2013 16:57
44 23.07 Alexandra Chrysothemis Salzburg, Austria 7 Apr 2013 02:43

но пока нашего Геннадия не обогнала

-- Вс апр 07, 2013 13:17:52 --

Наши в клубе 23+

Цитата:

19 24.00 Vladimir Chirkov Bobruisk, Russia 26 Mar 2013 12:35
23 23.77 Alex Chernov Penza, Russia 27 Feb 2013 10:40
29 23.68 Kalachev Gleb Moscow, Russia 3 Feb 2013 16:52
32 23.61 Viktor Polesov Moskow, Russia 7 Apr 2013 09:02
43 23.15 Gennady Gusev Rybinsk, Russia 31 Mar 2013 16:57

Владимира Чиркова тоже в этот клуб записала, ибо 24 балла --- это ещё не 24+

Vovka17
ау!
Вам пора вступать в клуб 24+

Очень жалко, что Алексей Чернов замолчал, аж 27 февраля введены последние результаты. Ещё раньше прекратил вводить результаты Калачев Глеб.

[Pavlovsky]

11 24.47 Dmitry Kamenetsky Adelaide, Australia 14 Mar 2013 22:17
12 24.46 Lucien Pech Zürich, Switzerland 30 Mar 2013 17:40
13 24.42 Valery Pavlovsky Ekaterinburg, Russia 7 Apr 2013 04:37
14 24.41 Ashley Wood Guildford, United Kingdom 4 Apr 2013 22:13
15 24.40 Michael Hürter Saarbrücken, Germany 6 Apr 2013 20:17
16 24.37 Andy Sloane Sunnyvale, California, United States 8 Feb 2013 21:39

Очень плотная группа. Надо из нее быстрее выбираться, а то затопчут.
Для меня конкурс закончен. Больше ничего делать не буду. Пусть работает компьютер. Если что то найдет, хорошо. Нет, значит судьба.