Factorials

[whitefox]

wanderers
Поскольку Ваша дискуссия с Nataly-Mak уже перешла на личности, полагаю её завершённой, и задам свой вопрос.

wanderers в сообщении #713853 писал(а):

Хотел бы уточнить метод хранения записей в моей базе данных: они хранятся в виде буквы "T". Например, для n = 3, сначала идут 1 и 2, а потом "шляпка" в виде 3-ки и 4-ки.

То есть каждая запись в вашей базе состоит из двух частей, первая часть это ветвь, а вторая листья?
Например, для ветви (1,2,3) Вы храните ещё множество листьев {4,5,6,9}?

[Nataly-Mak]

wanderers в сообщении #713971 писал(а):

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

Это разложение

$23! = 322\cdot (322+1) \cdot 12636 \cdot 4435200^2$

можно записать и так:

$23! = 323\cdot (323-1) \cdot 12636 \cdot 4435200^2$

Никакой разницы нет абсолютно.

Формальная разница есть: это два различных решения. И далеко не всегда существуют решения: одно - с плюсом, а другое - с минусом.

У вас есть пример, подтверждающий, что не всегда существуют решения: одно - с плюсом, а другое - с минусом?
Или вы можете это доказать теоретически?

[wanderers]

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

wanderers
Поскольку Ваша дискуссия с Nataly-Mak уже перешла на личности, полагаю её завершённой, и задам свой вопрос.

wanderers в сообщении #713853 писал(а):

Хотел бы уточнить метод хранения записей в моей базе данных: они хранятся в виде буквы "T". Например, для n = 3, сначала идут 1 и 2, а потом "шляпка" в виде 3-ки и 4-ки.

То есть каждая запись в вашей базе состоит из двух частей, первая часть это ветвь, а вторая листья?
Например, для ветви (1,2,3) Вы храните ещё множество листьев {4,5,6,9}?

Совершенно правильно полагаете. По поводу хранения Вы правы: еще раз подчеркну, что такое представление данных позволяет эффективно (т.е. очень быстро) генерировать новые записи без их дубляжа, что очень важно, так как эти самые записи плодятся быстрей кроликов.

[Nataly-Mak]

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

wanderers
Поскольку Ваша дискуссия с Nataly-Mak уже перешла на личности, полагаю её завершённой, и задам свой вопрос.

Вы ошибаетесь, у меня есть ещё к wanderers вопросы
Но это нисколько не мешает вам задавать свои вопросы.

-- Пн апр 22, 2013 15:05:22 --

wanderers в сообщении #714050 писал(а):

Совершенно правильно полагаете.

Нет, не правильно! Вы не ответили мне ещё на два вопроса по существу.
Потрудитесь, пожалуйста, ответить.

-- Пн апр 22, 2013 15:17:29 --

Формулирую вопрос в общем виде.

Известно, что существует решение в q шагов для разложения

$N! = A(A+1)CB^2$

Следует ли отсюда, что существует также решение в q шагов для разложения:

$N! = (A+1)ACB^2$

Пример, когда не следует. Или теоретическое доказательство того, что не следует.

Частный случай уже приведён выше, но повторю на всякий случай:

$23! = 322\cdot (322+1) \cdot 12636 \cdot 4435200^2$
$23! = 323\cdot (323-1) \cdot 12636 \cdot 4435200^2$

-- Пн апр 22, 2013 15:36:18 --

Я подумала...
У меня получается, что это всегда следует.
Доказательство привести?

wanderers
я жду ваш ответ.
Вы будете утверждать, что далеко не всегда существуют решения - одно с плюсом, а другое с минусом?

Тогда давайте доказательство этого утверждения.

[whitefox]

wanderers

wanderers в сообщении #713672 писал(а):

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

Что именно Вы включаете в число этих десяти членов?
В приведённом примере ветви (1,2,3), состоит ли запись из трёх членов?
Или только из одного (3)? Так как (1,2) входят во всякую ветвь.
Как учтены листья {4,5,6,9}?

