Factorials

[Pavlovsky]

Впрочем начало 1,2,4,6,36,144 тоже не плохое.

-- Вт фев 26, 2013 12:40:21 --

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

Для этого число В тоже факторизуйте.

Заменить одну операцию A mod B на кучу операций B mod p при факторизации B?!

[Nataly-Mak]

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

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

Поэтому рекомендую начинать с 1, 2, 4, 6.

Мне с моего 54-го места трудно с вами спорить. При постороении последовательности рано или поздно у нас должны появиться числа делителями которых являются все простые числа от 2 до <=N. Но зачем с этим торопиться?! Зачем получать число 6 делителем которого является 3 на третьем шаге?

Начало 1,2,4,16 выглядит куда более переспективным.

У dimkadimon статистика. И статистика эта верная.
Например, из 56 решений для N=14 только 3 решения начинаются с
1,2,4,16...
остальные 53 решения начинаются с
1,2,4,6...

[Pavlovsky]

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

У dimkadimon статистика

Есть ложь. Есть наглая ложь. А есть статистика.

[Nataly-Mak]

Pavlovsky в сообщении #688350[quote="Nataly-Mak в [url=http://dxdy.ru/post688345.html#p688345]сообщении #688345 писал(а):

Для этого число В тоже факторизуйте.

Цитата:

Заменить одну операцию A mod B на кучу операций B mod p при факторизации B?!

Блин!
У меня всё просто! Как я уже сказала, вообще без программ.
Пользуюсь только программой факторизации (интернетовской).

И для 37! решение давно нашла, разумеется, не оптимальное (25 шагов).

-- Вт фев 26, 2013 11:46:22 --

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

Например, из 56 решений для N=14 только 3 решения начинаются с
1,2,4,16...
остальные 53 решения начинаются с
1,2,4,6...

Это не ложь и не статистика. Это факт!

[Pavlovsky]

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

Это не ложь и не статистика. Это факт!

Убедили. Буду рассматривать только последовательности начинающиеся с 1,2,4,16. Буду плыть против течения!

[Nataly-Mak]

(Оффтоп)

Вы вроде не женщина; басню Ломоносова вспомнила, как муж искал утонувшую в реке жену...

[Pavlovsky]

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

[Nataly-Mak]

Плюньте на тормознутую платформу программирования
Пользуйтесь ЕИ.
У меня ещё более тормознутая платформа - древний язык Бейсик, но я не жалуюсь. Где Бейсик не умеет, я кластер подключаю

Правда, следует сказать, что у меня почти всегда есть добровольные помощники.
В этот раз таким помощником явился mertz, причём абсолютно добровольно! У меня и в мыслях не было просить его о помощи, а он вдруг ни с того, ни с сего прислал мне свою программу (о чём рассказано выше).

Кстати, вчера получила новую версию второй программы (решатель, ищет решения для любого числа в пределах 10 шагов).
mertz пишет, что поработал над скоростью выполнения и новая версия работает в два раза быстрее.
Я попробовала эту версию, на картинке поиск решений для числа 10400600 в 10 шагов. На моей маломощной машине (2 ядра) поиск занял 22 минуты, найдено 192 решения. Класс!

[Nataly-Mak]

Пошла ва-банк Уже всё перепробовала в поиске решений для 19!
16 шагов всё время хоть застрелись.

Наконец-то получила решение в 15 шагов. Люди в 13 шагов нашли, а я рада и 15 шагам

Решение по-прежнему основано на представлении
19! = K*(9!)^2 = 923780*(9!)^2

Итак, иду ва-банк: нахожу все решения для числа 923780 в 10 шагов. Таких решений программа mertz нашла 66 штук.
Теперь берём одно из решений для 9!, например:

1,2,4,16,18,72,70,5040,362880

Добавляем (9!)^2

1,2,4,16,18,72,70,5040,362880,131681894400

Решение будет заканчиваться одним умножением - на число 923780.
Осталось вставить в последовательность подпоследовательность формирования числа 923780 (эту подпоследовательность ищем среди решений для этого числа) и готовое решение имеет вид:

1,2,4,16,18,72,70,5040,362880,131681894400,...,19!

Уф! Ура, ура

Таким образом, в этом алгоритме требуется найти самое короткое представление числа 923780 с использованием чисел начальной последовательности (в качестве начальной последовательности можно выбирать любое решение для 9!).
Для решения в 13 шагов эта подпоследовательность должна содержать всего 3 члена (не знаю, возможно ли это). В моём решении из 15 шагов подпоследовательность содержит 5 членов.

[Pavlovsky]

1,2,4,16 Плывете против фактов и статистики????

[Nataly-Mak]

Я женщина!

К тому же, у меня не оптимальное решение.

[Pavlovsky]

У меня для 19! тоже не оптимальное 14 шагов. Но начинается с 1,2,4,16. Сейчас общими усилиями поправим статистику, хотя бы для не оптимальных решений.

[Nataly-Mak]

Ну, не оптимальные решения с чего угодно могут начинаться.
У меня есть несколько решений для 19! - от 17 до 15 шагов:

1,2,3,9 - 17 шагов
1,2,3,9 - 16
1,2,4,5 - 16
1,2,4,6 - 16
1,2,4,16 - 16
1,2,4,16 - 15

Если добавить результат Pavlovsky в 14 шагов 1,2,4,16
то в этой статистике лидирует начало 1,2,4,16.

Такая задача: существует ли решение следующего уравнения в целых числах:
$923780=x^2+x$

[Pavlovsky]

Анализирую свое не оптимальное решение для 30! - 19 операций.
Начинается 1,2,4,16,256. Далее идет 7 операций сложения/вычитания. Завершает последовательность 8 операций умножения.

-- Вт фев 26, 2013 17:42:20 --

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

Такая задача: существует ли решение следующего уравнения в целых числах:
$923780=x^2+x$

Вольфрам вам поможет. Не существует.

[Nataly-Mak]

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

Вольфрам вам поможет. Не существует.

Это где?
Спасибо. Жаль, что не существует.
Подобные уравнения весьма актуальны в этой задаче.
Я уже приводила пример:
104006=322^2+322