Наткнувшись недавно на эту статью, я понял, что редко упоминаются способы вычисления факториала, отличные от банального перемножения последовательных чисел. Нужно эту ситуацию исправить.
Предлагаю рассмотреть «асимптотически наиболее быстрый» алгоритм вычисления факториала!Читать полностью »
Рубрика «простые числа» - 4
Быстрое вычисление факториала — PrimeSwing
2017-04-28 в 21:03, admin, рубрики: primeswing, Алгоритмы, математика, простые числа, факториал, факторизация, метки: primeswing, факториалПростые числа Мерсенна и тест Люка-Лемера
2017-04-25 в 13:17, admin, рубрики: wolfram language, wolfram mathematica, Алгоритмы, Блог компании Wolfram Research, Занимательные задачки, математика, Программирование, простые числа, совершенные числа, факторизация чисел, числа мерсенна
Перевод поста Джона Макги (John McGee) "Mersenne Primes and the Lucas–Lehmer Test".
Код, приведенный в статье, можно скачать здесь.
Выражаю огромную благодарность Полине Сологуб за помощь в переводе и подготовке публикации
Содержание
— Введение.
— Теорема множителей Эйлера и Мерсенна
— Люка и Лемер
— От 
до 
— Совершенные числа
— 21-е, 22-е и 23-е числа Мерсенна
— 24-е, 25-е и 26-е числа Мерсенна.
— 27-е и 28-е числа Мерсенна
— 29-е число Мерсенна
— 30-е и 31-е числа Мерсенна
— Великий интернет-поиск чисел Мерсенна
— Факторизация чисел Мерсенна
Введение.
Простое число Мерсенна — простое число вида 
(значение степени р также должно быть простым). Эти простые числа получили свое название от имени французского математика и религиозного ученого Мерсенна, который и составил данный список простых чисел этой формы в первой половине семнадцатого века. Первые четыре из них были известны уже давно: 
, 
, 
и 
.
Мерсенн утверждал, что значение 
будет простым для простых чисел 
, принадлежащих множеству 
. Во всем ли он был прав, можно проверить с помощью функции Wolfram Language — PrimeQ, в которой используются современные методы тестирования чисел на простоту, для которых не требуется поиска конкретного множителя, чтобы доказать, что число составное.
Читать полностью »
2017 это не просто простое число…
2017-01-01 в 12:22, admin, рубрики: 2017, математика, мозг, Научно-популярное, нумерология, простые числа
Прощай, год 2016-й. Здравствуй, год 2017-й.
Все мы знаем, что число 2017 простое (это же Гиктаймс, не так ли). Но оно гораздо больше, чем просто простое число.Читать полностью »
Специальные простые числа помогают пассивно прослушать протокол обмена ключами Диффи-Хеллмана
2016-10-13 в 17:06, admin, рубрики: дискретный логарифм, информационная безопасность, конечные поля, криптография, математика, модуль p, простые числа, протокол Диффи-Хеллмана
Слайд из презентации АНБ
В 2013 году благодаря Эдварду Сноудену в СМИ попали документы АНБ. Среди них — замыленный слайд из презентации, который указывал на возможности АНБ по расшифровке трафика VPN. У АНБ не было причин врать в засекреченной презентации, так что специалисты восприняли эту информацию как свидетельство наличия некоей фундаментальной уязвимости в современных системах криптографии с открытым ключом.
Читать полностью »
Разбор задач первого этапа отбора в школу программистов HeadHunter 2016
2016-10-11 в 10:21, admin, рубрики: headhunter, javascript, Алгоритмы, задачи для программистов, Занимательные задачки, простые числаВ сентябре 2016 прошел очередной ежегодный отбор молодых специалистов, студентов и выпускников инженерных и математических специальностей в школу программистов HeadHunter.
Для поступления предлагалось пройти несколько этапов, решая логические/математические задачи.
Варианты решения некоторых типовых задач первого этапа я и попытаюсь разобрать в данной статье.
PS: Для удобства быстрого написания и отладки кода подсчетов использовался JavaScript.
Пока писал статью, смотрю, в песочнице меня уже опередили по теме. Однако, у меня рассмотрены другие типы задач, только одна совпала про степени (но, судя по комментариям, не в обиду автору — решение неверное).
Читать полностью »
Красота чисел. Антипростые числа
2016-10-05 в 11:58, admin, рубрики: 5040, антипростые числа, Научно-популярное, простые числа
У числа 60 двенадцать делителей: 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60
Все знают об удивительных свойствах простых чисел, которые делятся только на самих себя и на единицу. Эти числа исключительно полезны. Относительно большие простые числа (примерно от 10300) используются в криптографии с открытых ключом, в хеш-таблицах, для генерации псевдослучайных чисел и т.д. Кроме огромной пользы для человеческой цивилизации, эти особенные числа поразительно красивы:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199…
Все остальные натуральные числа больше единицы, которые не являются простыми, называются составными. У них несколько делителей. Так вот, среди составных чисел выделяется особая группа чисел, которые можно назвать «суперсоставными» или «антипростыми», потому что у них особенно много делителей. Такие числа всегда являются избыточными.
Читать полностью »
Математик оптимизировал решето Эратосфена, чтобы искать простые числа с меньшим расходом памяти
2016-09-27 в 20:27, admin, рубрики: Научно-популярное, простые числа, Харальд Хельфготт, Эратосфен, метки: Харальд Хельфготт, Эратосфен
38-летний перуанский математик Харальд Хельфготт три года назад доказал тернарную гипотезу Гольдбаха, а сейчас сумел оптимизировать компьютерный алгоритм для расчёта решета Эратосфена. Фото: Matías Loewy
В III в. до нашей эры древнегреческий математик, астроном, географ, филолог и поэт Эратосфен Киренский придумал гениальный способ поиска простых чисел. Очень эффективный и быстрый метод, который используется до сих пор, получил название решето Эратосфена.
Суть понятна из названия. Решето Эратосфена означает поиск простых чисел методом исключения. Берём список чисел, исключаем из него все составные числа — и получаем список простых чисел, словно просеяв список через решето.
Читать полностью »
Американские математики обнаружили ранее неизвестное свойство простых чисел
2016-03-15 в 12:20, admin, рубрики: математика, простые числа 
Два математика из Стэнфордского Университета, Каннан Соундараджан [Kannan Soundararajan] и Роберт Лемке Оливер [Robert Lemke Oliver] (на фото выше) обнаружили ранее неизвестное свойство простых чисел. Выяснилось, что шансы на то, что за простым числом, оканчивающимся на 9, будет следовать число, оканчивающееся на 1, на 65% больше, чем шансы, что за ним будет следовать число, снова оканчивающееся на 9. Это предположение было численно проверено компьютерными методами для миллиардов известных простых чисел.
По словам Кена Оно, математика из Университета Эмори в Атланте, это предположение по сути противоречит ожиданиям большинства математиков. Ранее считалось, что простые числа в массе своей ведут себя достаточно случайно. Большинство теоретиков сошлось бы на предположении, что шансы иметь на конце одну из возможных для простых чисел цифр (1, 3, 7, 9) примерно равны для всех таких чисел.
Эндрю Грэнвиль [Andrew Granville] из Монреальского университета, заявил, что «мы занимаемся изучением простых чисел уже очень давно, и никто раньше этого не замечал. Это безумие какое-то. Не могу поверить, что кто-то смог до этого додуматься. Это выглядит очень странно».
Читать полностью »
Свойства простых чисел впервые начали изучать математики Древней Греции. Математики пифагорейской школы (500 BC — 300 BC) в первую очередь интересовались мистическими и нумерологическими свойствами простых чисел. Они первыми пришли к идеям о совершенных и дружественных числах.
У совершенного числа сумма его собственных делителей равна ему самому. Например, собственные делители числа 6: 1, 2 и 3. 1 + 2 + 3 = 6. У числа 28 делители — это 1, 2, 4, 7 и 14. При этом, 1 + 2 + 4 + 7 + 14 = 28.
Числа называются дружественными, если сумма собственных делителей одного числа равна другому, и наоборот – например, 220 и 284. Можно сказать, что совершенное число является дружественным для самого себя.
Ко времени появления работы Евклида «Начала» в 300 BC уже было доказано несколько важных фактов касательно простых чисел. В книге IX «Начал» Эвклид доказал, что простых чисел бесконечное количество. Это, кстати, один из первых примеров использования доказательства от противного. Также он доказывает Основную теорему арифметики – каждое целое число можно представить единственным образом в виде произведения простых чисел.
Также он показал, что если число 2n-1 является простым, то число 2n-1 * (2n-1) будет совершенным. Другой математик, Эйлер, в 1747 году сумел показать, что все чётные совершенные числа можно записать в таком виде. По сей день неизвестно, существуют ли нечётные совершенные числа.
Читать полностью »
Решаем задачу про мудрецов без ЭВМ
2015-04-22 в 7:31, admin, рубрики: задача, логика, логические игры, простые числа, решаем на бумажкеНесколько дней назад в комментариях к задаче про возраст Шерил была предложена похожая, но более интересная и сложная задачка, сформулированная таким образом:
У некоторого султана было два мудреца: Али-ибн-Вали и Вали-ибн-Али. Желая убедиться в их мудрости, султан призвал мудрецов к себе и сказал: «Я задумал два числа. Оба они целые, каждое больше единицы, но меньше ста. Я перемножил эти числа и результат сообщу Али и при этом Вали я скажу сумму этих чисел. Если вы и вправду так мудры, как о вас говорят, то сможете узнать исходные числа».
Мудрецы задумались. Первым нарушил молчание Али.
— Я не знаю этих чисел, — сказал он, опуская голову.
— Я это знал, — подал голос Вали.
— Тогда я знаю эти числа, — обрадовался Али.
— Тогда и я знаю! — воскликнул Вали.
И мудрецы сообщили пораженному царю задуманные им числа.
Назовите эти числа.
Были предложены несколько вариантов решения задачи, в том числе на Scala и C#, предполагающие достаточно грубый перебор множества возможных ответов. Тем не менее, задачу можно решить, если под рукой не оказалось ноутбука, только карандаш и листок бумаги.
Читать полностью »