Как стать автором
Обновить
  • по релевантности
  • по времени
  • по рейтингу

В национальной лотерее ЮАР выпали числа 5, 6, 7, 8, 9 и 10. Регулятор начал расследование

Математика *
Необычная последовательность чисел в национальной лотерее PowerBall вызвала обвинения в мошенничестве. Организаторы заявили, что 20 человек выиграли по 5,7 млн рэндов ($370 000) каждый.


Столь необычно большое число победителей вызвано тем, какие именно числа выпали на лототроне: это 5, 6, 7, 8 и 9 (конкретно, порядок выпадения был 8, 5, 9, 7, 6). Плюс дополнительный номер в бонусном раунде — 10.
Всего голосов 17: ↑13 и ↓4 +9
Просмотры 8.7K
Комментарии 46

Знакомство с p-адическими числами. Часть 1

Математика *Научно-популярное

Иллюстрация сложения в p-адической топологии (E. Harriss and R. Nelson)
Изображение с сайта Mathematical Art Galleries


В этой серии из двух статей я приглашаю вас заглянуть в один любопытный и не самый популярный уголок математики, в котором обитают необычные создания — p-адические числа, а попутно хочу рассказать о написанной мной Haskell-библиотеке для работы с ними, а также о двух классных инструментах: о типах-литералах (type literals) и семействах типов (type families), приближающих нас к заветным зависимым типам.


Я люблю язык Haskell и, начиная с какого-то времени, мне стало комфортно думать на нём, особенно, на математические темы. Когда понадобилось освоить новый инструмент, — p-адические числа, оказалось, что в репозитории hackage, основном для Haskell-сообщества, нет инструментов для работы с ними, даже в таких серьёзных теоретико-числовых библиотеках, как arithmetic, arithmoi или factory. В конце концов, я написал и опубликовал свой модуль padic, и во второй части этой серии расскажу о некоторых деталях его реализации. А сейчас речь пойдёт о самих p-адических числах.

Читать дальше →
Всего голосов 27: ↑27 и ↓0 +27
Просмотры 3.2K
Комментарии 10

Как определить натуральные числа

Чулан
CREATE TABLE Nothing ( God XML );

— ноль
SELECT count(*) AS X FROM
    Nothing;

— один
SELECT count(*) AS X FROM
    (SELECT count(*) AS X FROM Nothing) X;

— два
SELECT count(*) AS X FROM
    (SELECT count(*) AS X FROM Nothing
     UNION
     SELECT count(*) AS X FROM (SELECT count(*) AS X FROM Nothing) X) X;

— и так далее ...
Всего голосов 28: ↑17 и ↓11 +6
Просмотры 449
Комментарии 5

Таинственное число 6174

Занимательные задачки Математика *
Перевод
Число 6174 по-настоящему таинственное. На первый взгляд может показаться, что в нём нет ничего уникального. Но как мы увидим дальше, каждый кто умеет считать, может обнаружить секрет, который делает число 6174 таким особенным.

Функция Капрекара

В 1949 году математик Д. Р. Капрекар из города Долали (Индия) придумал математическое действие, которое теперь известно как функция Капрекара. Для начала выберите любое число, в котором разряды не повторяются (то есть не 1111, 2222 и т.д.). Затем переставьте цифры так, чтобы получить самое большое число из максимально возможных и самое малое из возможных. Потом нужно вычесть из большего меньшее — и повторить операцию с получившимся числом.

Это простое действие, но Капрекар обнаружил, что оно ведёт к удивительному результату. Давайте посмотрим, как это работает, например, на числе 2005. Из этих цифр мы можем получить максимальное число 5200, а минимальное — 0025, то есть 25. Вычитания будут выглядеть так:

