2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 72, 73, 74, 75, 76, 77, 78 ... 88  След.
 
 Re: Factorials
Сообщение01.05.2013, 15:09 


02/11/12
141
Natalya, it was a memory error that I fixed.

The Run button is where I test. I was working on A216999. I will remove the button when I figure out Natalya's odd number problem.

Код:
326876 = 2^2 * 11 * 17 * 19 * 23


sequences can only have the numbers 1, 2, 4, 11, 17, 19, 23. none are possible.

Код:
1,2,4,5 no
1,2,4,6 no
1,2,4,8 no
1,2,4,16 no

 Профиль  
                  
 
 Re: Factorials
Сообщение01.05.2013, 15:16 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Ещё решения для числа 4200 в 9 шагов (ограничение: только чётные числа):

Код:
...
1,2,4,6,36,30,35,1050,1225,4200
1,2,4,6,36,30,35,1050,2100,4200
1,2,4,6,36,30,35,1050,5,4200
1,2,4,6,36,30,35,1080,1050,4200
1,2,4,6,36,30,35,1080,140,4200
1,2,4,6,36,30,35,120,1050,4200
1,2,4,6,36,30,35,120,1080,4200
...

Тут вообще чудеса :D
В этом решении:
Код:
1,2,4,6,36,30,35,1080,1050,4200

зачем число 35 нужно :?:
Мало того, что оно нечётное, так оно и совсем здесь без надобности.
Ведь решение прекрасно получается и без числа 35:

Код:
1,2,4,6,36,30,1080,1050,4200

Правда, это решение уже не в 9 шагов, а в 8.

Так сколько же фактически будет решений для числа 4200 в 9 шагов, если решения составляются только из чётных чисел :?:
Интересный вопрос.
Кто-нибудь знает ответ? :D

 Профиль  
                  
 
 Re: Factorials
Сообщение01.05.2013, 15:21 
Заслуженный участник
Аватара пользователя


19/12/10
1546
mertz
Вот решение для 326876 состоящее только из делителей 28!
Код:
1, 2, 4, 8, 64, 72, 70, 4900, 5184, 331776, 326876
Именно его я хотел найти, но обрезка Non-Factor ищет решения состоящие только из делителей 326876.

А что ответите про Chain Search?

 Профиль  
                  
 
 Re: Factorials
Сообщение01.05.2013, 15:30 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
whitefox в сообщении #718260 писал(а):
Вот решение для 326876 состоящее только из делителей 28!
Код:
1, 2, 4, 8, 64, 72, 70, 4900, 5184, 331776, 326876

Именно его я хотел найти, но обрезка Non-Factor ищет решения состоящие только из делителей 326876.[/code]

Извините, что вмешиваюсь.
Вы, значит, хотите, чтобы при поиске числа 326876 учитывались только делители 28! :?:
Хорошее требование :-)

 Профиль  
                  
 
 Re: Factorials
Сообщение01.05.2013, 15:37 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Nataly-Mak в сообщении #718265 писал(а):
Вы, значит, хотите, чтобы при поиске числа 326876 учитывались только делители 28! :?:
Хорошее требование :-)

Решение для числа 326876 ищется не само по себе, а как часть решения для 28!
Логично чтобы оно строилось из делителей 28!

 Профиль  
                  
 
 Re: Factorials
Сообщение01.05.2013, 15:38 


02/11/12
141
Цитата:
It means that you want to search for the number 326876 into account only the divisors of 28! Good call


I could add an option to select your factor number.

 Профиль  
                  
 
 Re: Factorials
Сообщение01.05.2013, 15:44 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
whitefox в сообщении #718270 писал(а):
Решение для числа 326876 ищется не само по себе, а как часть решения для 28!
Логично чтобы оно строилось из делителей 28!

Ну да, и я говорю: хорошее требование.
Однако... реализация его, как мне кажется, не совсем проста.
Надо проверять все делители 28!, которых не так мало.

 Профиль  
                  
 
 Re: Factorials
