Викиучебник

Теория чисел и язык Haskell: различия между версиями

Интерактивная навигация по истории
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
редакторы, делай как я
Строка 1:
<small> Исходный текст опубликован в [[Журнал «Потенциал»|журнале "«Потенциал"»]] ([[Участник:Dark_Magus|Душкин Р. В.]] "«Теория чисел и язык Haskell"»)</small>
 
Эта статья продолжает рассматривать функциональный язык программирования [[w:Haskell|Haskell]], изучение которого начато в статье А.&nbsp;В.&nbsp;Ворожцова [[Язык Haskell: О пользе и вреде лени|«Язык ''Haskell'': О пользе и вреде лени»]], опубликованной в журнале «Потенциал» №&nbsp;1 за 2006&nbsp;год. В статье рассматриваются некоторые интересные задачи из теории чисел и предлагаются численные способы их решения. Методология представления функций на языке ''Haskell'' основана на том, чтобы сделать определения таких функций наиболее похожими на математические формулы.
Эта статья продолжает рассматривать функциональный язык
программирования [[w:Haskell|Haskell]], изучение которого начато в статье
А.&nbsp;В.&nbsp;Ворожцова «Язык ''Haskell'': О пользе и вреде лени»,
опубликованной в журнале «Потенциал» №&nbsp;1 за 2006&nbsp;год. В статье
рассматриваются некоторые интересные задачи из теории чисел и
предлагаются численные способы их решения. Методология представления
функций на языке ''Haskell'' основана на том, чтобы сделать
определения таких функций наиболее похожими на математические
формулы.
 
==Введение==
 
[[w:Теория чисел|Теория чисел]] &mdash; это одно из направлений математики, которое иногда называют «высшей арифметикой». Данная наука изучает натуральные числа и некоторые сходные с ними объекты, рассматривает различные свойства (делимость, разложимость, взаимосвязи и&nbsp;т.&nbsp;д.), алгоритмы поиска чисел, а также определяет ряд достаточно интересных наборов натуральных чисел.
называют «высшей арифметикой». Данная наука изучает натуральные
числа и некоторые сходные с ними объекты, рассматривает различные
свойства (делимость, разложимость, взаимосвязи и&nbsp;т.&nbsp;д.), алгоритмы
поиска чисел, а также определяет ряд достаточно интересных наборов
натуральных чисел.
 
Так, к примеру, в рамках теории чисел рассматриваются вопросы делимости целых чисел друг на друга, [[w:алгоритм Евклида|алгоритм Евклида]] для поиска наибольшего общего делителя, поиск наименьшего общего кратного, [[w:малая теорема Ферма|малая]] и [[w:Великая теорема Ферма|большая]] теоремы Ферма. В качестве самых известных рядов натуральных чисел можно привести [[w:Числа Фибоначчи|ряд Фибоначчи]], простые числа, совершенные и дружественные числа, степени и суперстепени натуральных чисел.
Так, к примеру, в рамках теории чисел рассматриваются вопросы
делимости целых чисел друг на друга, алгоритм Евклида для поиска
наибольшего общего делителя, поиск наименьшего общего кратного,
малая и большая теоремы Ферма. В качестве самых известных рядов
натуральных чисел можно привести ряд Фибоначчи, простые числа,
совершенные и дружественные числа, степени и суперстепени
натуральных чисел.
 
С другой стороны, в рамках функционального программирования существуют различные методы для вычисления значений сложных формул. А если рассмотреть мощь и выразительность современных функциональных языков программирования, то становится очевидным, что изучать на практике различные аспекты теории чисел можно при помощи программирования формул на каком-нибудь функциональном языке.
С другой стороны, в рамках функционального программирования
существуют различные методы для вычисления значений сложных формул.
А если рассмотреть мощь и выразительность современных функциональных
языков программирования, то становится очевидным, что изучать на
практике различные аспекты теории чисел можно при помощи
программирования формул на каком-нибудь функциональном языке.
 
В этой статье в качестве функционального языка программирования, при помощи которого можно рассматривать теорию чисел, предлагается использовать ''Haskell'' как уже зарекомендовавший себя язык для использования в науке и прикладных технологиях. Более того, тот язык используется в качестве первого языка программирования в некоторых университетах мира, поэтому его рассмотрение для решения задач из теории чисел имеет ещё и практическую цель &mdash; дать читателю навыки работы с этим языком.
В этой статье в качестве функционального языка программирования, при
помощи которого можно рассматривать теорию чисел, предлагается
использовать язык ''Haskell'' как уже зарекомендовавший себя язык
для использования в науке и прикладных технологиях. Более того, язык
''Haskell'' используется в качестве первого языка программирования в
некоторых университетах мира, поэтому его рассмотрение для решения
задач из теории чисел имеет ещё и практическую цель &mdash; дать читателю навыки
работы с этим языком.
 