5200 — 0025 = 5175
7551 — 1557 = 5994
9954 — 4599 = 5355
5553 — 3555 = 1998
9981 — 1899 = 8082
8820 — 0288 = 8532
8532 — 2358 = 6174
7641 — 1467 = 6174
Читать дальше →
Всего голосов 46: ↑37 и ↓9 +28
Просмотры 8.5K
Комментарии 20

Теория чисел in TeX-way

LaTeX *Математика *
Теория чисел и TeXДемонстрируем некоторые особенности написания TeX-макросов, встраивая в TeX калькулятор теоретико-числовых функций.

Постановка задачи


Время от времени мне приходится набирать очередной текст, сопровождаемый примерами вычисления теоретико-числовых функций: функция Эйлера φ, функция делителей τ, функция Кармайкла λ. Раньше это делалось так: запускаем любимый калькулятор (мой выбор — PARI/GP), в нем все считаем и копируем выкладки в ТеХ. Изменились исходные данные — снова в калькулятор и обратно. Много возни, много шансов забыть заменить какой-то промежуточный результат. Да и просто мышкой махать надоедает. Хочется автоматизировать этот процесс хотя бы для самых распространенных функций, чтобы можно было написать
$\phi(1001)=\Phi(1001)$
и получить на печати
\phi(1001)=720

Читать дальше →
Всего голосов 66: ↑65 и ↓1 +64
Просмотры 4.7K
Комментарии 16

Еще раз о поиске простых чисел

Алгоритмы *
Скульптура `Решето Эратосфена` (Стэнфордский университет) В заметке обсуждаются алгоритмы решета для поиска простых чисел. Мы подробно рассмотрим классическое решето Эратосфена, особенности его реализации на популярных языках программирования, параллелизацию и оптимизацию, а затем опишем более современное и быстрое решето Аткина. Если материал о решете Эратосфена предназначен в первую очередь уберечь новичков от регулярного хождения по граблям, то алгоритм решета Аткина ранее на Хабрахабре не описывался.

На снимке — скульптура абстрактного экспрессиониста Марка Ди Суверо «Решето Эратосфена», установленная в кампусе Стэнфорского университета
Читать дальше →
Всего голосов 159: ↑151 и ↓8 +143
Просмотры 211K
Комментарии 27

Гипотеза Била подорожала до 1 миллиона долларов

Математика *
Американское математическое общество во вторник объявило о повышении награды до 1 миллиона долларов за доказательство гипотезы Била или за нахождение контрпримера.

Гипотеза

Если

где — натуральные и , то имеют общий простой делитель.

То есть если вы подберёте такие числа, чтобы у A, B, C не было общего простого делителя, то заработаете миллион долларов.
Читать дальше →
Всего голосов 49: ↑41 и ↓8 +33
Просмотры 61K
Комментарии 93

Нормальные числа: ликбез

Математика *
Не так давно попалась мне на глаза великолепная юмористическая статья про файловую систему, хранящую данные в числе Пи. Бурное обсуждение, развернувшееся в комментариях (кажется, не все его участники поняли шутку), натолкнуло меня на мысль, что тему нормальных чисел неплохо бы обсудить более серьёзно, тем более что тема эта благодатна, полна красивых результатов, нерешённых проблем и прочих кошерных вещей. Если желаете с этими вещами ознакомиться — пожалуйте под кат.

image

Читать дальше →
Всего голосов 116: ↑112 и ↓4 +108
Просмотры 56K
Комментарии 38

Функция «ковра»

PHP *Занимательные задачки Математика *
Из песочницы
Подшефные ребята осваивают вэб-программирование, в частности, PHP.
Одной из первых задач на освоение таблиц <table> они получают задание отрисовать на PHP таблицу умножения, эдак 25х25.
Далее начинаются простые «навороты» — например, выкрасить в полученной таблице клетки с четными числами. Как выяснилось, наворотами можно наслаждаться часами.
Читать дальше →
Всего голосов 88: ↑72 и ↓16 +56
Просмотры 7.8K
Комментарии 6

Коллективный разум в теории чисел