Сообщение01.05.2013, 15:46 
Заслуженный участник
Аватара пользователя


19/12/10
1546
mertz в сообщении #718271 писал(а):
I could add an option to select your factor number.

Думаю это будет полезно. :-)

-- 01 май 2013, 16:50 --

Nataly-Mak в сообщении #718277 писал(а):
Надо проверять все делители 28!, которых не так мало.

Не очень.
Всего 882000.

 Профиль  
                  
 
 Re: Factorials
Сообщение01.05.2013, 15:56 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
whitefox
сейчас проверила: решений для числа 326876 в 10 шагов, состоящих только из чётных чисел, всего 67.
Это хвост массива решений:

Код:
...
1,2,4,8,10,64,4096,4086,32688,326880,326876
1,2,4,8,10,64,4096,4086,40860,326880,326876
1,2,4,8,10,64,80,4096,4086,326880,326876
1,2,4,8,64,68,72,4608,4540,326880,326876
1,2,4,8,64,72,4608,4536,4540,326880,326876
1,2,4,8,64,72,4608,4544,4540,326880,326876
1,2,4,8,64,72,4608,4604,331488,326880,326876
1,2,4,8,64,72,4608,4604,331488,326884,326876
1,2,4,8,64,72,4608,4604,331488,331480,326876
1,2,4,8,64,72,4608,4604,331488,331484,326876
1,2,4,8,64,72,4608,4604,4540,326880,326876
1,2,4,8,64,72,4608,4612,4540,326880,326876
1,2,4,8,64,72,4608,4612,4604,331488,326876
1,2,4,8,64,72,70,4608,4900,331776,326876
1,2,4,8,64,72,70,5184,4900,331776,326876
1,2,4,8,64,72,70,576,4900,331776,326876
1,2,4,8,64,72,70,576,646,506,326876

Решение, приведённое вами, здесь есть.
Зачем вам обрезка по Non-Factor да ещё не для самого числа 326876, а для 28! :?:

Если можно, покажите, что вы дальше делаете с показанным вами решением для числа 326876 в 10 шагов (с указанной обрезкой)? Вы получаете из него оптимальное решение для 28! :?:

Между делом, запустила поиск решения для 28! от этой вашей последовательности. Так просто, интересно --- достроится или нет? Хотя здесь добавляется аж 6 шагов, что у меня за разумное время не выполняется программой.
Я ввела оба ограничения: только делители 28! и только чётные числа.

 Профиль  
                  
 
 Re: Factorials
Сообщение01.05.2013, 16:08 


02/11/12
141
New version. Fixed odd number in even only solutions. Fixed a crash caused by a misplaced Mutex. Same links as before.

 Профиль  
                  
 
 Re: Factorials
Сообщение01.05.2013, 16:12 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
mertz
быстро вы работаете.
Я не успеваю тестировать новые версии :D
Спасибо!

 Профиль  
                  
 
 Re: Factorials
Сообщение01.05.2013, 16:13 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Nataly-Mak в сообщении #718284 писал(а):
сейчас проверила: решений для числа 326876 в 10 шагов, состоящих только из чётных чисел, всего 67.
Зачем вам обрезка по Non-Factor да ещё не для самого числа 326876, а для 28! :?:

Если можно, покажите, что вы дальше делаете с показанным вами решением для числа 326876 в 10 шагов (с указанной обрезкой)? Вы получаете из него оптимальное решение для 28! :?:

Очень эффективной оказалась эвристика -- строить решение для N! только из делителей N!

Так как $28! =1651104000^2\cdot326876\cdot342144$ и все три числа делят 28!, найдём решение для 326876 состоящее только из делителей 28!, продолжим его до 342144 (также используя только делители 28!), полученную последовательность продолжаем до 1651104000 (опять используя только делители 28!), выполняем три завершающих умножения и получаем решение для 28! состоящее только из делителей 28!

