Haskellでいろんな数列を書き出してみる

Contents

1 はじめに
2 Haskellの環境を整える
3 素数
4 双子素数
5 幸運数
6 完全数
7 階乗
8 フィボナッチ数
9 パスカルの三角形
10 終わりに

はじめに

こんにちは、野村です。

今回は、Haskellというプログラム言語でいろいろな数列を表示させてみます。
せっかくなので、Haskellの導入方法も紹介します。

Haskellの環境を整える

実行環境ghcのインストール

管理ユーザになってghcをインストールします。

# apt install ghc

Vimの設定

・インデントの体裁を揃えるための設定です。
・Haskellのソースファイルの拡張子は「.hs」とします。

~/.vim/filetype.vim

augroup filetypedetect
  au BufRead,BufNewFile *.hs setfiletype haskell
augroup END

~/.vim/ftplugin/haskell.vim

set shiftwidth=2
set softtabstop=2
set expandtab

実行方法

実行方法はいくつかあるけど、今回はVimのコマンドモードで行います。
Vimでソースコードを開き、コマンドモードで以下のコードを実行すれば結果が得られます。

:!runghc %

素数

・１より大きい自然数で、正の約数が１と自分自身のみである数。

sieve :: [Int] -> [Int]
sieve (x:xs) = x : sieve [y| y<-xs, mod y x /= 0]

p = sieve [2..]

main = do
  print $ p!!(10-1) -- 10番目の素数を表示
  print $ take 10 p -- 素数を10個表示
  print $ takeWhile (< 100) p -- 100未満の素数を表示

29
[2,3,5,7,11,13,17,19,23,29]
[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]

双子素数

・双子素数：差が２である２つの素数の組
・いとこ素数：差が４である２つの素数の組
・セクシー素数：差が６である２つの素数の組

sieve :: [Int] -> [Int]
sieve (x:xs) = x : sieve [y| y<-xs, mod y x /= 0]

twin :: Int -> [[Int]]
twin n = [[(y-n),y]|y<-[x| x<-loop p, x/=0]]
  where
    p = sieve [2..]
    loop :: [Int] -> [Int]
    loop (x:xs) = (if elem (x-n) (takeWhile (< x) p) then x else 0) : loop xs

main = do
  print $ take 10 (twin 2) -- 双子素数を10組表示
  print $ take 10 (twin 4) -- いとこ素数を10組表示
  print $ take 10 (twin 6) -- セクシー素数を10組表示

[[3,5],[5,7],[11,13],[17,19],[29,31],[41,43],[59,61],[71,73],[101,103],[107,109]]
[[3,7],[7,11],[13,17],[19,23],[37,41],[43,47],[67,71],[79,83],[97,101],[103,107]]
[[5,11],[7,13],[11,17],[13,19],[17,23],[23,29],[31,37],[37,43],[41,47],[47,53]]

幸運数

・ポーランドの数学者スタニスワフ・ウラムによって提案された数列。
・素数の性質を研究するために、素数に似たルールで導き出せる数列を考案したとのこと。

loop :: Int -> [Int] -> [Int]
loop m a = if c!!m<((length c)+1) then loop (m+1) c else c
  where
    b = [y| y<-[0..], mod y (a!!m) /= 0]
    c = [(0:a)!!x| x<-takeWhile (< (length a)+1) b]

luc :: Int -> [Int]
luc n = loop 1 (filter (odd) [0..n])

main = print $ luc 100 -- 100までの幸運数を表示

[1,3,7,9,13,15,21,25,31,33,37,43,49,51,63,67,69,73,75,79,87,93,99]

完全数

・その数自身を除く約数の和が、その数自身と等しい自然数

sieve :: [Int] -> [Int]
sieve (x:xs) = x : sieve [y| y<-xs, mod y x /= 0]

search :: Int -> [Int] -> Bool
search n a = (last (takeWhile (<= n) a)) == n

p = sieve [2..]
per1 = [take x (map ((^) 2) [0..])| x<-[2..]]
per2 = [x| x<-per1, search (sum x) p]
per3 = [(sum x)*(last x)| x<-per2]

main = print $ take 5 per3 -- 完全数を5個表示

[6,28,496,8128,33550336]

階乗

・1 から n までのすべての整数の積。

fact :: [Int] -> [Int]
fact (x:xs) = product [1..x] : fact xs
f = fact [0,1..]

main = do
  print $ f!!(10-1) -- 10番目の階乗を表示
  print $ take 10 f -- 階乗を10個表示
  print $ takeWhile (< 100) f -- 100未満の階乗を表示

362880
[1,1,2,6,24,120,720,5040,40320,362880]
[1,1,2,6,24]

フィボナッチ数

・イタリアの数学者レオナルド・フィボナッチにちなんで名付けられた数

fib = 0:1:zipWith (+) fib (tail fib)

main = do
  print $ fib!!(10-1) -- 10番目のフィボナッチ数を表示
  print $ take 10 fib -- フィボナッチ数を10個表示
  print $ takeWhile (< 100) fib -- 100未満のフィボナッチ数を表示

34
[0,1,1,2,3,5,8,13,21,34]
[0,1,1,2,3,5,8,13,21,34,55,89]

パスカルの三角形

・二項展開における係数を三角形状に並べたもの。

pas = [1] : [zipWith (+) (0:t) (t++[0])| t<-pas]

main = do
  print $ pas!!(10-1) -- パスカルの三角形の10段目を表示
  print $ take 10 pas -- パスカルの三角形を10段表示

[1,9,36,84,126,126,84,36,9,1]
[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1],[1,5,10,10,5,1],[1,6,15,20,15,6,1],[1,7,21,35,35,21,7,1],[1,8,28,56,70,56,28,8,1],[1,9,36,84,126,126,84,36,9,1]]