Factorials

[Nataly-Mak]

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

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

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

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

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

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

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

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.
Кто поможет? Между прочим, хорошая тренировка

[dimkadimon]

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

Не надоело вам обсасывать этот вопрос? Вы уподобляетесь Gerbicz.
Ну, я могла бы показать пример из статьи по приведённой тут ссылке, как представляется 20! Это было бы можно?

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

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

[Nataly-Mak]

(Оффтоп)

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

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

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

[Xaositect]

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 --

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

[Nataly-Mak]

Сделала представление 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 шагов

[dimkadimon]

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

А вот если из последовательности
http://oeis.org/A173419
выбрать минимальные числа с длинной последовательности i, то получится забавня последовательность, состоящая из простых чисел.

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

[Nataly-Mak]

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 шагов

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

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

[Pavlovsky]

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

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

[Nakilon]

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

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

Цитата:

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

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

[Nataly-Mak]

Nakilon в сообщении #675765 писал(а):

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

Конечно, можно

[Xaositect]

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

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

С делением существует способ построения факториала за $\mathop{\mathrm{poly}}(\log n)$. См. P.Borwein & J. Hobart, The Extraordinary Power of Division in Straight Line Programs.

[Nataly-Mak]

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 шагов.

[Pavlovsky]

Xaositect в сообщении #675769 писал(а):

С делением существует способ построения факториала за . См. P.Borwein & J. Hobart, The Extraordinary Power of Division in Straight Line Programs.

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

[Nataly-Mak]

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

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

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

[Nakilon]

С числами Смита такие дела:

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

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

Цитата:

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

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