wanderers в сообщении #713672 писал(а):

При этом использовалась техника быстрой генерации неповторяющихся записей

Нельзя ли поподробнее?
Ветви (1,2,3,4) и (1,2,4,3) имеет одни и те же листья.
Можете показать как Ваша техника устраняет этот дубляж?

[Nataly-Mak]

На всякий случай запишу второе разложение в виде:

$N! = (A+1)((A+1)-1)CB^2$

Более точно!

[wanderers]

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

wanderers

wanderers в сообщении #713672 писал(а):

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

Что именно Вы включаете в число этих десяти членов?
В приведённом примере ветви (1,2,3), состоит ли запись из трёх членов?
Или только из одного (3)? Так как (1,2) входят во всякую ветвь.
Как учтены листья {4,5,6,9}?

wanderers в сообщении #713672 писал(а):

При этом использовалась техника быстрой генерации неповторяющихся записей

Нельзя ли поподробнее?
Ветви (1,2,3,4) и (1,2,4,3) имеет одни и те же листья.
Можете показать как Ваша техника устраняет этот дубляж?

1 и 2 не хранятся. Старт генерации базы начинается с n=3, т.е. при старте первая часть записи состоит только из информационного члена, а вторая содержит два числа: 3, 4. Дальше все на автомате. По поводу быстрой генерации не хотелось бы распространяться.

[Nataly-Mak]

Цитата:

Формальная разница есть: это два различных решения. И далеко не всегда существуют решения: одно - с плюсом, а другое - с минусом.

Цитата:

У вас есть пример, подтверждающий, что не всегда существуют решения: одно - с плюсом, а другое - с минусом?
Или вы можете это доказать теоретически?

wanderers
игнорирование вопросов оппонента не есть правильное поведение.
Я повторяю вопрос.
Докажите, что ваше утверждение верно.
У меня есть доказательство обратного. Я могу ошибаться.
Хочу увидеть ваше доказательство.

[dimkadimon]

wanderers в сообщении #713984 писал(а):

Угу, за всю жизнь в университете была только одна четверка по физике (из точных наук) и то только за то, что профессору Толстому (сыну писателя) не понравилось, что я отвечал не по его лекциям.

Правда сын Льва Толстого? Я не знал что у него был сын профессор по физике. Последний сын Толстого умер в 1945 году. Если вы учились в университете в это время, то вам должно быть около 90 лет...

[whitefox]

wanderers в сообщении #714080 писал(а):

По поводу быстрой генерации не хотелось бы распространяться.

Ну а я секретничать не буду.

Продемонстрирую алгоритм на примере ветви (1,2,3).
Впрочем, ветвь хранится в виде множества своих узлов {1,2,3}, что автоматически устраняет дубляж ветвей (1,2,3,4) и (1,2,4,3).

И так, в базе имеется запись (1,2,3){4,5,6,9}.
Выполняем цикл по всем листьям, в котором:
1. выбираем очередной лист, например 4;
2. создаём новую запись;
3. в первую часть записи заносим родительскую ветвь дополненную выбранным листом, в нашем примере (1,2,3,4);
4. во вторую часть записи заносим всех братьев выбранного листа, в примере {5,6,9};
5. выбранный лист комбинируем со всеми узлами новой ветви используя операции +,-,*;
6. полученные на шаге 5 числа добавляем во вторую часть записи, в примере получим {5,6,7,8,9,12,16}.

В результате первой итерации цикла в базу будет добавлена запись:
(1,2,3,4){5,6,7,8,9,12,16}.

-- 22 апр 2013, 16:42 --

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

Правда сын Льва Толстого?

Наверно, Алексея Толстого?

[Nataly-Mak]

(Оффтоп)

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

Ну а я секретничать не буду.

Сразу видно - не завистник

[Pavlovsky]

Анализирую задачи, где не смог найти оптимальное решение. Обидно ведь был совсем рядом.
N=37
Начальная последовательность: 1,2,4,6,36,216,210,220,45360,9979200,10024560
Разложение: 37!=10024780*174*10024560^2*220*9979200^2*224*4^2 длина = 20