Математика *
В мае на Хабре была опубликована статья, которая повествует о работе Yitang Zhang в области теории простых чисел, вызвавшей большой резонанс в научном сообществе. В этой заметке даётся краткая сводка результатов, которых удалось достичь научному сообществу спустя девять месяцев с момента публикации этой работы.

Подробности
Всего голосов 77: ↑72 и ↓5 +67
Просмотры 31K
Комментарии 33

Конечное и бесконечное в математике. Лекция Павла Кожевникова для старшеклассников в Яндексе

Блог компании Яндекс Алгоритмы *Математика *
В отличие от окружающего нас мира, в котором всё конечно, в математике мы часто сталкиваемся с бесконечными объектами. Например, бесконечны множества целых, рациональных, алгебраических, конструктивных или действительных чисел. На лекции мы рассмотрим задачи, в которых проявляются некоторые принципы работы с бесконечными множествами. Иногда эти принципы сильно отличаются от тех, к которым мы привыкли в случае «конечного» мира.


Конспект лекции
Всего голосов 72: ↑62 и ↓10 +52
Просмотры 27K
Комментарии 31

Множительный инструмент на основе теоремы Слонимского

Математика *История IT
Recovery mode
Из песочницы
В XIX веке существовали интересные инструменты для умножения, построенные на основе теоремы Слонимского. Это «Снаряд для умножения» Слонимского и бруски Иоффе. Об этих инструментах в интернете невозможно ничего прочитать, кроме скудного описания внешнего вида, ни на что ни годного описания методики работы (в стиле «это работало как-то вот так»), заимствованного из книги «История вычислительной техники» И.А. Апокин, Л.Е. Майстров, «Наука» 1990 г. Описание не раскрывает принцип действия приборов. Литературу, на которую ссылается автор книги, достать неприемлемо сложно. Я решил вскрыть алгоритм работы прибора самостоятельно, а для демонстрации — изготовить собственный аналог.
Читать дальше →
Всего голосов 12: ↑2 и ↓10 -8
Просмотры 3.1K
Комментарии 7

База данных простых чисел

Алгоритмы *Big Data *Математика *
Из песочницы
Давеча снова увлекся простыми числами. Манит меня их тайна.

Написал алгоритм, похожий на решето Эратосфена. За 3 часа программа нашла 700 тысяч первых простых чисел. А мне надо хотя бы 14 миллионов простых чисел, чтобы перемножив их, получить число с количеством десятичных цифр, равным 100 миллионам штук.

Из статьи «Еще раз о поиске простых чисел», написанной пользователем Bodigrim, узнал о существовании быстрой программы primegen, которая работает используя решето Аткина. Установил ее в виртуальной машине LUbuntu (VirtualBox). Действительно, primegen очень быстро работает!

Тогда встал вопрос, как сохранить 14 миллионов простых чисел? Можно просто каждое простое число записать в файл как int32. А если простое число будет больше мощности 32-х бит?
Читать дальше →
Всего голосов 66: ↑49 и ↓17 +32
Просмотры 53K
Комментарии 59

Hydra Slayer: убиваем время и числа

Математика *
24 марта сего года произошло событие, которого мы все так давно ждали: в сервисе цифровой дистрибуции компьютерных игр Steam вышел очередной шедевр польского игростроя — Hydra Slayer. И хотя шедевр этот местами кривоват, да и ждали его далеко не все, а скорее три с половиной человека, всё же я полагаю его достойным своей статьи на Хабре. «Постойте-ка, любезный автор, — воскликнет сейчас человек по другую сторону монитора от меня, — а не спутали ли вы часом столь уважаемый сайт, как Хабрахабр, с каким-нибудь игровым порталом, где юноши от четырнадцати лет и младше делятся своими успехами в Майнкрафте, обильно используя ненормативную лексику?». Нет, не спутал. Этому материалу суждено особое место в хабе «Математика».

