Как найти номер телефона в числе пи

Время на прочтение
4 мин

Количество просмотров 7.5K

Коллеги, привет! Недавно передо мной встала задача розыграть бесплатные места на нашем курсе по Python разработке. Вообще говоря, разыграть пару бесплатных мест — это просто. Можно сделать буквально в две строчки, если уже есть готовый список участников:

emails = pandas.read_csv("emails.csv")
emails.sample(NUM_WINNERS, random_state=SEED)

И это хорошо, это работает. Да и бритва Оккама говорит, что не стоит сущности плодить без необходимости. Но есть проблема — это не весело. Плюс, так мы уже выбирали победителей на курсе по Java. Там, конечно, за две строчки это не сделаешь, нужна фабрика фабрик абстрактных классов и вот это все. Все равно повторяться не хочется.

Хотелось бы сделать робота, который сам выбирает реальные шары из корзины, распознает номера и отправляет в чатик по API (это весело!), но это не очень быстро. Решение должно быть бессмысленным, беспощадным и не особо времязатратным. Так в голову пришло число Пи. Вообще у нас с коллегами есть inside joke про идеальный Пи-архиватор. Суть проста: чтобы сжать любые данные нужно лишь найти то место в числе Пи, где они начинаются и запомнить позицию (+длину, конечно).

Непревзойденное сжатие! Получается, что также можно искать устаников, в частности их emai’ы в числе Пи, и считать победителем тех, кто найдется первым. Если хотите сразу к сути, то можно тут же перейти в notebook.

Непродолжительный поиск в интернетах выдал множество решений по генерации цифр числа Пи, в том числе на Python (также в процессе находится этот прекрасный ресурс: www.angio.net/pi, — не могу не поделиться). Я, честно говоря, не знал, что человечество до такой степени обеспокоено этой проблемой. Самые популярные решения: Gauss–Legendre algorithm, Chudnovsky algorithm, BBP formula.

Я же выбрал тот вариант, который позволяет генерировать цифры числа бесконечно, а не выдает заранее определенное количество цифр:

def pi_digits():
    """generator for digits of pi"""
    q, r, t, k, n, l = 1, 0, 1, 1, 3, 3
    while True:
        if 4 * q + r - t < n * t:
            yield n
            q, r, t, k, n, l = (10*q, 10*(r-n*t), t, k, (10*(3*q+r))/t-10*n, l)
        else:
            q, r, t, k, n, l = (q*k, (2*q+r)*l, t*l, k+1, (q*(7*k+2)+r*l)/(t*l), l+2)

Это Spigot algorithm товарища Гиббонcа, который вычисляет цифры числа Пи в потоковом режиме. Все подробности есть в research paper, которая особенно понравится любителям Haskell.

Остается только связать email’ы участников с какими-то числами. Сначала я хотел брать md5 от почты и потом делить по модулю, чтобы получить число не больше заданной длины. Но это как-то не очень случайно, тем более что можно подобрать и зарегистрировать почту, которая окажется достаточно близко к началу числа Пи. Поэтому расчехляем старый добрый ПГСЧ:

np.random.seed(SEED)
emails["num"] = np.random.randint(10 ** (NUM_DIGITS - 1), 10 ** NUM_DIGITS - 1, size=len(emails))

Длина чисел задается заранее, чем длиннее число, тем, соответственно, сложнее найти его в Пи. Осталось только написать функцию поиска.

class _Num(object):
    def __init__(self, n):
        self.n = n
        self.s = str(n)
        self.p = 0 # pointer in number string representation
        self.l = len(self.s)

    def move_p(self, d):
        if self.p >= self.l:
            return
        if d == self.s[self.p]:
            self.p += 1
        else:
            # find largerst prefix in num that is suffix in current part of Pi (dumb algorithm)
            pi_part = self.s[:self.p] + d
            self.p = 0
            for i in xrange(1, len(pi_part)):
                if self.s[:i] == pi_part[-i:]:
                    self.p = i
          

def find_nums_in_pi(nums, first_n=None):
    MAX_POS = 10 ** 6
    pi_gen = pi_digits()
    first_n = first_n if first_n is not None else len(nums)
    _nums = [_Num(n) for n in nums]
    nums_pos = {}
    for pos in itertools.count():
        if pos % 1000 == 0:
            print "Current Pi position: %s. Nums found: %s" % (pos, len(nums_pos))
        if pos == MAX_POS:
            raise RuntimeError("Circuit breaker!")
        d = str(pi_gen.next())
        found_num = None
        for cur_num in _nums:
            cur_num.move_p(d)
            # whole number found
            if cur_num.p == cur_num.l:
                nums_pos[cur_num.n] = pos - cur_num.l + 1
                # found enough numbers
                if len(nums_pos) == first_n:
                    return nums_pos
                found_num = cur_num.n
        # create new search array without found number
        if found_num:
            _nums = [num for num in _nums if num.n != found_num]

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

Найти двух победителей, email’ам которых сопоставлены шестизначные числа, заняло около минуты на моей машине. Профит!

