Текст:Роман Душкин:Теория чисел и язык Haskell

Исходный текст опубликован в журнале «Потенциал» (Душкин Р. В. «Теория чисел и язык Haskell»)

Эта статья продолжает рассматривать функциональный язык программирования Haskell, изучение которого начато в статье А. В. Ворожцова «Язык Haskell: О пользе и вреде лени». В статье рассматриваются некоторые интересные задачи из теории чисел и предлагаются численные способы их решения. Методология представления функций на языке Haskell основана на их представление в виде, наиболее близком к математическим формулам.

Введение

Теория чисел — это одно из направлений математики, которое иногда называют «высшей арифметикой». Данная наука изучает натуральные числа и некоторые сходные с ними объекты, рассматривает различные свойства (делимость, разложимость, взаимосвязи и т. д.), алгоритмы поиска чисел, а также определяет ряд достаточно интересных наборов натуральных чисел.

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

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

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

Для работы с функциями, приведёнными в этой статье, необходимо использовать интерпретатор языка Haskell HUGS 98, бесплатную версию которого можно достать на http://www.haskell.org/hugs/. Все рассмотренные в статье функции протестированы на этом интерпретаторе, поэтому правильность их определения гарантируется автором. Использование других трансляторов языка Haskell (например, компилятора GHC) также возможно, однако для их использования, возможно, придётся вносить в определения функций незначительные изменения.

Предполагается, что читатель прочитал и понял основы языка Haskell, изложенные в статье «Язык Haskell: О пользе и вреде лени», поэтому далее синтаксис поясняется редко. Если вам трудно понять синтаксис или смысл приводимых определений, можно обратиться к курсу «Основы функционального программирования», находящемуся в Викиучебнике и основанному на курсе лекций МИФИ.

Автор будет признателен любым отзывам и комментариям к статье, которые помогут сделать дальнейшие статьи более интересными и полезными для читателей. Отзывы можно посылать электронной почтой по адресу [email protected].

Простейшие задачи

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

