Factorials

[Nataly-Mak]

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

Я понимаю так, что эта аддитивная последовательность даёт нам только схему умножения для 2^994.
А как сюда присоединить умножение на другие простые числа?

Pavlovsky
а ответ на этот вопрос будет?
Если я сморозила глупость, вы так и скажите, не стесняйтесь
А вот оставлять вопросы без ответа как-то... не очень...
Вы же знаете моё отношение к этому.

Напомню, о чём речь:

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

Выпишем степени простых чисел из разложения на простые множители 1000!

994,498,249,164,98,81,61,54,44,35,33,27,24,23,21,18,16,14,13,12,11,10,9,8,7,6,5,4,3,2,1

Если бы эта последовательность была аддитивной (показанная последовательность написана задом на перед), тогда по теореме Оливоса у нас было бы 162 умножения. А так придется в последовательность добавить еще несколько чисел, что бы последовательность стала аддитивной. Надо добавить совсем немного 5-6 чисел.

-- Вт апр 23, 2013 10:03:03 --

Ой соврал. умножений потребуется 2*162=324 плюс накладные расходы. Итоговая длина последовательности получается 3*162=486 плюс накладные расходы. Много!

Я рассуждаю на основе этого примера из Википедии.
Дана аддитивная последовательность:

v = (1,2,3,6,12,24,30,31)

Далее:

Цитата:

Addition chains can be used for addition-chain exponentiation:
so for example we only need 7 multiplications to calculate $5^{31}$:

5^2 = 5^1 × 5^1
5^3 = 5^2 × 5^1
5^6 = 5^3 × 5^3
5^12 = 5^6 × 5^6
5^24 = 5^12 × 5^12
5^30 = 5^24 × 5^6
5^31 = 5^30 × 5^1

Мои рассуждения не верны?

[Pavlovsky]

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

Я понимаю так, что эта аддитивная последовательность даёт нам только схему умножения для 2^994.
А как сюда присоединить умножение на другие простые числа?

Pavlovsky
а ответ на этот вопрос будет?

Этот вопрос мы подробно обсуждали, когда разбирались с теоремой Оливоса. И даже слегка повздорили по этому поводу. Начинать все сначала?!

[Nataly-Mak]

Да, уж будьте так добры.

У меня вопрос: как по приведённой вами почти аддитивной последовательности перемножить все степени различных простых чисел?

994,498,249,164,98,81,61,54,44,35,33,27,24,23,21,18,16,14,13,12,11,10,9,8,7,6,5,4,3,2,1

Я вижу только способ найти 2^994.

А, я вижу также способ найти 3^498, потом найти 5^249, 7^164 и т.д.
Но потом-то все эти степени надо перемножить.

1000! = a1^k1*a2^k2*a3^k3*...*an^kn

Для каждого am^km имеем по аддитивной последовательности m умножений.
Так, может быть, по теореме Оливоса, всего умножений будет не 324 всё-таки?

Ну, зашла могзга за мозгу у меня
Так разъясните, пожалуйста, как тут всё перемножить?

[Pavlovsky]

Как применять теорему Оливоса не строя оргграф. На примере 13!
Пусть мы построили последовательность где есть все простые числа от 2 до 13
1,2,3,5,7,4,11,13
Разложение на простые множители:
13!=2^10×3^5×5^2×7×11×13

Постепенно начинаем избавляться от старших степеней в разложении. Для этого используем оперецию A^k=A^k1*A^k2, где k=k1+k2. Желательно,чтобы k1,k2 уже есть в нашем разложении. В этом случае дополнительных операций не возникает.

1) 2^10=2^5*2^5
13!=(2*2*3)^5×5^2×7×11×13=12^5×5^2×7×11×13
1,2,3,5,7,4,11,13,12
2) 12^5=12^3*12^2
13!=12^3×(12*5)^2×7×11×13=12^3×60^2×7×11×13
1,2,3,5,7,4,11,13,12,60
3)12^3=12^2*12
13!=(12*60)^2×(12*7×11×13)=720^2×12012
1,2,3,5,7,4,11,13,12,60,720,84,924,12012
4) Далее все элементарно
1,2,3,5,7,4,11,13,12,60,720,84,924,12012,518400,6227020800

[Nataly-Mak]

Блин!
Вы можете на примере с 1000! пояснить?
Я вам пишу, пишу про этот пример.
А вы мне пример про 13!

Откуда вы взяли, что умножений будет 324? Это вы уже избавились от всех старших степеней простых чисел так быстро и выяснили, что умножений будет 324?

[Pavlovsky]

Все так же постепенно избавляемся от старших степеней.
$1000!=2^{994}*3^{498}*5^{249}*7^{164}*11^{98}*13^{81}*17^{61}*19^{54}*23^{44} *29^{35}*31^{33}*37^{27}*41^{24}*43^{23}*47^{21}*53^{18}*59^{16}*61^{16}*67^{14} *71^{14}*73^{13}*79^{12}*83^{12}*89^{11}*97^{10}*101^9*103^9*107^9*109^9*113^8*127^7 *131^7*137^7*139^7*149^6*151^6*157^6*163^6*167^5*173^5*179^5*181^5*191^5*193^5*197^5 *199^5*211^4*223^4*227^4*229^4*233^4*239^4*241^4*251^3*257^3*263^3*269^3*271^3*277^3 *281^3*283^3*293^3*307^3*311^3*313^3*317^3*331^3*337^2*347^2*349^2*353^2*359^2*367^2 *373^2*379^2*383^2*389^2*397^2*401^2*409^2*419^2*421^2*431^2*433^2*439^2*443^2*449^2 *457^2*461^2*463^2*467^2*479^2*487^2*491^2*499^2*503*509*521*523*541*547*557*563*569 *571*577*587*593*599*601*607*613*617*619*631*641*643*647*653*659*661*673*677*683*691 *701*709*719*727*733*739*743*751*757*761*769*773*787*797*809*811*821*823*827*829*839 *853*857*859*863*877*881*883*887*907*911*919*929*937*941*947*953*967*971*977*983*991*997$

