2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 63, 64, 65, 66, 67, 68, 69 ... 88  След.
 
 Re: Factorials
Сообщение24.04.2013, 09:06 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Nataly-Mak в сообщении #714415 писал(а):
Я понимаю так, что эта аддитивная последовательность даёт нам только схему умножения для 2^994.
А как сюда присоединить умножение на другие простые числа?

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

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

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

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

 Профиль  
                  
 
 Re: Factorials
Сообщение24.04.2013, 09:20 
Аватара пользователя


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #714870 писал(а):
Я понимаю так, что эта аддитивная последовательность даёт нам только схему умножения для 2^994.
А как сюда присоединить умножение на другие простые числа?

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


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

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


22/03/08

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

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

Код:
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 всё-таки?

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

 Профиль  
                  
 
 Re: Factorials
Сообщение24.04.2013, 09:43 
Аватара пользователя


21/02/10
1594
Екатеринбург
Как применять теорему Оливоса не строя оргграф. На примере 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

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


22/03/08

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

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

 Профиль  
                  
 
 Re: Factorials
Сообщение24.04.2013, 09:53 
Аватара пользователя


21/02/10
1594
Екатеринбург
Все так же постепенно избавляемся от старших степеней.
$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$
и так далее по тексту.

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


22/03/08

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

 Профиль  
                  
 
 Re: Factorials
Сообщение24.04.2013, 09:59 
Аватара пользователя


21/02/10
1594
Екатеринбург
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 умножений плюс накладные расходы.

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


22/03/08

7154
Саратов
Pavlovsky в сообщении #714895 писал(а):
Nataly-Mak в сообщении #714890 писал(а):
Откуда вы взяли, что умножений будет 324? Это вы уже избавились от всех старших степеней простых чисел так быстро и выяснили, что умножений будет 324?

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

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

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


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #714898 писал(а):
В следующий раз предупреждайте, когда включаете бредогенератор.

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

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


22/03/08

7154
Саратов
Pavlovsky в сообщении #714895 писал(а):
Для разложения 1000! получается 162+30-2=188 умножений плюс накладные расходы.

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

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

Pavlovsky в сообщении #714903 писал(а):
Сразу предупреждаю он у меня включен постоянно.

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

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


21/02/10
1594
Екатеринбург
Надо позвать Xaositect, в качестве арбитра.

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

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


22/03/08

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

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

 Профиль  
                  
 
 Re: Factorials
Сообщение24.04.2013, 14:09 
Аватара пользователя


21/02/10
1594
Екатеринбург
Всего 379 операций. С построением простых чисел, их умножением и накладными расходами.

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

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


22/03/08

7154
Саратов
Класс!
Теперь болею за вас :wink:

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1310 ]  На страницу Пред.  1 ... 63, 64, 65, 66, 67, 68, 69 ... 88  След.

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



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

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


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

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