Как водится, “в бою” все пошло не совсем так гладко. Розыгрыш запускался в live режиме, с компа одновременно транслировалось видео, он немного поднапрягся и поиск занял уже 5 минут, вместо одной. Но чтобы еще более накалить обстановку я ненароком (честно!) перезапустил в notebook’е выполнение cell’а с поиском чисел после его успешного выполнения в первый раз. А notebook ошибок не прощает, старые значения не запоминает, выполняет ячейки синхронно. Нервы натянулись, как канаты. К счастью, все закончилось хорошо, победители были выявлены, награждены, справедливость восторжествовала. Слава роботам, слава числу Пи!

Кстати, впереди еще один розыгрыш мест на курсе 5 июля в 20-00. Хотите прикоснуться к прекрасному? Проходите тест и регистрируйтесь на День открытых дверей, время есть!

Если спросить любого человека на улице: что он знает о числе пи, наиболее частым будет ответ о том, что это десятичная дробь 3,14. Немногие расширят ответ, вспомнив программу 7-го класса: «Это отношение длины окружности к ее диаметру» или «Это десятичная дробь — 3,14… у которой бесконечное множество знаков после запятой».

Уточним — к июню 2022 года неугомонные математики вычислили первые 100 триллионов (!) знаков после запятой…, и это, как они считают, не предел.

Подобных иррациональных чисел, чье десятичное представление может длиться бесконечно, очень много, больше, чем рациональных.

— Юрий Валентинович, почему же именно числу пи досталось столько внимания?

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

— Почему для обозначения этого числа используется греческая буква «пи»?

— С нее начинается греческое слово, которое в переводе на русский обозначает «периферия, окружность». Вот букву и выбрали для выражения отношения длины окружности к длине ее диаметра.

Великий ученый Леонард Эйлер использовал это обозначение во многих своих трудах. Оно оказалось удобным, привилось в математике, а оттуда перешло в нашу жизнь. Для любой окружности, большой или маленькой, это отношение одно и то же. Его примерное значение равно 3,1415926… Поставленное здесь многоточие означает, что за цифрой 6 можно написать еще ряд цифр. Вместе с написанными они дадут более точное приближенное значение числа. Этот ряд цифр можно продолжить сколь угодно далеко.

— Слышала, что в 2022 году были вычислены первые 100 триллионов знаков числа пи после запятой…

— Это так. Чтобы прочесть все их вслух по одному в секунду, потребуется более 3,1 миллиона лет. А стотриллионный десятичный знак числа пи — ноль. Мы сможем приблизиться к пи сколь угодно близко, но нам никогда не удастся получить таким способом его точное значение. Как говорят, десятичная запись числа пи бесконечна. Можно сказать и по-другому: длину окружности единичного диаметра можно измерить лишь приближенно.

Справка «МК». Числа, равные отношению двух целых чисел, называют рациональными, а все остальные числа — иррациональными. Рациональным числам соответствуют конечные десятичные дроби или бесконечные, но периодические дроби. При этом иррациональных чисел намного больше, чем рациональных. Их даже невозможно пересчитать.

— Расскажите об исторических корнях числа пи.

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

Для древних греков слова «измерить площадь фигуры» означали: построить с помощью циркуля и линейки без делений квадрат, имеющий такую же площадь, как и эта фигура. Они научились это делать для треугольников и прямоугольников, вообще для любых многоугольников, для некоторых криволинейных фигур. Но вот для круга это никак не удавалось. Задача получила собственное имя — «квадратура круга», и в попытках найти ее были обнаружены хорошие приближения пи к рациональным числам.

Например, древние греки считали, что длина окружности равняется 22/7 диаметра, и это, как мы сейчас знаем, приближенное равенство вполне обеспечивало их нужды, скажем, в строительном деле. Если представить число 22/7 десятичной дробью, то мы увидим бесконечный ряд, он тоже периодичен: 22/7 = 3,142857142857…, сочетание «142857» повторяется в нем бесконечное число раз. Заметим, что первые две цифры после запятой у дроби 22/7 и у числа пи совпадают. Это означает, что дробь 22/7 хорошо приближает отношение длины окружности к ее диаметру.

А в Вавилоне было известно еще более точное приближение: 355/113 = 3,141592… намного более точное, чем 22/7.

В общем, задача найти квадратуру круга была очень привлекательной, она имела простую и понятную формулировку, почтенный возраст и, несмотря на значительные усилия, была недоступна многим профессионалам и любителям. Лишь в 1882 году немецкому математику Фердинанду Линдеману удалось доказать, что построения, реализующего квадратуру круга, не существует, квадратура круга невозможна.

— Можете привести еще пример неизмеримых геометрических объектов?

— Их очень много. Например, диагональ квадрата и его сторона несоизмеримы. Этот факт был обнаружен еще древнегреческими учеными. Длину диагонали можно измерить только приблизительно.