1, 2, 4, 8, 64, 72, 70, 4900, 5184, 331776, 326876
1, 2, 4, 8, 64, 72, 70, 4900, 5184, 331776, 326876, 336960, 342144
1, 2, 4, 8, 64, 72, 70, 4900, 5184, 331776, 326876, 336960, 342144, 1651104000
1, 2, 4, 8, 64, 72, 70, 4900, 5184, 331776, 326876, 336960, 342144, 1651104000, 2726144418816000000, 891111183044898816000000, 304888344611713860501504000000

 Профиль  
                  
 
 Re: Factorials
Сообщение01.05.2013, 16:22 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
whitefox в сообщении #718294 писал(а):
Очень эффективной оказалась эвристика -- строить решение для N! только из делителей N!

Так как $28! =1651104000^2\cdot326876\cdot342144$ и все три числа делят 28!, найдём решение для 326876 состоящее только из делителей 28!, продолжим его до 342144 (также используя только делители 28!), полученную последовательность продолжаем до 1651104000 (опять используя только делители 28!), выполняем три завершающих умножения и получаем решение для 28! состоящее только из делителей 28!

1, 2, 4, 8, 64, 72, 70, 4900, 5184, 331776, 326876

Итак, от найденных мной 67 решений для числа 326876 в 10 шагов (состоящих только из чётных чисел) выполняю первый этап по вашему сценарию: достраиваю до числа 342144:

Код:
found 3 solutions for 342144 in 12 steps
1,2,4,8,64,72,70,5184,4900,331776,326876,10368,342144
1,2,4,8,64,72,70,5184,4900,331776,326876,336960,342144
1,2,4,8,64,72,70,5184,4900,331776,326876,66,342144

[ограничение Non-Factor не действует здесь]
Сейчас пойду выполнять от найденных решений второй этап - достраивание до числа 1651104000.
Получится? :D

А почему же не получится?
Вот оно:

Код:
found 1 solutions for 1651104000 in 13 steps
1,2,4,8,64,72,70,5184,4900,331776,326876,336960,342144,1651104000

Вывод: совершенно напрасно вы морочили голову с обрезкой Non-Factor (да ещё по делителям 28!). Всё прекрасно получается с одним ограничением: только чётные числа. Решений очень мало даже на первом этапе - всего 67.

-- Ср май 01, 2013 17:34:16 --

Обалдеть :D
Программа поиска решений от вашей последовательности для числа 326876 закончила работу!
Программа работала всего 39 мин. 15 сек. Фантастика!

Код:
found 9 solutions for 304888344611713860501504000000 in 16 steps
1,2,4,8,64,72,70,4900,5184,331776,326876,336960,1651104000,342144,111838662144,184657262420606976000,304888344611713860501504000000
1,2,4,8,64,72,70,4900,5184,331776,326876,336960,1651104000,342144,2726144418816000000,111838662144,304888344611713860501504000000
1,2,4,8,64,72,70,4900,5184,331776,326876,336960,1651104000,342144,2726144418816000000,891111183044898816000000,304888344611713860501504000000
1,2,4,8,64,72,70,4900,5184,331776,326876,336960,1651104000,342144,2726144418816000000,932733956031381504000000,304888344611713860501504000000
1,2,4,8,64,72,70,4900,5184,331776,326876,336960,1651104000,342144,539706271104000,184657262420606976000,304888344611713860501504000000
1,2,4,8,64,72,70,4900,5184,331776,326876,336960,1651104000,342144,539706271104000,564915326976000,304888344611713860501504000000
1,2,4,8,64,72,70,4900,5184,331776,326876,336960,1651104000,342144,539706271104000,891111183044898816000000,304888344611713860501504000000
1,2,4,8,64,72,70,4900,5184,331776,326876,336960,1651104000,342144,564915326976000,184657262420606976000,304888344611713860501504000000
1,2,4,8,64,72,70,4900,5184,331776,326876,336960,1651104000,342144,564915326976000,932733956031381504000000,304888344611713860501504000000

