1 // Part 1 about the 3n+1 conceture |
1 // Part 1 about the 3n+1 conceture |
2 //================================= |
2 //================================= |
3 |
3 |
|
4 //(1) Complete the collatz function below. It should |
|
5 // recursively calculate the number of steps needed |
|
6 // until the collatz series reaches the number 1. |
|
7 // If needed you can use an auxilary function that |
|
8 // performs the recursion. The function should expect |
|
9 // arguments in the range of 1 to 10 Million. |
4 |
10 |
5 //(1) Complete the collatz function below. It should |
11 def collatz(n: Long): List[Long] = |
6 //recursively calculates the number of steps needed |
12 if (n == 1) List(1) else |
7 //number until a series ends with 1 |
13 if (n % 2 == 0) (n::collatz(n / 2)) else |
8 |
14 (n::collatz(3 * n + 1)) |
9 def collatz(n: Long): List[Long] = ... |
|
10 |
15 |
11 |
16 |
12 // an alternative that calculates the steps directly |
17 // an alternative that calculates the steps directly |
13 def collatz1(n: Long): Int = |
18 def collatz1(n: Long): Int = |
14 if (n == 1) 1 else |
19 if (n == 1) 1 else |
15 if (n % 2 == 0) (1 + collatz1(n / 2)) else |
20 if (n % 2 == 0) (1 + collatz1(n / 2)) else |
16 (1 + collatz1(3 * n + 1)) |
21 (1 + collatz1(3 * n + 1)) |
17 |
22 |
18 |
23 |
19 //(2) |
24 //(2) Complete the collatz bound function below. It should |
|
25 // calculuate how many steps are needed for each number |
|
26 // from 1 upto a bound and return the maximum number of |
|
27 // steps. You should expect bounds in the range of 1 |
|
28 // upto 10 million. |
|
29 |
20 def collatz_max(bnd: Int): Int = { |
30 def collatz_max(bnd: Int): Int = { |
21 (for (i <- 1 to bnd) yield collatz(i).length).max |
31 (for (i <- 1 to bnd) yield collatz(i).length).max |
22 } |
32 } |
23 |
33 |
24 |
34 |
|
35 // some testing harness |
25 val bnds = List(10, 100, 1000, 10000, 100000, 1000000, 10000000) |
36 val bnds = List(10, 100, 1000, 10000, 100000, 1000000, 10000000) |
26 |
37 |
27 for (bnd <- bnds) { |
38 for (bnd <- bnds) { |
28 val max = collatz_max(bnd) |
39 val max = collatz_max(bnd) |
29 println(s"In the range of 1 - ${bnd} the maximum steps are ${max}") |
40 println(s"In the range of 1 - ${bnd} the maximum steps are ${max}") |