2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 3, 4, 5, 6, 7, 8, 9 ... 88  След.
 
 Re: Factorials
Сообщение24.01.2013, 14:17 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
У-у-у, как много статей, оказывается.
Читайте, товарищи, не ленитесь :wink:

А в последовательности OEIS A173419 произвольные натуральные числа представляются? Интереснно!
А давайте будем мои любимые числа Смита представлять таким же образом :D

Первые числа Смита:

Код:
4 22 27 58 85 94 121 166 202 265 274 319 346 355 378 382 391 438 454 483 517

Хотя, конечно, числа Смита являются подпоследовательностью последовательности A173419, как, впрочем, и факториалы.

А вот последовательность A173419 не возрастающая, и не убывающая.

Я начинаю представлять числа Смита :D

4: 1,2,4 - 2 шага (точно!)
22: 1,2,4,16,20,22 - 5 шагов (точно!)
27: 1,2,3,9,27 - 4 шага [ещё не посмотрела, сколько там в OEIS :-) ]

Правильно, для 27 4 шага. Для 58 там 6 шагов. Сейчас попробую.
А для чисел Смита в OEIS нет последовательности?

Тэк-с,

58: 1,2,3,9,27,29,58 - 6 шагов
85: 1,2,4,5,16,17,85 - 6 шагов

На 94 застряла, у меня получается 7 шагов, а надо 6.
Кто поможет? Между прочим, хорошая тренировка :-)

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


01/06/12
1016
Adelaide, Australia
Nataly-Mak в сообщении #675651 писал(а):
Не надоело вам обсасывать этот вопрос? Вы уподобляетесь Gerbicz.
Ну, я могла бы показать пример из статьи по приведённой тут ссылке, как представляется 20! Это было бы можно?


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

В прошлом конкурсе не было никаких правил и поэтому обвинения Gerbicz были не уместны. Но в этом конкурсе есть конкретные правила и их надо соблюдать.

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


22/03/08

7154
Саратов

(Оффтоп)

dimkadimon в сообщении #675734 писал(а):
В правилах конкурса написано что запрещается показывать решения или программы, все остальное можно. Эти правила относятся ко всем, даже если вы не участвуете. Не понимаю, зачем их нарушать?

Не понимаете - и не нарушайте. А за других-то что переживать? И тем более навязывать другим своё понимание.
Я привела один очень простой пример решения и не считаю это нарушением правил.
Больше не хочу это обсуждать.

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


06/10/08
6422
Pavlovsky в сообщении #675695 писал(а):
http://rjlipton.wordpress.com/2009/02/23/factoring-and-factorials/
Factoring and Factorials

Цитата:
Let G(n) be the cost of computing Г(n). Then, such a equation would yield that
G(n)\leq G(n/2)+ O({\log}^{O(1)} n)
This implies a fast method of computing n!.


Есть ли в статье алгоритм быстрого вычисления n!?
В статье говорится о том, что было бы, если бы у нас была формула вида $(2n)! = C2^{\mathop{\mathrm{poly}}(n)}n!$ и спрашивается, а нельзя ли доказать, что такой формулы быть не может.

-- Чт янв 24, 2013 15:53:31 --

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

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


22/03/08

7154
Саратов
Сделала представление 94 из 6 шагов, просто оказалось :-)

94: 1,2,4,6,16,96,94

На очереди смит 121. А в OEIS последовательность, кажется, только до 108 (?)

Смит 121 совсем простой :-)

121: 1,2,3,9,11,121 - 5 шагов

Кто меньше?

166: 1,2,3,9,81,83,166 - 6 шагов

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


01/06/12
1016
Adelaide, Australia
Pavlovsky в сообщении #675719 писал(а):
А вот если из последовательности
http://oeis.org/A173419
выбрать минимальные числа с длинной последовательности i, то получится забавня последовательность, состоящая из простых чисел.


Очень интересно! Кстати для i=8 должно быть 311, но это тоже простое. Надо проверить если последовательность продолжается. Простые действительное сложнее получать потому что их нельзя получить умножением.

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


22/03/08

7154
Саратов
Nataly-Mak в сообщении #675748 писал(а):
121: 1,2,3,9,11,121 - 5 шагов
166: 1,2,3,9,81,83,166 - 6 шагов

202: 1,2,4,5,25,100,200,202 - 7 шагов

Что-то у меня последовательность начала возрастать :-)

265:1,2,3,5,10,50,53,265 - 7 шагов

Немного остановилось возрастание.
А вот и убывает:

274: 1,2,4,16,256,18,274 - 6 шагов

Ну, понятно, тем, кто в конкурсе участвует, на смитов нельзя отвлекаться :D
Им надо факториалы представлять.
Однако все решения могут иногда - вдруг - чем-то помочь.

