Anonymous user
Motzkin numbers: Difference between revisions
Initial Haskell version.
(J) |
(Initial Haskell version.) |
||
Line 845:
40 66,368,199,913,921,497 false
41 192,137,918,101,841,817 false
</pre>
=={{header|Haskell}}==
<lang haskell>import Control.Monad.Memo (Memo, memo, startEvalMemo)
import Math.NumberTheory.Primes.Testing (isPrime)
import System.Environment (getArgs)
import Text.Printf (printf)
type I = Integer
-- The n'th Motzkin number, where n is assumed to be ≥ 0. We memoize the
-- computations using MonadMemo.
motzkin :: I -> Memo I I I
motzkin 0 = return 1
motzkin 1 = return 1
motzkin n = do
m1 <- memo motzkin (n-1)
m2 <- memo motzkin (n-2)
return $ ((2*n+1)*m1 + (3*n-3)*m2) `div` (n+2)
-- The first n+1 Motzkin numbers, starting at 0.
motzkins :: I -> [I]
motzkins = startEvalMemo . mapM motzkin . enumFromTo 0
-- For i = 0 to n print i, the i'th Motzkin number, and if it's a prime number.
printMotzkins :: I -> IO ()
printMotzkins n = mapM_ prnt $ zip [0 :: I ..] (motzkins n)
where prnt (i, m) = printf "%2d %20d %s\n" i m $ prime m
prime m = if isPrime m then "prime" else ""
main :: IO ()
main = do
[n] <- map read <$> getArgs
printMotzkins n</lang>
{{out}}
<pre>
0 1
1 1
2 2 prime
3 4
4 9
5 21
6 51
7 127 prime
8 323
9 835
10 2188
11 5798
12 15511 prime
13 41835
14 113634
15 310572
16 853467
17 2356779
18 6536382
19 18199284
20 50852019
21 142547559
22 400763223
23 1129760415
24 3192727797
25 9043402501
26 25669818476
27 73007772802
28 208023278209
29 593742784829
30 1697385471211
31 4859761676391
32 13933569346707
33 40002464776083
34 114988706524270
35 330931069469828
36 953467954114363 prime
37 2750016719520991
38 7939655757745265
39 22944749046030949
40 66368199913921497
41 192137918101841817
</pre>
| |||