НОД двух целых чисел $m$ и $n$ — это такой общий делитель $d$ (т. е.: $d \mid m$ и $d \mid n$, который делится на любой другой общий делитель исходных чисел. НОД определён, если хотя бы одно из чисел $m$ или $n$ не ноль. Обозначение — $(m, n)$. Для вычисления этого числа можно воспользоваться функцией gcd (от английского наименования «greatest common divisor»):

gcd :: Integral a => a -> a -> a
gcd 0 0 = error "НОД(0,0) не определён"
gcd m n = gcd' (abs m) (abs n)
  where gcd' m 0 = m
        gcd' m n = gcd' n (rem m n)

В этом определении использованы функция abs, вычисляющая модуль заданного целого числа, а также функция rem, которая возвращает остаток от целочисленного деления первого аргумента на второй. Данная функция реализует алгоритм Евклида вычисления НОД, разработаный ещё в древней Греции.

Необходимо напомнить, что строка с символами (::) является определением типа функции, тело которой определяется в следующей строке. То есть такая строка определяет сигнатуру функции. В ней используются два специальных символа: => и ->. Первый задаёт контекст использования переменных типа a в дальнейшей записи (в указанном примере — переменная a). В функции gcd аргументы могут быть любого типа a, являющегося экземпляром класса Integral, то есть классом чисел, для которых определены операции целочисленного деления и взятия остатка от деления.

Стрелка -> используется для определения типа функций. Так, к примеру, запись типа функции «Integer -> Bool» гласит, что функция принимает на вход один параметр типа Integer, а возвращает результат типа Bool. В свою очередь, запись типа «Integer -> Char -> Bool» говорит, что у функции есть два аргумента: первый типа Integer, а второй — типа Char. Возвращает функция значение типа Bool.

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

НОК двух целых чисел $m$ и $n$ — это такое наименьшее целое число, которое делится на $m$ и $n$ без остатка. Обозначение — $[m, n]$. Для вычисления этого числа можно воспользоваться функцией lcm (от английского наименования «least common multiple»):

lcm :: Integral a => a -> a -> a
lcm _ 0 = 0
lcm 0 _ = 0
lcm m n = abs ((quot m (gcd m n)) * n)

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

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

reciprocals :: Integral a => [(a, a)]
reciprocals = [(m, n) | m <- [1..], n <- [1..m], gcd m n == 1]

Как видно, это определение полностью соответствует математической формуле, по которой можно было бы вычислить множество пар взаимно простых чисел:

 \(\mathbb{N}_{reciprocals} = \{ \langle m, n \rangle \mid m \in \mathbb{N}, n \in \mathbb{N}, (m, n) = 1 \}\)

Данная функция не очень интересна с точки зрения её реализации. Всё довольно типично — определитель списка с двумя генераторами (выражения со знаком (<-)) и одним охраняющим выражением (условное выражение $gcd m n == 1$). Здесь интересно другое. Ведь приведённое определение функции, хотя и является таким простым, на самом деле содержит два скрытых вложенных цикла и одну проверку. Циклы соответствуют генераторам, при этом первый цикл выполняется от единицы до бесконечности, а второй — от единицы до значения переменной первого цикла. Это важно, т. к. если бы в определении функции стояло бы два одинаковых генератора: m <- [1..] и n <- [1..], то результаты работы были бы не так интересны — первый элемент любой пары в полученном бесконечном списке всегда был бы равен единице. Читателю предлагается самостоятельно подумать, почему это так.

Необходимо отметить, что функции gcd и lcm определены в стандартном модуле Prelude, поэтому их определение здесь приведено исключительно в познавательных целях. При разработке собственных программ эти функции можно использовать непосредственно без дополнительного определения.

Одним из самых ключевых понятий теории чисел является понятие делителя. Очень многие целочисленные последовательности, в том числе и те, которые будут рассмотрены далее, определяются через делители. Поэтому было бы интересно иметь функцию для получения списка делителей заданного числа. Пусть такая функция называется divisors:

divisors :: Integral a => a -> [a]
divisors n = [x | x <- [1..(n - 1)], rem n x == 0]

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

Такие непростые простые числа

Очень широкую известность в рамках теории чисел имеют простые числа, т. е. такие, в списке собственных делителей которых находится только один делитель — 1. Такие числа нашли самое широкое применение во многих прикладных областях, в том числе и в современных методах и алгоритмах шифрования информации. Кроме того, простые числа успешно используются в хеш-таблицах и для генерации псевдослучайных чисел.

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

Проще всего находить простые числа перебором:

primes = [n | n <- [1..], isPrime n]
         where isPrime x = (divisors x == [1])

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

Описанная функция primes вполне подходит для решения многих задач в рамках теории чисел. Хотя она работает долго, но зато вполне надёжно, вычисляя действительно бесконечный список простых чисел. Чтобы получить ограниченный список простых чисел, не превышающих заданного $n$, необходимо воспользоваться стандартной функцией take, которая возвращает заданное количество элементов с начала списка (например, команда «take 1000 primes» вернёт список из тысячи первых простых чисел). А для того, чтобы получить определённое простое число, можно воспользоваться функцией (!!), возвращающей заданный элемент списка: «primes !! 1000» вернёт тысячное простое число.

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

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

expansion :: Integer -> [Integer]
expansion 1 = []
expansion n = x:expansion (quot n x)
   where primesBN = takeWhile (<= n) primes
         x = head [y | y <- primesBN, mod n y == 0]

Данная функция будет работать медленнее для чисел, которые раскладываются на большие простые числа. Так, к примеру, число $\mbox{1 000 000}$ (миллион) раскладывается на простые множители за доли секунды ($[2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 5, 5]$), а вот следующее за ним число $\mbox{1 000 001}$ (миллион один) факторизуется примерно за полминуты ($[101, 9 901]$). Читателю предлагается самостоятельно изучить зависимость времени исполнения приведённого алгоритма факторизации от величины аргумента.

Доказано, что ряд простых чисел бесконечен. Однако среди всех таких чисел имеются т. н. числа-близнецы, т. е. такие, которые отличаются друг от друга на 2. Неизвестно, сколько таких пар, и бесконечно ли их количество вообще. Простейшее описание функции, вычисляющей такие числа, выглядит так:

twins :: [(Integer, Integer)]
twins = [(p, p + 2) | p <- primes, isPrime (p + 2)]

Кроме чисел-близнецов можно вводить ряды пар простых чисел, отличающихся друг от друга на 4, на 6 и т. д. Такие ряды имеют обобщённое наименование родственных простых чисел. Для поиска пар родственных чисел можно написать функцию, параметризуемую разницей, которая должна быть между родственными числами. Определение такой функции может выглядеть так:

kins :: Integer -> [(Integer, Integer)]
kins n = [(p, p + n) | p <- primes, isPrime (p + n)]

В этом случае определение функции для поиска простых чисел-близнецов выглядит очень просто:

twins :: [(Integer, Integer)]
twins = kins 2

Однако несмотря на всю кажущуюся простоту простых чисел, математики очень любят их. И в связи с этим постоянно ищут различные свойства, которые характеризуют простые числа. Более того, для некоторых целей выделяются особые простые числа, которые получают свои собственные имена, часто по имени своего первооткрывателя. У всех таких подмножеств простых чисел имеются собственные области применения.

Числа Мерсенна

Так, к примеру, в XVII веке французский математик М. Мерсенн определил последовательность чисел вида:

 \(M_{n} = 2^{n} - 1\)

Эта последовательность получила наименование «чисел Мерсенна». Сама по себе она не так интересна, но в ней существуют т. н. простые числа Мерсенна, которые получили свою известность в связи с эффективным критерием простоты Люка — Лемера, благодаря которому простые числа Мерсенна давно удерживают лидерство как самые большие известные простые числа. На данный момент самым большим известным простым числом является число Мерсенна $M_{30402457} = 2^{30402457} - 1$, найденное в декабре 2005 года. Оно содержит $9152052$ десятичных цифры.

Эффективный тест простоты (тест Люка — Лемера) для чисел Мерсенна был предложен в 1878 году и базируется на том наблюдении, что простота числа Мерсенна $M_{p} = 2^{p} - 1$ влечёт простоту его индекса $p$, а также на следующем утверждении: «для простого $p$ число $M_{p}$ является простым тогда и только тогда, когда оно делит число $L_{p - 1}$, где числа $L_{k}$ определяются рекуррентным соотношением — $L_{1} = 4$, $L_{k + 1} = L_{k}^{2} - 2$».

Для установления простоты $M_{p}$ последовательность чисел $L_{1}, L_{2}, \ldots, L_{p - 1}$ достаточно вычислять по модулю числа $M_{p}$ (т. е. вычислять не сами числа $L_{k}$, длина которых растёт экспоненциально, а остатки от деления $L_{k}$ на $M_{p}$, длина которых ограничена $p$ битами). Последнее число в этой последовательности $L_{p - 1} \mod M_{p}$ называется вычетом Люка — Лемера. Таким образом, число Мерсенна является простым тогда и только тогда, когда число $p$ — простое и вычет Люка — Лемера равен нулю.

Для вычисления последовательности простых чисел Мерсенна можно воспользоваться следующими несложными функциями (необходимо в очередной раз заметить, что данные определения весьма далеки от оптимизированного варианта — они лишь показывают, насколько определения функций на языке Haskell похожи на математические формулы):

lucas :: (Num a, Num b) => b -> a
lucas 1 = 4
lucas n = (lucas (n - 1))^2 - 2

mersenne :: [Integer]
mersenne = [m p | p <- primes, rem (lucas (p - 1)) (m p) == 0]
                where m p = 2^p - 1

При помощи функции mersenne во время написания автором данного подраздела статьи вычислены первые семь простых чисел Мерсенна:

[7, 31, 127, 8 191, 131  071, 524  287, 2  147  483  647].

Числа Ферма

Эксцентричный учёный П. Ферма, придумавший малую и большую теоремы своего имени, которые долгое время мучили математиков (а большая и вовсе до 1994 г. не была доказана , также интересовался простыми числами, в связи с чем пытался разработать формулу, при помощи которой можно было бы оные вычислять. После некоторых усилий он получил такое соотношение:

$F_{n} = 2^{2^{n}} + 1$

Сам П. Ферма смог проверить простоту чисел из данной последовательности только до $n = 4$. Далее он просто предположил, что остальные числа из этого ряда тоже простые. Однако в 1732 году Л. Эйлер нашёл разложение числа $F_{5}$. На сегодняшний день известно, что все числа Ферма для $5 \leq n \leq 32$ являются составными. Б\'ольшие числа из этого ряда на простоту пока не проверены.

Для проверки простоты чисел Ферма используется тест Пепина, являющийся полиномиальным. Данный тест утверждает, что число Ферма $F_{n}$ является простым тогда и только тогда, когда $3^{\frac{F_{n} - 1}{2}} \equiv -1 (\mod F_{n})$.

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

Числа Софи Жермен

Софи Жермен доказала большую теорему Ферма для показателей $n$, являющихся простыми числами $p$ такими, что числа $2p + 1$ также простые. Тем самым подмножество таких простых чисел получило наименование чисел Софи Жермен. Неизвестно, является ли эта последовательность бесконечной, хотя предполагается, что это так.

Для вычисления пар чисел Софи Жермен можно воспользоваться следующей функцией:

germain :: [(Integer, Integer)]
germain = [(p, 2 * p + 1) | p <- primes, isPrime (2 * p + 1)]

Другие последовательности простых чисел

Существует ещё большое количество различных подмножеств простых чисел, которые используются как для развлечения, так и для некоторых прикладных аспектов науки и техники. Так, к примеру, выведены формулы для простых чисел имени Вильсона (на сегодняшний день известно три таких числа) и имени Вольстенхольма (известно два таких числа). В англоязычных математических справочниках вводится до шестидесяти различных типов простых чисел, многие из которых используются в доказательствах тех или иных теорем.

Особый интерес у учёных, занимающихся теорией чисел, вызывают т. н. факториальные простые числа. Факториальным называется такое простое число, которое отличается на единицу в ту или иную сторону от факториала некоторого натурального числа: $n! \pm 1$. Эти числа интересны тем, что сигнализируют своим присутствием о начале или конце длинной последовательности составных чисел. Для получения бесконечного списка таких простых чисел можно воспользоваться следующими функциями:

fact :: (Num a, Enum a) => a -> a
fact n = product [1..n]

fp :: [Integer]
fp = [p | n <- test, p <- n, isPrime p]
       where test = [[x-1, x+1] | x <- map fact [1..]]

Функция product из стандартного модуля Prelude возвращает произведение элементов переданного ей в качестве аргумента списка.

С другой стороны простые числа можно использовать и для развлечения. Например, в ряду простых чисел можно искать такие, которые читаются одинаково в обе стороны (в десятичной системе счисления) — числа-палиндромы. Такие палиндромы можно также искать и среди простых чисел в различных системах счисления. Читателю предлагается самостоятельно разработать функцию для проверки того, что заданное число является палиндромом и реализовать бесконечный список простых чисел-палиндромов.

Совершенству нет предела

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

perfects :: [Integer]
perfects = [n | n <- [1..], sum (divisors n) == n]

Функция sum из стандартного модуля Prelude возвращает сумму элементов переданного ей в качестве аргумента списка. Однако данное определение весьма несовершенно. Если обратиться к теории чисел, то в ней можно найти доказательство того, что чётные совершенные числа и числа Мерсенна, рассмотренные в предыдущем разделе, связаны друг с другом простым соотношением:

$P_{p} = 2^{p - 1} * (2^{p} - 1)$

где число $2^{p} - 1$ является простым (числом Мерсенна). Таким образом, каждому чётному совершенному числу соответствует число Мерсенна и наоборот.

Это соотношение нашёл ещё древнегреческий математик Евклид, а строго доказал Л. Эйлер. Однако не доказано, существуют ли нечётные совершенные числа, потому данное соотношение необходимо использовать с осторожностью. Известно лишь, что если нечётное совершенное число существует, то оно должно превышать $10^{300}$.

Используя указанное соотношение, можно реализовать функцию, вычисляющую совершенные числа не медленным перебором, а достаточно быстро:

perfects :: [Integer]
perfects = [p n | n <- primes, isPrime (m n)]
        where p n = 2^(n - 1) * (m n)
              m n = 2^n - 1

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

isPerfect :: Integral a => a -> Bool
isPerfect n = sum (divisors n) == n

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

friends :: [(Integer, Integer)]
friends = [(m, n) | m <- [1..], n <- [1..(m - 1)],
                   sum (divisors m) == n,
                   sum (divisors n) == m]

Как уже упоминалось, совершенные числа очень редки. Для того, чтобы поле для исследований в этом направлении было немного шире, математики ввели некоторые дополнительные определения целочисленных последовательностей: недостаточное число и избыточное число. К недостаточным относятся такие натуральные числа, сумма собственных делителей которых меньше самого числа. Соответственно, к избыточным относятся числа, сумма собственных делителей которых больше самого числа. Таким образом, весь класс натуральных чисел может быть разделён на три непересекающихся подмножества — недостаточных, совершенных и избыточных чисел. А каждое натуральное число в свою очередь находится в одном из этих трёх подмножеств.

Но и этого адептам математики показалось мало. Были введены слегка недостаточные и слегка избыточные числа. Такие числа отличаются от совершенных в ту или иную сторону. Однако при определении таких множеств математиков ждало некоторое разочарование. Если использовать следующие функции для поиска таких чисел:

imperfects :: [Integer]
imperfects = [n | n <- [1..], sum (divisors n) == n - 1]

excesses :: [Integer]
excesses = [n | n <- [1..], sum (divisors n) == n + 1]

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

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

Заключение

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

В интернете http://www.research.att.com/njas/sequences/ можно найти энциклопедию целочисленных последовательностей (к сожалению, на английском языке), в которой представлена информация более чем о ста тысячах различных конечных и бесконечных последовательностей, состоящих из целых чисел. Данную энциклопедию можно использовать, в том числе, и для самостоятельного создания новых задач в рамках теории чисел для последующего решения методами функционального программирования.

Все перечисленные в этой статье определения функций сведены в отдельный модуль, который каждый желающий может получить, послав письмо с запросом автору статьи по адресу электронной почты [email protected].

Ссылки

• www.haskell.org
• Журнал «Потенциал», №1,2006
• Энциклопедия целочисленных последовательностей