1 // Part 1 about the 3n+1 conceture |
1 // Part 1 about the 3n+1 conjecture |
2 //================================= |
2 //================================== |
|
3 |
|
4 object CW6a { |
|
5 |
|
6 def collatz(n: Long): Long = |
|
7 if (n == 1) 1 else |
|
8 if (n % 2 == 0) 1 + collatz(n / 2) else |
|
9 1 + collatz(3 * n + 1) |
3 |
10 |
4 |
11 |
5 //(1) Complete the collatz function below. It should |
12 def collatz_max(bnd: Long): (Long, Long) = { |
6 // recursively calculate the number of steps needed |
13 val all = for (i <- (1 to bnd.toInt).toList) yield collatz(i) |
7 // until the collatz series reaches the number 1. |
|
8 // If needed you can use an auxilary function that |
|
9 // performs the recursion. The function should expect |
|
10 // arguments in the range of 1 to 1 Million. |
|
11 |
|
12 |
|
13 def collatz(n: Long): Int = |
|
14 if (n == 1) 1 else |
|
15 if (n % 2 == 0) (1 + collatz(n / 2)) else |
|
16 (1 + collatz(3 * n + 1)) |
|
17 |
|
18 |
|
19 //(2) Complete the collatz bound function below. It should |
|
20 // calculuate how many steps are needed for each number |
|
21 // from 1 upto a bound and then produce the maximum number of |
|
22 // steps and the corresponding number that needs that many |
|
23 // steps. You should expect bounds in the range of 1 |
|
24 // upto 1 million. |
|
25 |
|
26 def collatz_max(bnd: Int): (Int, Int) = { |
|
27 val all = for (i <- (1 to bnd).toList) yield collatz(i) |
|
28 val max = all.max |
14 val max = all.max |
29 (all.indexOf(max) + 1, max) |
15 (max, all.indexOf(max) + 1) |
30 } |
16 } |
31 |
17 |
32 |
18 |
33 // some testing harness |
19 } |
34 /* |
|
35 val bnds = List(2, 10, 100, 1000, 10000, 100000, 77000, 90000, 1000000, 5000000) |
|
36 |
20 |
37 for (bnd <- bnds) { |
|
38 val (max, steps) = collatz_max(bnd) |
|
39 println(s"In the range of 1 - ${bnd} the number ${max} needs the maximum steps of ${steps}") |
|
40 } |
|
41 */ |
|
42 |
|
43 //val all = for (i <- (1 to 100000).toList) yield collatz1(i) |
|
44 //println(all.sorted.reverse.take(10)) |
|
45 |
|
46 |
|
47 |
|