image
И вот почему.
Всего голосов 21: ↑21 и ↓0 +21
Просмотры 11K
Комментарии 15

Оракул от арифметики

Математика *
Перевод

В свои 28 лет Петер Шольце раскрывает глубинные связи между теорией чисел и геометрией




В 2010 году по сообществу людей, изучающих теорию чисел, прошёл поразительный слух – и дошёл до Джареда Вайнштейна [Jared Weinstein]. Якобы какой-то аспирант из Боннского университета в Германии опубликовал работу, в которой 288-страничное доказательство теоремы из теории чисел ужато всего до 37 страниц. 22-летний студент Петер Шольце нашёл способ обойти одну из самых сложных частей доказательства, сопоставив теорию чисел и геометрию.

«Просто невероятно, что такой молодой человек смог сделать нечто настолько революционное,- говорит Вайнштейн, 34-летний специалист по теории чисел из Бостонского университета. – Это несомненный повод для уважения».

Математики из Боннского университета, присвоившие Шольце звание профессора всего два года спустя, уже знали о его экстраординарных умственных способностях. После публикации работы его начали замечать эксперты и по теории чисел, и по геометрии.

С того момента Шольце, которому сейчас 28, дорос до высокого положения уже в более широком математическом сообществе. Его называют "одним из самых влиятельных математиков мира", и "редким талантом, появляющимся раз в несколько десятилетий". О нём говорят, как о фаворите среди претендентов на Филдсовскую премию, одну из высочайших наград для математика.

Ключевому нововведению Шольце – классу фрактальных структур, названных им перфектоидными пространствами – исполнилось всего несколько лет, но оно уже ведёт к далеко идущим последствиям в области арифметической геометрии, в которой сливаются теория чисел и геометрия. Вайнштейн говорит, что работа Шольце была провидческой. «Он смог увидеть последствия до того, как те начали происходить».
Читать дальше →
Всего голосов 51: ↑50 и ↓1 +49
Просмотры 33K
Комментарии 103

Кем был Рамануджан?

Блог компании Wolfram Research Занимательные задачки Математика *Профессиональная литература
Перевод

Перевод поста Stephen Wolfram "Who Was Ramanujan?".
Выражаю огромную благодарность Полине Сологуб за помощь в переводе и подготовке публикации

Содержание


Удивительное письмо
Начало истории
Кем был Харди?
Письмо и его последствия
Стиль работы Рамануджана
Видеть то, что важно
Истина или объяснение
Переход в Кембридж
Рамануджан в Кембридже
Что было дальше
Что стало с Харди?
Математика Рамануджана
Факты — случайные или нет?
Автоматизация работ Рамануджана
Современные Рамануджаны?
Что было бы, если бы у Рамануджана была Mathematica?
На этой неделе вышел фильм "Человек, который познал бесконечность" (который мне показали еще прошлой осенью Манджул Бхаргава и Кен Оно), так что я не мог не написать о его главном герое — Сринивасе Рамануджане.



Удивительное письмо


Раньше они приходили по обычной почте. Сейчас — по электронной. В течение многих лет со всего мира ко мне стекаются письма, в которых содержатся смелые утверждения о простых числах, теории относительности, искусственном интеллекте, сознании и множестве других вещей. Глядя на эти сообщения, я вспоминаю историю Рамануджана и неизменно откладываю свои идеи и проекты, чтобы хотя бы просмотреть их.

Около 31 января 1913 года математик по имени Харди из Кембриджа, Англия, получил пакет документов с сопроводительным письмом, которое начиналось так: "Дорогой сэр, хочу представиться вам: я клерк из бухгалтерии порта в Мадрасе с зарплатой £20 в год. Мне 23 года....». И продолжал: писал о том, что достиг «поразительного» прогресса в теории расходящихся рядов по математике и решил давнишнюю проблему распределения простых чисел. Сопроводительное письмо заканчивалось словами: "Я беден; если вы решите, что здесь есть что-нибудь ценное, я хотел бы, чтобы мои теоремы были опубликованы… Я неопытен, и любые ваши советы ценны для меня. Прошу извинить меня за доставленные неудобства. Искренне ваш, с уважением, С. Рамануджан".
Читать дальше о Рамануджане...
Всего голосов 86: ↑79 и ↓7 +72
Просмотры 90K
Комментарии 58

