| author | Christian Urban <christian dot urban at kcl dot ac dot uk> |
| Sat, 05 Nov 2016 18:15:38 +0000 | |
| changeset 10 | e7eeeb5b41dc |
| parent 9 | 48a477fdef21 |
| child 11 | 417869f65585 |
| permissions | -rw-r--r-- |
|
9
48a477fdef21
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
1 |
import scala.annotation.tailrec |
|
48a477fdef21
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
2 |
|
|
48a477fdef21
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
3 |
|
|
48a477fdef21
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
4 |
def collatz(n: Int): List[Int] = |
|
48a477fdef21
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
5 |
if (n == 1) List(1) else |
|
48a477fdef21
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
6 |
if (n % 2 == 0) (n::collatz(n / 2)) else |
|
48a477fdef21
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
7 |
(n::collatz(3 * n + 1)) |
|
48a477fdef21
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
8 |
|
|
48a477fdef21
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
9 |
def collatz1(n: Int): Int = |
|
48a477fdef21
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
10 |
if (n == 1) 1 else |
|
48a477fdef21
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
11 |
if (n % 2 == 0) (1 + collatz1(n / 2)) else |
|
48a477fdef21
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
12 |
(1 + collatz1(3 * n + 1)) |
|
48a477fdef21
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
13 |
|
|
48a477fdef21
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
14 |
@tailrec |
|
10
e7eeeb5b41dc
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
9
diff
changeset
|
15 |
def collatz2(n: Long, acc: Int): Int = |
|
9
48a477fdef21
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
16 |
if (n == 1) acc else |
|
48a477fdef21
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
17 |
if (n % 2 == 0) collatz2(n / 2, acc + 1) else |
|
48a477fdef21
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
18 |
collatz2(3 * n + 1, acc + 1) |
|
48a477fdef21
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
19 |
|
|
10
e7eeeb5b41dc
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
9
diff
changeset
|
20 |
@tailrec |
|
e7eeeb5b41dc
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
9
diff
changeset
|
21 |
def collatz3(n: BigInt, acc: Int): Int = |
|
e7eeeb5b41dc
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
9
diff
changeset
|
22 |
if (n == 1) acc else |
|
e7eeeb5b41dc
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
9
diff
changeset
|
23 |
if (n % 2 == 0) collatz3(n / 2, acc + 1) else |
|
e7eeeb5b41dc
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
9
diff
changeset
|
24 |
collatz3(3 * n + 1, acc + 1) |
|
e7eeeb5b41dc
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
9
diff
changeset
|
25 |
|
|
9
48a477fdef21
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
26 |
collatz(1) |
|
48a477fdef21
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
27 |
collatz(2) |
|
48a477fdef21
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
28 |
collatz(3) |
|
48a477fdef21
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
29 |
collatz(4) |
|
48a477fdef21
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
30 |
collatz(5) |
|
48a477fdef21
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
31 |
collatz(6) |
|
48a477fdef21
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
32 |
collatz(7) |
|
48a477fdef21
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
33 |
collatz(8) |
|
48a477fdef21
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
34 |
collatz(9) |
|
48a477fdef21
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
35 |
collatz(100000) |
|
48a477fdef21
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
36 |
println((for (i <- 1 to 100000) yield collatz(i).length).max) |
|
48a477fdef21
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
37 |
println((for (i <- 1 to 100000) yield collatz1(i)).max) |
|
48a477fdef21
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
38 |
println((for (i <- 1 to 1000000) yield collatz2(i, 1)).max) |
|
48a477fdef21
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
39 |
println((for (i <- (1 to 10000000).par) yield collatz2(i, 1)).max) |
|
10
e7eeeb5b41dc
updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
9
diff
changeset
|
40 |
println((for (i <- (1 to 100000000).par) yield collatz3(i, 1)).max) |