関数合成でcollatzしよう
collatz chainLength
１．関数の合成
このワークシートはMath by Codeの一部です。
関数の合成は役に立つ。
関数プログラミングの視点からみると
関数は
リストを別のリストに変形する(mapなど）
リストから新リストを作る(filterなど）
２つのリストを合体する（連結やZip)
リストを集計する（countやsumとか）
などの操作をする。
この場合の関数は、数学でよく使う代数式の関数とはちがう。
しかし、Inputに対して必ずOutputがあるようにすれば、
returnのないとか、elseがないような手続き型の処理とはちがって、関数と呼ぶことができるだろう。
関数から返されたデータを次の関数に渡すと、関数をつないでパイプラインのように合成できるね。
合成関数は、数学では通常、ｆ(g(h(x)))という記法はf*g*h とか、ｆ◯ｇ◯ｈｘとかいたりする。
xに対してh,g,fの順、右から作用させていく。
haskellの合成関数は.(dot)を使って、f.g.h = \x ->f(g(h x)) の意味でかくこともできるようです。
juliaはパイプ演算子|> を使って、引数ｘのあとに左から作用させていく。
ｘ |> h |> g |> f
とかくこともできます。
パイプ演算子の有無と書き方は、言語によってちがうので、そこは調べてみよう。
２．コラッツ数列の調査
コラッツ数列というのは有名は未解決の予想問題に関係があるね。
整数を偶数なら２で割り、奇数なら３倍して１を足すということを繰り返すと、
どんな自然数も最後は１になるチェーンができるという予想の証明がまだ未解決だ
というのは有名な話だね。
コラッツ数列になれるための課題として、１００以下の自然数すべてに対して、
１までのチェーンの長さが１００をこえるものが何個あり、それが何かを調べてみよう。
質問：この課題解決のためのコードは、関数の合成を使うとどんな作りになりますか。
では、まず、何をやっているかわかりやすくするためにhaskellを使ってみよう。
コラッツ数列の連鎖を作る再帰関数で作ります。それがchain。
１から100までの整数1つ１つにchainをマップし、連鎖の長さが100をこえたものだけfilterします。
それにあてはまる個数を出します。
つまり length( filter(map )))の合成関数を作ります。
その結果がnumLongChainsです。
どの整数からスタートしているかを知りたいので、filter(map))までは同じで、そのあと連鎖の先頭だけ取り出します。だから、map head( filter(map ))します。その結果がlongListです。
#[IN]Haskell
--=======================================================
chain :: Integer -> [Integer]
chain 1=[1]
chain n
| even n = n : chain ( n `div` 2)
| odd n = n : chain ( n * 3 + 1)
numLongChains :: Int
numLongChains = length (filter isLong (map chain [1..100]))
where isLong xs = length xs > 100
longList = map head ( filter isLong (map chain [1..100]))
where isLong xs = length xs > 100
--=======================================================
[OUT]
ghci> numLongChains
15
ghci> longList
[27,31,41,47,54,55,62,63,71,73,82,83,94,95,97]
juliaでは、コラッツ数列作りは再帰ではなくてwhile文で作ってみる。
where文がないので、使う関数を並べておき、それをつないで関数合成してみよう。
#[IN]Julia
#=======================================================
function chain(n)
result = [n]
while n != 1
n = isodd(n) ? 3n + 1 : div(n, 2)
push!(result, n)
end
return result
end
lst=[x for x in 1:100]
mapping(xs)= map(chain,xs)
long(xs) = filter(xs -> length(xs) > 100, xs)
head(xs) = map(x -> x[1],xs) #リストxのリストxsから先頭x[1]のリストを作る。
println(length(long(mapping(lst))))
println(head(long(mapping(lst))))
#=======================================================
[OUT]
15
[27, 31, 41, 47, 54, 55, 62, 63, 71, 73, 82, 83, 94, 95, 97]
かっこが入れ子になりすぎるのがイヤなら、パイプ演算子で次のようにかいてもいいね。
#=======================================================
lst |> mapping |> long |> length |> println
lst |> mapping |> long |> head |> println
#=======================================================
[OUT]
15
[27, 31, 41, 47, 54, 55, 62, 63, 71, 73, 82, 83, 94, 95, 97]
３．コラッツ数列の連鎖長の見える化
コラッツ数列の連鎖長が100超えが15％もあるのはビックリだ。
でも、長さに規則性がないだろうか？
それを探るために、1000までの連鎖長をリスト化して見える化してみよう。
#=======================================================
lst=[x for x in 1:1000]
lst |> mapping |> len |> println
#=======================================================
[OUT]
[1, 2, 8, 3, 6, 9, 17, 4, 20, 7, 15, 10, 10, 18, 18, 5, 13, 21, 21, 8, 8, 16, 16, 11, 24, 11, 112, 19, 19, 19, 107, 6, 27, 14, 14, 22, 22, 22, 35, 9, 110, 9, 30, 17, 17, 17, 105, 12, 25, 25, 25, 12, 12, 113, 113, 20, 33, 20, 33, 20, 20, 108, 108, 7, 28, 28, 28, 15, 15, 15, 103, 23, 116, 23, 15, 23, 23, 36, 36, 10, 23, 111, 111, 10, 10, 31, 31, 18, 31, 18, 93, 18, 18, 106, 106, 13, 119, 26, 26, 26, 26, 26, 88, 13, 39, 13, 101, 114, 114, 114, 70, 21, 13, 34, 34, 21, 21, 34, 34, 21, 96, 21, 47, 109, 109, 109, 47, 8, 122, 29, 29, 29, 29, 29, 42, 16, 91, 16, 42, 16, 16, 104, 104, 24, 117, 117, 117, 24, 24, 16, 16, 24, 37, 24, 86, 37, 37, 37, 55, 11, 99, 24, 24, 112, 112, 112, 68, 11, 50, 11, 125, 32, 32, 32, 81, 19, 32, 32, 32, 19, 19, 94, 94, 19, 45, 19, 45, 107, 107, 107, 45, 14, 120, 120, 120, 27, 27, 27, 120, 27, 19, 27, 40, 27, 27, 89, 89, 14, 40, 40, 40, 14, 14, 102, 102, 115, 27, 115, 53, 115, 115, 71, 71, 22, 53, 14, 14, 35, 35, 35, 128, 22, 84, 22, 128, 35, 35, 35, 53, 22, 22, 97, 97, 22, 22, 48, 48, 110, 48, 110, 66, 110, 110, 48, 48, 9, 123, 123, 123, 30, 30, 30, 79, 30, 123, 30, 22, 30, 30, 43, 43, 17, 30, 92, 92, 17, 17, 43, 43, 17, 43, 17, 61, 105, 105, 105, 43, 25, 30, 118, 118, 118, 118, 118, 56, 25, 74, 25, 118, 17, 17, 17, 43, 25, 38, 38, 38, 25, 25, 87, 87, 38, 131, 38, 38, 38, 38, 56, 56, 12, 25, 100, 100, 25, 25, 25, 144, 113, 51, 113, 25, 113, 113, 69, 69, 12, 113, 51, 51, 12, 12, 126, 126, 33, 126, 33, 126, 33, 33, 82, 82, 20, 126, 33, 33, 33, 33, 33, 51, 20, 46, 20, 46, 95, 95, 95, 46, 20, 20, 46, 46, 20, 20, 46, 46, 108, 64, 108, 59, 108, 108, 46, 46, 15, 33, 121, 121, 121, 121, 121, 121, 28, 59, 28, 77, 28, 28, 121, 121, 28, 20, 20, 20, 28, 28, 41, 41, 28, 41, 28, 134, 90, 90, 90, 134, 15, 134, 41, 41, 41, 41, 41, 33, 15, 59, 15, 54, 103, 103, 103, 41, 116, 28, 28, 28, 116, 116, 54, 54, 116, 28, 116, 54, 72, 72, 72, 98, 23, 116, 54, 54, 15, 15, 15, 41, 36, 129, 36, 129, 36, 36, 129, 129, 23, 36, 85, 85, 23, 23, 129, 129, 36, 36, 36, 28, 36, 36, 54, 54, 23, 49, 23, 23, 98, 98, 98, 142, 23, 49, 23, 142, 49, 49, 49, 98, 111, 23, 49, 49, 111, 111, 67, 67, 111, 62, 111, 36, 49, 49, 49, 62, 10, 36, 124, 124, 124, 124, 124, 62, 31, 124, 31, 124, 31, 31, 80, 80, 31, 31, 124, 124, 31, 31, 23, 23, 31, 23, 31, 49, 44, 44, 44, 137, 18, 44, 31, 31, 93, 93, 93, 44, 18, 137, 18, 31, 44, 44, 44, 88, 18, 44, 44, 44, 18, 18, 62, 62, 106, 57, 106, 31, 106, 106, 44, 44, 26, 31, 31, 31, 119, 119, 119, 31, 119, 57, 119, 119, 119, 119, 57, 57, 26, 75, 75, 75, 26, 26, 119, 119, 18, 57, 18, 70, 18, 18, 44, 44, 26, 132, 39, 39, 39, 39, 39, 70, 26, 132, 26, 132, 88, 88, 88, 132, 39, 26, 132, 132, 39, 39, 39, 39, 39, 31, 39, 31, 57, 57, 57, 132, 13, 52, 26, 26, 101, 101, 101, 39, 26, 145, 26, 101, 26, 26, 145, 145, 114, 52, 52, 52, 114, 114, 26, 26, 114, 52, 114, 145, 70, 70, 70, 96, 13, 65, 114, 114, 52, 52, 52, 65, 13, 65, 13, 39, 127, 127, 127, 39, 34, 127, 127, 127, 34, 34, 127, 127, 34, 127, 34, 65, 83, 83, 83, 171, 21, 34, 127, 127, 34, 34, 34, 65, 34, 26, 34, 26, 34, 34, 52, 52, 21, 47, 47, 47, 21, 21, 47, 47, 96, 34, 96, 140, 96, 96, 47, 47, 21, 140, 21, 21, 47, 47, 47, 96, 21, 91, 21, 47, 47, 47, 47, 140, 109, 21, 65, 65, 109, 109, 60, 60, 109, 34, 109, 153, 47, 47, 47, 60, 16, 34, 34, 34, 122, 122, 122, 153, 122, 34, 122, 60, 122, 122, 122, 122, 29, 122, 60, 60, 29, 29, 78, 78, 29, 78, 29, 104, 122, 122, 122, 73, 29, 60, 21, 21, 21, 21, 21, 73, 29, 47, 29, 135, 42, 42, 42, 135, 29, 42, 42, 42, 29, 29, 135, 135, 91, 135, 91, 42, 91, 91, 135, 135, 16, 29, 135, 135, 42, 42, 42, 86, 42, 42, 42, 42, 42, 42, 34, 34, 16, 60, 60, 60, 16, 16, 55, 55, 104, 29, 104, 148, 104, 104, 42, 42, 117, 148, 29, 29, 29, 29, 29, 179, 117, 148, 117, 29, 55, 55, 55, 148, 117, 117, 29, 29, 117, 117, 55, 55, 73, 148, 73, 47, 73, 73, 99, 99, 24, 68, 117, 117, 55, 55, 55, 117, 16, 68, 16, 55, 16, 16, 42, 42, 37, 130, 130, 130, 37, 37, 130, 130, 37, 130, 37, 68, 130, 130, 130, 117, 24, 130, 37, 37, 86, 86, 86, 130, 24, 174, 24, 86, 130, 130, 130, 37, 37, 37, 37, 37, 37, 37, 29, 29, 37, 29, 37, 29, 55, 55, 55, 130, 24, 50, 50, 50, 24, 24, 24, 143, 99, 50, 99, 37, 99, 99, 143, 143, 24, 99, 50, 50, 24, 24, 143, 143, 50, 24, 50, 37, 50, 50, 99, 99, 112, 94, 24, 24, 50, 50, 50, 50, 112]
これをみてもピンとこないのでgeogebraで視覚化してみよう。
xs=sequence(1000)で、ｘ座標を1から1000までの整数で作る。
そして、ys=上にある1000個のデータ
でｙ座標とする。
最後にzip((p,q),p,xs,q,ys)をすると、２つのリストxsとysから要素p,qを取り出してその順序対ができる。
これで、関数とグラフが即出来上がりだ。
たとえば、連続する値で長さが同じ長さになる部分があることや、
長さが直線上にように分布しているような、うろこ状に見えるところが多くあるね。
質問：下のコラッツの連鎖長の分布になにか他に気づいたことはありますか？