Для работы с функциями, приведёнными в этой статье, необходимо использовать интерпретатор языка ''Haskell'' [[HUGS 98|HUGS&nbsp;98]], бесплатную версию которого можно достать на http://www.haskell.org/hugs/. Все рассмотренные в статье функции протестированы на этом интерпретаторе, поэтому правильность их определения гарантируется автором. Использование других трансляторов языка ''Haskell'' (например, компилятора GHC) также возможно, однако для их использования, возможно, придётся вносить в определения функций незначительные изменения.
Для работы с функциями, приведёнными в этой статье, необходимо
использовать интерпретатор языка ''Haskell'' HUGS&nbsp;98, бесплатную
версию которого можно получить в интернете по адресу
http://www.haskell.org/hugs/. Все рассмотренные в статье функции
протестированы на этом интерпретаторе, поэтому правильность их
определения гарантируется автором. Использование других трансляторов
языка ''Haskell'' (например, компилятора GHC) также возможно, однако
для их использования, возможно, придётся вносить в определения
функций незначительные изменения.
 
Предполагается, что читатель прочитал и понял основы языка ''Haskell'', изложенные в статье «[[Язык Haskell: О пользе и вреде лени]]», поэтому далее синтаксис поясняется редко. Если вам трудно понять синтаксис или смысл приводимых определений, можно обратиться к курсу «[[Основы функционального программирования]]», находящемуся в Викиучебнике и основанному на курсе лекций [[w:Московский инженерно-физический институт|МИФИ]].
Предполагается, что читатель прочитал и понял основы языка ''Haskell'',
изложенные в статье «Язык Haskell: о пользе и вреде лени»,
поэтому далее объяснение синтаксиса языка будет проводиться
минимальным образом. В случае, если у читателя возникнут затруднения
с пониманием синтаксиса языка или смысла приводимых определений,
можно посоветовать обратиться к лекциям по функциональному
программированию, находящимся в интернете по адресу
http://roman-dushkin.narod.ru/fp.html.
 
Автор будет признателен любым отзывам и комментариям к статье, которые помогут сделать дальнейшие статьи более интересными и полезными для читателей. Отзывы можно посылать электронной почтой по адресу darkus.14@gmail.com.
которые помогут сделать дальнейшие статьи более интересными и
полезными для читателей. Отзывы можно посылать электронной
почтой по адресу darkus.14@gmail.com.
 
==Простейшие задачи==
 
Прежде чем рассматривать сложные вопросы теории чисел, следует понять и подготовить основной набор функций, требуемых для вычисления более сложных формул: в первую очередь, функции для нахождения наибольшего общего делителя&nbsp;(НОД) и наименьшего общего кратного&nbsp;(НОК).
Перед тем, как начать рассмотрение каких-то сложных вопросов теории
чисел, необходимо провести подготовительную работу в виде разработки
некоторых вспомогательных функций, требуемых для вычисления более
сложных формул. К таким функциям относятся в первую очередь функции
для нахождения наибольшего общего делителя&nbsp;(НОД) и наименьшего
общего кратного&nbsp;(НОК).
 
НОД двух целых чисел <math>m</math> и <math>n</math> &mdash; это такой общий делитель
 
НОД двух целых чисел <math>m</math> и <math>n</math>&mdash; это такой общий делитель
<math>d</math> (т.&nbsp;е.: <math>d \mid m</math> и <math>d \mid n</math>, который
делится на любой другой общий делитель исходных чисел. НОД
Строка 86 ⟶ 31 :
наименования «greatest common divisor»):
 
<code>gcd :: Integral a => a -> a -> a
 
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)</code>
 
 
В этом определении использованы функция <tt>abs</tt>, вычисляющая
Строка 133 ⟶ 76 :
 
 
<code>lcm :: Integral a => a -> a -> a
lcm _ 0 = 0
lcm 0 _ = 0
lcm m n = abs ((quot m (gcd m n)) * n)</code>
 
 
Здесь также встречается уже рассмотренная функция <tt>abs}</tt>, а
также функция <tt>quot}</tt>, возвращающая значение целочисленного
деления первого аргумента на второй. Как видно, НОК вычисляется
достаточно просто &mdash; необходимо разделить первый аргумент на НОД
Строка 150 ⟶ 92 :
можно воспользоваться следующей функцией:
 