Поле Галуа на Scala

Scala *Математика *

Введение


В этой статье будет рассмотрена тема построения и работы с конечными полями (или полями Галуа), которые используются в криптографии, теории информации и кодирования и других науках, т.е. имеют широкое практическое применение. Сухую теорию о группах/кольцах/полях можно прочитать по ссылке Поля Галуа, а здесь будет больше практики и реализации на языке Scala.

Типы и ограничения


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

  • Тип Int в Scala/Java имеет размер 32 бита
  • Использовать можно биты: 0..30 — 31, поскольку 32-ой бит является знаковым
  • Полиномы должны быть представлены числами в диапозоне 0..29
  • Неприводимые полиномы (или модули) имеют диапозон 1..30
  • Конечное поле имеет элементов

Реализация


Сначала опишем класс Polynomial, который реализует полином и 4 операции. Этот вид полинома является «полуфабрикатом» и не привязан к конечному полю.
Читать дальше →
Всего голосов 18: ↑15 и ↓3 +12
Просмотры 7.9K
Комментарии 6

Компрессия больших массивов простых чисел

C *Математика *Сжатие данных *
Из песочницы
песочница

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

 

Так, формат 16-разрядных беззнаковых целых при размере такой таблицы около 13 килобайт вмещает всего лишь 6542 простых числа: вслед за числом 65531 идут значения более высокой разрядности. Такая таблица годится разве что в качестве игрушки.

 

Наиболее ходовой в программировании формат 32-разрядных целых выглядит значительно солиднее — он позволяет хранить около 203 млн простых. Но такая таблица занимает уже около 775 мегабайт.

 

Еще больше перспектив у 64-разрядного формата. Однако при теоретической мощности порядка 1e+19 значений, таблица имела бы размер 64 экзабайта.


Читать дальше →
Всего голосов 55: ↑54 и ↓1 +53
Просмотры 16K
Комментарии 56

О взаимосвязи простых и иррациональных чисел

Математика *
Из песочницы
После некоторых моих исследований простых чисел, я обнаружил интересную связь с иррациональными числами. Эта связь дает ответ на вопрос, почему простые числа расположены столь «хаотично» и почему они так сложно устроены. Под катом объяснение этой связи и вариант улучшенного алгоритма RSA.
Читать дальше →
Всего голосов 22: ↑18 и ↓4 +14
Просмотры 8.8K
Комментарии 28

В распределении простых чисел обнаружена дифракционная картина, примерно как у квазикристаллов

Блог компании GlobalSign Криптография *Математика *Визуализация данных Химия

В марте 2016 года Роберт Дж. Лемке-Оливер и Каннан Соундарараджан из Стэнфордского университета открыли новый шаблон в распределении простых чисел. Оказалось, что простые числа специфически распределяются по числовому пространству. Подробнее см. перевод статьи «Структура и случайность простых чисел» на Хабре.

К изучению темы подключились специалисты из других областей, в том числе химии. И успешно. Профессор теоретической химии Сальваторе Торкуато вместе с теоретиком чисел Мэтью де Курси-Айрлэнд нашли новые шаблоны в распределении простых чисел, о которых раньше не было известно. Оказалось, что распределение простых чисел образует фракталоподобную дифракционную картину, чем-то похожую на картину дифракции у экзотических квазикристаллов.
Читать дальше →
Всего голосов 64: ↑61 и ↓3 +58
Просмотры 54K
Комментарии 58
1