Давайте возьмем метровую линейку с нанесенными на ней рисками на расстоянии в один миллиметр и попробуем с ее помощью измерить длину диагонали квадрата со стороной в 1 метр. Если мы отложим на диагонали метр, а потом попробуем измерить оставшуюся ее часть с помощью линейки, то конец диагонали попадет между рисочками. Можно разделить линейку на более мелкие части, и опять ни одна из рисок нового деления не совпадет с концом диагонали. Конец диагонали всегда будет попадать между двумя соседними рисками, сколь мелкое деление вы ни сделаете. Отношение длин стороны квадрата и его диагонали — число иррациональное.

— А кто первый доказал иррациональность пи и как он это сделал?

— Иррациональность этого числа впервые доказал еще в 1761 году Иоганн Ламберт. Он использовал для этого так называемые цепные дроби, экспоненциальную и тригонометрические функции.

— Если древних греков устраивало приближенное значение пи, современные школьники, студенты тоже обходятся им, то зачем ученые продолжают высчитывать сотни триллионов знаков после запятой?

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

— Есть ли еще числа, которые настолько сильно привлекают математиков?

— Я не знаю, есть ли праздник числа е… Но это еще одна константа, которая не менее известна среди инженеров и ученых, чем пи. Она тоже иррациональна. Никто до сих пор не ответил на вопрос: получим ли мы рациональное число, сложив е с пи? Это старая проблема, которую никто не может решить.

— Как выглядит число е?

— Примерно можно записать его как десятичную дробь 2,7128… Она тоже просчитана до триллионов знаков после запятой. У нее не геометрическое, а аналитическое происхождение.

— Вы лауреат премий: Харди-Рамануджана (1997), Гумбольдта (2003), Маркова (2006). За решение какой теоретической задачи вам вручили несколько международных премий подряд?

— Она связана с числами пи и е. Как я уже говорил, это две математические постоянные, но есть ли между ними алгебраическая связь — вопрос нерешенный и очень трудный. Я рассматривал числа пи и е в степени пи. Казалось бы, число е в степени пи устроено сложнее, чем просто число е, но тем не менее мне удалось доказать, что эти числа алгебраически независимы.

— Они могут использоваться в криптографии?

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

— Существуют ли еще какие-нибудь трудные, нерешенные математические задачи, связанные с числом пи?

— Конечно, существуют. Например, неизвестно, встречается ли каждая цифра от 0 до 9 в десятичной дроби пи бесконечное число раз. А если встречается, то какая цифра встречается чаще? Может быть, в среднем все цифры появляются одинаково часто? Компьютерные вычисления подтверждают последнюю гипотезу, но она все еще не доказана.

— Считается, что в числе пи каждый может найти свой номер телефона, банковский счет и так далее. Это так?

— Это еще одна из известных открытых проблем. Вопрос, в общем, ставится так: можно ли найти любую заданную конечную последовательность цифр в десятичной дроби числа пи? Ответ: это до сих пор неизвестно — дробь-то бесконечная. К примеру, банковский счет из 20 известных цифр вы, может, найдете, а может, и нет. Если не найдете, подождите, когда вычислят следующие 100 триллионов, может, там окажется ваш банковский счет. (Улыбается.)

— Вы лично что-то искали?

— Нет, это пустая трата времени. Для чего это нужно?

— Так, из спортивного интереса.

— Ну разве что устроить спортивные соревнования, кто быстрее найдет свой номер телефона или счета, и потом выдать за это приз. Но, по-моему, доказать гипотезу — более интересная цель. Правда, она почти бесперспективна.

— Вы отмечаете праздник этого числа?

— Нет, ему, собственно, не так уж много лет, чтобы это вошло в традицию. Кроме того, этот праздник был рожден в США и связан с их системой записи дат. В России, как, впрочем, и во многих других странах, скажем, в Англии, даты записываются в порядке день-месяц-год. А в США порядок другой — месяц-день-год. Поэтому 14 марта в США запишут в виде 3.14, а в России — 14.3. Американская запись соответствует первым трем десятичным цифрам числа пи, а российская — 14.3 — к этому числу отношения не имеет. Получается, нам 14 марта праздновать нечего.

— Может, есть другие «математические» даты, которые, по-вашему, стоит праздновать?

— В 1973 году у себя на кафедре теории чисел МГУ мы отмечали другое событие — столетие доказательства французским математиком Шарлем Эрмитом трансцендентности числа е. Трансцендентность означает, что это число не может быть корнем никакого многочлена с целыми коэффициентами.

С этого события, по существу, началось развитие большого направления теории чисел, и российские математики приняли активное участие в этом процессе.

Линдеман, пытаясь доказать невозможность квадратуры круга, доказал утверждение намного более общее — трансцендентность числа пи.

Использование всех текстовых материалов без изменений в некоммерческих целях разрешается со ссылкой на N + 1

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

Если вы являетесь собственником того или иного произведения и не согласны с его размещением на нашем сайте, пожалуйста, напишите на nl@nplus1.ru

Сайт может содержать контент, не предназначенный для лиц младше 18 лет.

Связь с редакцией: info@nplus1.ru