<code>reciprocals :: Integral a => [(a, a)]
 
reciprocals = [(m, n) | m <- [1..], n <- [1..m], gcd m n == 1]</code>
reciprocals :: Integral a => [(a, a)]
reciprocals = [(m, n) | m <- [1..], n <- [1..m], gcd m n == 1]
 
 
Как видно, это определение полностью соответствует математической
формуле, по которой можно было бы вычислить множество пар взаимно
простых чисел:
 
 
<math>\mathbb{N}_{reciprocals} = \{ \langle m, n \rangle \mid m \in \mathbb{N}, n \in \mathbb{N}, (m, n) = 1 \}</math>
 
 
Данная функция не очень интересна с точки зрения её реализации. Всё
Строка 191 ⟶ 129 :
<tt>divisors</tt>:
 
<code>divisors :: Integral a => a -> [a]
 
divisors ::n Integral= a[x =>| ax <-> [a1..(n - 1)], rem n x == 0]</code>
divisors n = [x | x <- [1..(n - 1)], rem n x == 0]
 
 
Необходимо отметить, что данная функция возвращает список т.&nbsp;н.
Строка 235 ⟶ 171 :
 
Проще всего находить простые числа перебором:
<code>primes = [n | n <- [1..], isPrime n]
 
where isPrime x = (divisors x == [1])</code>
 
primes = [n | n <- [1..], isPrime n]
where isPrime x = (divisors x == [1])
 
 
Однако данный алгоритм весьма несовершенен. Незачем перебирать все
Строка 280 ⟶ 213 :
выглядит так:
 
<code>expansion :: Integer -> [Integer]
 
expansion :: Integer1 ->= [Integer]
expansion n = x:expansion 1(quot =n []x)
expansion nwhere primesBN = x:expansiontakeWhile (quot<= n x) primes
where primesBN x = takeWhilehead [y | y (<=- primesBN, mod n) primesy == 0]</code>
x = head [y | y <- primesBN, mod n y == 0]
 
 
Данная функция будет работать медленнее для чисел, которые
Строка 302 ⟶ 233 :
отличаются друг от друга на&nbsp;2. Неизвестно, сколько таких пар, и
бесконечно ли их количество вообще. Простейшее описание функции,
вычисляющей такие числа, выглядит следующим образомтак:
 
 
twins :: [(Integer, Integer)]
twins = [(p, p + 2) | p <- primes, isPrime (p + 2)]
 
<code>twins :: [(Integer, Integer)]
twins = [(p, p + 2) | p <- primes, isPrime (p + 2)]</code>
 
Кроме чисел-близнецов можно вводить ряды пар простых чисел,
Строка 316 ⟶ 245 :
Определение такой функции может выглядеть так:
 
<code>kins :: Integer -> [(Integer, Integer)]
 
kins n = [(p, p + n) | p <- primes, isPrime (p + n)]</code>
kins :: Integer -> [(Integer, Integer)]
kins n = [(p, p + n) | p <- primes, isPrime (p + n)]
 
 
В этом случае определение функции для поиска простых чисел-близнецов
выглядит очень просто:
 
<code>twins :: [(Integer, Integer)]
 
twins ::= [(Integer,kins Integer)]2</code>
twins = kins 2
 
 
Однако несмотря на всю кажущуюся простоту простых чисел, математики
Строка 341 ⟶ 266 :
Так, к примеру, в XVII&nbsp;веке французский математик М.&nbsp;Мерсенн
определил последовательность чисел вида:
 
 
<math>M_{n} = 2^{n} - 1</math>
 
 
 
Эта последовательность получила наименование «чисел Мерсенна».
Строка 383 ⟶ 305 :
формулы):
 
<code>lucas :: (Num a, Num b) => b -> a
lucas 1 = 4
lucas n = (lucas (n - 1))^2 - 2
 
mersenne :: [Integer]
lucas :: (Num a, Num b) => b -> a
mersenne = [m p | p <- primes, rem (lucas (p - 1)) (m p) == 40]
lucas n = (lucas (n - 1))^ where m p = 2^p - 21</code>
 
mersenne :: [Integer]
mersenne = [m p | p <- primes, rem (lucas (p - 1)) (m p) == 0]
where m p = 2^p - 1
 
 
 
 
При помощи функции <tt>mersenne</tt> во время написания автором данного
Строка 415 ⟶ 333 :
После некоторых усилий он получил такое соотношение:
 