Вот! Сразу в лоб от числа 326876 достроилось до 28!
И можно точно так же достроить, начиная от всех 67 решений для числа 326876, только в этом случает программа будет намного дольше выполняться.

P.S. Интересно: в этих решениях сначала найдено число 1651104000, а потом число 342144.

 Профиль  
                  
 
 Re: Factorials
Сообщение01.05.2013, 16:53 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Nataly-Mak в сообщении #718299 писал(а):
Вывод: совершенно напрасно вы морочили голову с обрезкой Non-Factor (да ещё по делителям 28!). Всё прекрасно получается с одним ограничением: только чётные числа. Решений очень мало даже на первом этапе - всего 67.

В данном частном случае всё прекрасно получается и без каких-либо ограничений.
На моей машине за три минуты находятся все 187 решений в 10 шагов для 326876, за несколько секунд они достраиваются до 5 решений в 12 шагов для 342144, а достройка до одного решения в 13 шагов для 1651104000 выполняется вообще мгновенно.

Всё дело в том, что нам известно, что разложение $28! =1651104000^2\cdot326876\cdot342144$ даёт оптимальное решение.
Но когда такой информации нет, пространство поиска слишком велико, и разумно использовать упомянутую выше эвристику для его существенного сокращения.

-- 01 май 2013, 18:07 --

Выше Вы описывали с какими трудностями столкнулись при поиске решения для 22!
Их бы не было ищи Вы решение для 4200 состоящее из делителей 22! и продолжив затем его до решения для 7983360, также состоящее из делителей 22!
1,2,4,6,24,144,864,840,5040,4200,9240,7983360

 Профиль  
                  
 
 Re: Factorials
Сообщение01.05.2013, 17:10 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
whitefox в сообщении #718315 писал(а):
Всё дело в том, что нам известно, что разложение $28! =1651104000^2\cdot326876\cdot342144$ даёт оптимальное решение.
Но когда такой информации нет, пространство поиска слишком велико, и разумно использовать упомянутую выше эвристику для его существенного сокращения.

Стоп! Не поняла юмора :D
Что изменилось бы в показанном мной поиске, если бы у меня не было "такой информации" (что оптимальное решение для данного разложения существует)???
Ровным счётом ничего не изменилось бы!

-- Ср май 01, 2013 18:14:21 --

whitefox в сообщении #718315 писал(а):
Выше Вы описывали с какими трудностями столкнулись при поиске решения для 22!
Их бы не было ищи Вы решение для 4200 состоящее из делителей 22! и продолжив затем его до решения для 7983360, также состоящее из делителей 22!
1,2,4,6,24,144,864,840,5040,4200,9240,7983360

Если вы внимательно читали эти самые описанные мной трудности, то должны были бы заметить, что и в этом примере я прекрасно вышла из положения, введя ограничение при поиске решений для числа 4200 в 9 шагов - только чётные числа!
И это дало решение за считанные минуты.
Никаких ограничений по делителям 22! я не использовала.

Nataly-Mak в сообщении #718112 писал(а):
И вот! Чего не сообразила :-( надо было искать решения для числа 4200 в 9 шагов только с чётными числами!
Ищу сейчас такие решения, программа выдаёт всего 4332 решения.

Теперь беру эти 4332 решения для числа 4200 и достраиваю их до числа 7983360 в два шага.
Вот они - эти решения:

Код:
found 2 solutions for 7983360 in 11 steps
1,2,4,6,24,144,864,840,5040,4200,9240,7983360
1,2,4,6,24,36,864,840,5040,4200,9240,7983360


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1310 ]  На страницу Пред.  1 ... 72, 73, 74, 75, 76, 77, 78 ... 88  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group