somefunctions/someFunctions.hs at master · Teiolass/somefunctions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
import Data.List

common::(Ord a)=>[a]->[a]->[a]
common xs [] = []
common [] ys = []
common xs@(x:xt) ys@(y:yt)
    |x<y  = common xt ys
    |x==y = x:common xt yt
    |x>y  = common xs yt

diff::(Ord a)=>[a]->[a]->[a]
diff xs [] = xs
diff [] ys = []
diff xs@(x:xt) ys@(y:yt)
    |x<y  = x:diff xt ys
    |x==y = diff xt yt
    |x>y  = diff xs yt

merge::(Ord a)=>[a]->[a]->[a]
merge xs [] = xs
merge [] ys = ys
merge xs@(x:xt) ys@(y:yt)
    |x<y  = x:merge xt ys
    |x==y = x:merge xt yt
    |x>y  = y:merge xs yt

merge'::(Ord a)=>[a]->[a]->[a]
merge' [] ys = ys
merge' xs [] = xs
merge' xs@(x:xt) ys@(y:yt)
    |x<y  = x:merge' xt ys
    |x==y = x:y:merge' xt yt
    |x>y  = y:merge' xs yt

group'::(Ord a)=>[a]->[[a]]
group' (x:xt) = (x:prefix):group' remainder
    where (prefix,remainder) = span (==x) xt

legendreDePolignac::Int->Int->Int
legendreDePolignac n m = f 0 m
    where f k s
            |n<s       = k
            |otherwise = f (k+(n`quot`s)) (s*m)

multiples::Int->[Int]
multiples n = [n,2*n..]

commonMultiples::[Int]->[Int]
commonMultiples xs = foldl1' common.map multiples $xs

mcmList::[Int]->Int
mcmList xs = foldl1' lcm xs

gcdList::[Int]->Int
gcdList xs = foldl1' gcd xs

listPrimes::[Int]
listNonPrimes::[Int]
listPrimes    = 2:3:5:7:(diff [9,11..] listNonPrimes)
listNonPrimes = foldr1 f.map g.tail $listPrimes
    where f (x:xt) ys = x:(merge xt ys)
          g p         = [p*p,p*(p+2)..]

listPrimesLow::Int->[Int]
listPrimesLow n = takeWhile (<=n) listPrimes

isPrime::Int->Bool
isPrime m = m`elem`listPrimes

firstPrimes::Int->[Int]
firstPrimes n = take n listPrimes

nPrime::Int->Int
nPrime n = listPrimes!!n

primeFactors::Int->[Int]
primeFactors n = listFactors n listPrimes
    where listFactors n (p:pt)
             |p*p>n      = [n]
             |n`rem`p/=0 = listFactors n pt
             |otherwise  = p:listFactors (n`quot`p) (p:pt)

listFactors'::Int->[[Int]]
listFactors' n = group'.primeFactors $n

primeFactors'::Int->[(Int,Int)]
primeFactors' n = map elemLength.listFactors' $n
    where elemLength xs = (head xs,length xs)

numDiv::Int->Int
numDiv n = product.map (\xs->1+length xs).listFactors' $n

phi::Int->Int
phi n = n+1-(numDiv n)

productsList::[Int]->[Int]
productsList'::[Int]->[Int]->[Int]
productsList xs = productsList' [] xs
productsList' ys [] = ys
productsList' ys (x:xt) = productsList' (f ys x) xt
    where f [] x = [x]
          f (y:yt) x = y:(y*x):(f yt x)

nubProductsList::[Int]->[Int]
nubProductsList'::[Int]->[Int]->[Int]
nubProductsList xs = nubProductsList' [] xs
nubProductsList' ys [] = ys
nubProductsList' ys (x:xt) = nubProductsList' (nub.f ys $x) xt
    where f [] x = [x]
          f (y:yt) x = y:(y*x):(f yt x)

listDiv::Int->[Int]
listDiv 0 = []
listDiv n = (1:).nubProductsList.primeFactors $n

sumProductsList::[Int]->Int
sumProductsList xs = foldl1' (\acc x->acc*(x+1)) $xs

listFib::[Int]
listFib = 0:1:(zipWith (+) listFib $tail listFib)

nFib::Int->Int
nFib n = listFib!!n

listTriangNum::[Int]
listTriangNum = scanl1 (+) [1..]

listPentNum::[Int]
listPentNum = scanl1 (+) [1,4..]

listHexNum::[Int]
listHexNum = scanl1 (+) [1,5..]

listFact::[Integer]
listFact = scanl (*) 1 [1..]

nFact::Int->Integer
nFact n = listFact!!n

tartaLP::Int->Int->Integer
tartaLP l p = (nFact l)`quot`((nFact p)*(nFact $l-p))

collantzChain::Int->[Int]
collantzChain n
   |n==1      = [1]
   |even n    = n:collantzChain (n`quot`2)
   |otherwise = n:collantzChain (3*n+1)