<math>F_{n} = 2^{2^{n}} + 1</math>
 
F_{n} = 2^{2^{n}} + 1
 
 
Сам П.&nbsp;Ферма смог проверить простоту чисел из данной
Строка 446 ⟶ 362 :
функцией:
 
<code>germain :: [(Integer, Integer)]
 
germain = [(p, 2 * p + 1) | p <- primes, isPrime (2 * p + 1)]</code>
germain :: [(Integer, Integer)]
germain = [(p, 2 * p + 1) | p <- primes, isPrime (2 * p + 1)]
 
 
===Другие последовательности простых чисел===
Строка 471 ⟶ 385 :
воспользоваться следующими функциями:
 
<code>fact :: (Num a, Enum a) => a -> a
fact n = product [1..n]
 
fp :: [Integer]
fact :: (Num a, Enum a) => a -> a
fp = [p fact| n =<- producttest, p <- [1..n, isPrime p]
where test = [[x-1, x+1] | x <- map fact [1..]]</code>
 
fp :: [Integer]
fp = [p | n <- test, p <- n, isPrime p]
where test = [[x-1, x+1] | x <- map fact [1..]]
 
 
Функция <tt>product</tt> из стандартного модуля <tt>Prelude</tt>
Строка 502 ⟶ 414 :
помощи следующей функции:
 
<code>perfects :: [Integer]
 
perfects = [n | n <- [1..], sum (divisors n) == n]</code>
perfects :: [Integer]
perfects = [n | n <- [1..], sum (divisors n) == n]
 
 
Функция <tt>sum</tt> из стандартного модуля <tt>Prelude</tt>
Строка 514 ⟶ 424 :
предыдущем разделе, связаны друг с другом простым соотношением:
 
<math>P_{p} = 2^{p - 1} * (2^{p} - 1)</math>
 
P_{p} = 2^{p - 1} * (2^{p} - 1)
 
 
где число <math>2^{p} - 1</math> является простым (числом
Строка 532 ⟶ 440 :
быстро:
 
<code>perfects :: [Integer]
 
perfects = [p n | n <- primes, isPrime (m n)]
perfects :: [Integer]
perfects = [ where p n |= 2^(n <- primes,1) isPrime* (m n)]
where p m n = 2^(n - 1) * (m n)</code>
m n = 2^n - 1
 
 
Дополнительно проверить получаемые числа можно при помощи
предиката <tt>isPerfect</tt>:
 
<code>isPerfect :: Integral a => a -> Bool
 
isPerfect n = sum (divisors n) == n</code>
isPerfect :: Integral a => a -> Bool
isPerfect n = sum (divisors n) == n
 
 
Однако математики не остановились на такой формулировке. В обиход
Строка 556 ⟶ 460 :
функции:
 
<code>friends :: [(Integer, Integer)]
 
friends = [(m, n) | m <- [1..], n <- [1..(m - 1)],
friends :: [(Integer, Integer)]
friends = [(m, n) | m <- [1..], n <- [1..(m - 1)],
sum (divisors m) == n,
sum (divisors n) == m]</code>
 
 
Как уже упоминалось, совершенные числа очень редки. Для того,
Строка 574 ⟶ 476 :
недостаточных, совершенных и избыточных чисел. А каждое натуральное
число в свою очередь находится в одном из этих трёх подмножеств.
 
 
Но и этого адептам математики показалось мало. Были введены слегка
Строка 582 ⟶ 483 :
использовать следующие функции для поиска таких чисел:
 
<code>imperfects :: [Integer]
imperfects = [n | n <- [1..], sum (divisors n) == n - 1]
 
excesses :: [Integer]
excesses = [n | n <- [1..], sum (divisors n) == n + 1]</code>
 
то будет ясно, что первая функция возвращает список степеней числа
Строка 627 ⟶ 528 :
письмо с запросом автору статьи по адресу электронной почты
darkus.14@gmail.com.
 
 
==Ссылки==
Строка 633 ⟶ 533 :
* [http://potential.org.ru/bin/view/Home/JourDt200601000000PHJ1 Журнал «Потенциал», №1,2006]
* [http://www.research.att.com/njas/sequences/ Энциклопедия целочисленных последовательностей]
 
 
[[Категория:Журнал_«Потенциал»]]
Источник — https://ru.wikibooks.org/wiki/Теория_чисел_и_язык_Haskell