319: 1,2,4,16,20,320,319 - 6 шагов

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


21/02/10
1594
Екатеринбург
dimkadimon в сообщении #675753 писал(а):
Простые действительное сложнее получать потому что их нельзя получить умножением.


Не факт. Последней операцией последовательности не обязано быть умножение.

Кстати вот еще тема. Числа Мерсенна
http://ru.wikipedia.org/wiki/%D7%E8%F1% ... 5%ED%ED%E0
1, 3, 7, 15, 31, 63, 127, 255, 511, 1023

Должны иметь очень короткую последовательность.

Двойные числа Мерсенна 2^{2^n-1}-1

Почему по правилам конкурса нельзя использовать операцию деления?

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


23/01/13
11
Мелитополь
Я вчера усердно хватался за попытки ускорить программу в ущерб точности – держался на 20-м, но опять за ночь спустили на 27-е. А в запасе осталась лишь одна идея, но она тягомотная – жалко будет, если потратив несколько часов на реализацию, ресурсов так и не хватит.
Пожалуй, можно будет из этой задачки слепить маленький блог-like пост о "попытках соревноваться без законченного высшего" ..)

Хм, Числа Смита – никогда о них не слышал, хотя на Project Euler наверняка сталкивался. Nataly-Mak, с вами можно соревноваться программой? ..)

Цитата:
Почему по правилам конкурса нельзя использовать операцию деления?

Может, посчитали некрасивым добавлять в задачу уточнение вида "следует придерживаться целых чисел", когда в рамках сложения и умножения его можно опустить.
UPD: а хотя нет, там в первой же строке написано integers.

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


22/03/08

7154
Саратов
Nakilon в сообщении #675765 писал(а):
Хм, Числа Смита – никогда о них не слышал, хотя на Project Euler наверняка сталкивался. Nataly-Mak, с вами можно соревноваться программой? ..)

Конечно, можно :-)

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


06/10/08
6422
Pavlovsky в сообщении #675762 писал(а):
Почему по правилам конкурса нельзя использовать операцию деления?
С делением существует способ построения факториала за $\mathop{\mathrm{poly}}(\log n)$. См. P.Borwein & J. Hobart, The Extraordinary Power of Division in Straight Line Programs.

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


22/03/08

7154
Саратов
346 не поддаётся, два варианта и оба 8 шагов.

346: 1,2,4,6,16,20,26,320,346
346: 1,2,3,9,11,81,162,173,346
355: 1,2,3,5,9,14,70,350,355
378: 1,2,3,5,9,14,27,378
382: 1,2,3,9,11,81,90,180,191,382

Ух! Плохо :-) аж 9 шагов.

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


21/02/10
1594
Екатеринбург
Xaositect в сообщении #675769 писал(а):
С делением существует способ построения факториала за . См. P.Borwein & J. Hobart, The Extraordinary Power of Division in Straight Line Programs.


Спасибо. Вот так всегда. Кто то уже глубоко в теме. А кто то начинает с нуля, как студент первого курса. :D

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


22/03/08

7154
Саратов
Pavlovsky в сообщении #675780 писал(а):
Вот так всегда. Кто то уже глубоко в теме. А кто то начинает с нуля, как студент первого курса. :D

Вот именно поэтому важно обсуждение. Кто уже многое знает по теме, поделятся с остальными. Разве это плохо?

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


23/01/13
11
Мелитополь
С числами Смита такие дела:

22 : 5
27 : 4
58 : 6
85 : 6
94 : 6
121 : 5
166 : 6
202 : 7
265 : 7
274 : 6
319 : 6
346 : 7
355 : 7
378 : 6
382 : 7
391 : 7
438 : 7
454 : 7
483 : 7
517 : 7
526 : 7
535 : 7
562 : 7
576 : 5
588 : 7
627 : 6
634 : 7
636 : 7
645 : 7
648 : 6
654 : 7
663 : 8
666 : 7
690 : 7
706 : 8
728 : 6
729 : 5
762 : 7
778 : 7
825 : 7
852 : 7
861 : 7
895 : 7
913 : 7
915 : 7
922 : 8
958 : 7
985 : 8
1086 : 7

До восьмерки еле доходит, поэтому считается быстро и надежно.

Цитата:
Вот так всегда. Кто то уже глубоко в теме. А кто то начинает с нуля, как студент первого курса.


Я на эти ваши формулы с логарифмами и Пи смотрю как в книгу с фигой ..)

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1310 ]  На страницу Пред.  1 ... 3, 4, 5, 6, 7, 8, 9 ... 88  След.

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



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

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


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

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