Последовательность 1,2,4,6,36,216,210,220 была у меня в списке переспективных. Но не задолго до окончания конкурса я исключил из поиска N=35,37 как приносящие слишком мало очков.

N=36
Вот это очень обидно. Вот мое решение:
1,2,4,6,36,35,216,220,864,899,31465, 31464, 30240, 6652800, 6683040, 44460928512000, 1976774164149174534144000000, 28286136, 188182005580800, 371993326789901217467999448150835200000000
36!=899*31464*221^2*220^3*35^5*864^5
Одно преобразование я увидел 221^2*220^3*(35*864)^5=(220*35*864+35*864)^2*(220*35*864)^3
Но оказывается в разложении было и второе преобразование: 899*31464=899*(899*35-1). Блин надо было автоматизировать поиск преобразований, это же было не трудно.

[Nataly-Mak]

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

wanderers
игнорирование вопросов оппонента не есть правильное поведение.
Я повторяю вопрос.
Докажите, что ваше утверждение верно.
У меня есть доказательство обратного. Я могу ошибаться.
Хочу увидеть ваше доказательство.

Хорошо, я привожу своё доказательство.

Известно, что существует решение в q шагов для разложения

$N! = A(A+1)CB^2=AB(AB+B)C$

Это означает, что существует последовательность из (q-3) членов, содержащая числа A, B, C, которую потом завершаем в 4 операции.

Докажем, что тогда существует решение в q шагов и для разложения

$N! = (A+1)((A+1)-1)CB^2$

Преобразуем это разложение:

$N! = (A+1)((A+1)-1)CB^2=(A+1)B((A+1)B-B)C=(A+1)BABC=AB(AB+B)C$

Сравните с первым разложением.
Дальше всё понятно.

Если моё доказательство не верно, пусть другие участники темы меня поправят.

wanderers
подвожу итоги нашей дискуссии:
1. вы напрасно "наехали" на моё решение для 23!
В этом решении нет никакой лишней операции, в нём 15 шагов, как и должно быть.
2. вы сделали опечатку (x=223) и не соблаговолили это признать.
3. вы сморозили глупость по поводу решений "с плюсом" и "с минусом". Если бы это было не так, вы привели бы доказательство своего утверждения.

Теперь я тоже считаю дискуссию завершённой и заношу вас в список игнорируемых пользователей (будем игнорировать друг друга взаимно).

[wanderers]

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

wanderers в сообщении #714080 писал(а):

По поводу быстрой генерации не хотелось бы распространяться.

Ну а я секретничать не буду.

Продемонстрирую алгоритм на примере ветви (1,2,3).
Впрочем, ветвь хранится в виде множества своих узлов {1,2,3}, что автоматически устраняет дубляж ветвей (1,2,3,4) и (1,2,4,3).

И так, в базе имеется запись (1,2,3){4,5,6,9}.
Выполняем цикл по всем листьям, в котором:
1. выбираем очередной лист, например 4;
2. создаём новую запись;
3. в первую часть записи заносим родительскую ветвь дополненную выбранным листом, в нашем примере (1,2,3,4);
4. во вторую часть записи заносим всех братьев выбранного листа, в примере {5,6,9};
5. выбранный лист комбинируем со всеми узлами новой ветви используя операции +,-,*;
6. полученные на шаге 5 числа добавляем во вторую часть записи, в примере получим {5,6,7,8,9,12,16}.

В результате первой итерации цикла в базу будет добавлена запись:
(1,2,3,4){5,6,7,8,9,12,16}.

-- 22 апр 2013, 16:42 --

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

Правда сын Льва Толстого?

Наверно, Алексея Толстого?

Я бы не назвал предложенный Вами метод быстрой генерацией (идея находится совсем в другой плоскости). По поводу Толстого Вы правы: такой же был породистый и самовлюбленный барин.

[whitefox]

wanderers в сообщении #714112 писал(а):

Я бы не назвал предложенный Вами метод быстрой генерацией.

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