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