$1000!=3^{498}*4^{497}*5^{249}*7^{164}*11^{98}*13^{81}*17^{61}*19^{54}*23^{44} *29^{35}*31^{33}*37^{27}*41^{24}*43^{23}*47^{21}*53^{18}*59^{16}*61^{16}*67^{14} *71^{14}*73^{13}*79^{12}*83^{12}*89^{11}*97^{10}*101^9*103^9*107^9*109^9*113^8*127^7 *131^7*137^7*139^7*149^6*151^6*157^6*163^6*167^5*173^5*179^5*181^5*191^5*193^5*197^5 *199^5*211^4*223^4*227^4*229^4*233^4*239^4*241^4*251^3*257^3*263^3*269^3*271^3*277^3 *281^3*283^3*293^3*307^3*311^3*313^3*317^3*331^3*337^2*347^2*349^2*353^2*359^2*367^2 *373^2*379^2*383^2*389^2*397^2*401^2*409^2*419^2*421^2*431^2*433^2*439^2*443^2*449^2 *457^2*461^2*463^2*467^2*479^2*487^2*491^2*499^2*503*509*521*523*541*547*557*563*569 *571*577*587*593*599*601*607*613*617*619*631*641*643*647*653*659*661*673*677*683*691 *701*709*719*727*733*739*743*751*757*761*769*773*787*797*809*811*821*823*827*829*839 *853*857*859*863*877*881*883*887*907*911*919*929*937*941*947*953*967*971*977*983*991*997$

$1000!=4^{497}*45^{249}*7^{164}*11^{98}*13^{81}*17^{61}*19^{54}*23^{44} *29^{35}*31^{33}*37^{27}*41^{24}*43^{23}*47^{21}*53^{18}*59^{16}*61^{16}*67^{14} *71^{14}*73^{13}*79^{12}*83^{12}*89^{11}*97^{10}*101^9*103^9*107^9*109^9*113^8*127^7 *131^7*137^7*139^7*149^6*151^6*157^6*163^6*167^5*173^5*179^5*181^5*191^5*193^5*197^5 *199^5*211^4*223^4*227^4*229^4*233^4*239^4*241^4*251^3*257^3*263^3*269^3*271^3*277^3 *281^3*283^3*293^3*307^3*311^3*313^3*317^3*331^3*337^2*347^2*349^2*353^2*359^2*367^2 *373^2*379^2*383^2*389^2*397^2*401^2*409^2*419^2*421^2*431^2*433^2*439^2*443^2*449^2 *457^2*461^2*463^2*467^2*479^2*487^2*491^2*499^2*503*509*521*523*541*547*557*563*569 *571*577*587*593*599*601*607*613*617*619*631*641*643*647*653*659*661*673*677*683*691 *701*709*719*727*733*739*743*751*757*761*769*773*787*797*809*811*821*823*827*829*839 *853*857*859*863*877*881*883*887*907*911*919*929*937*941*947*953*967*971*977*983*991*997$
и так далее по тексту.

[Nataly-Mak]

Ну, да...
И почему же умножений должно быть именно 324 (после всех понижений степеней)?

[Pavlovsky]

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

Откуда вы взяли, что умножений будет 324? Это вы уже избавились от всех старших степеней простых чисел так быстро и выяснили, что умножений будет 324?

Это я в очередной раз соврал. Количество умножений будет
L+K-2+НакладныеРасходы, где L количество чисел в разложении; K количество различных степеней в разложении. Накладные расходы возникают, когда мы вибираем A^k=A^k1*A^k2, токое что в нашем разложении нет степеней k1,k2. Каждое отсутствие k1 или k2 добавляет одно умножение.
Для разложения 1000! получается 162+30-2=188 умножений плюс накладные расходы.

[Nataly-Mak]

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

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

Откуда вы взяли, что умножений будет 324? Это вы уже избавились от всех старших степеней простых чисел так быстро и выяснили, что умножений будет 324?

Это я в очередной раз соврал.

Ага...
Ну, вот, значит, тактика у вас такая: если соврал, то на вопрос оппонента отвечать не буду.
Пусть помучается с моим враньём
В следующий раз предупреждайте, когда включаете бредогенератор.

[Pavlovsky]

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

В следующий раз предупреждайте, когда включаете бредогенератор.

Сразу предупреждаю он у меня включен постоянно. Так что все зависит от состояния датчика "здравого смысла"

[Nataly-Mak]

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

Для разложения 1000! получается 162+30-2=188 умножений плюс накладные расходы.

Что-то количество умножений стало ещё меньше
Может быть, опять напутали?

-- Ср апр 24, 2013 11:16:11 --

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

Сразу предупреждаю он у меня включен постоянно.

В таком случае, не игнорируйте вопросы участников темы.
Эти вопросы приведут ваши бредовые идеи в порядок.

[Pavlovsky]

Надо позвать Xaositect, в качестве арбитра.

Или дождаться выходных. Составлю решение для 1000!, тогда назову точное количество.

[Nataly-Mak]

Ага...
"Суха теория, мой друг, а древо жизни вечно зеленеет." (с)

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

[Pavlovsky]

Всего 379 операций. С построением простых чисел, их умножением и накладными расходами.

4 .723 Valery Pavlovsky Ekaterinburg, Russia 24 Apr 2013 11:06

[Nataly-Mak]

Класс!
Теперь болею за вас

[я вас подтолкнула к этому шагу? ]