1 // Part 1 about the 3n+1 conjecture |
1 object CW6a { |
2 //================================== |
|
3 |
2 |
4 // generate jar with |
3 //(1) Complete the collatz function below. It should |
5 // > scala -d collatz.jar collatz.scala |
4 // recursively calculate the number of steps needed |
6 |
5 // until the collatz series reaches the number 1. |
7 object CW6a { |
6 // If needed, you can use an auxiliary function that |
|
7 // performs the recursion. The function should expect |
|
8 // arguments in the range of 1 to 1 Million. |
8 |
9 |
9 |
10 |
10 /* |
11 // def collatz(n: Long) : Long = { |
11 * def collatz(n: Long): Long = |
12 // if (n == 1) 1 //else |
12 if (n == 1) 0 else |
13 // // if (n % 2 == 0) { |
13 if (n % 2 == 0) 1 + collatz(n / 2) else |
14 // // collatz(n/2) |
14 1 + collatz(3 * n + 1) |
15 // // steps + 1 |
15 */ |
16 // // } //else |
|
17 // // if (n % 2 != 0) { |
|
18 // // collatz((3 * n) + 1) |
|
19 // // steps + 1 |
|
20 // // } |
|
21 // } |
16 |
22 |
17 def collatz_max(bnd: Long): (Long, Long) = { |
23 // val steps: Long = 1 |
18 val all = for (i <- (1L to bnd)) yield (collatz(i), i) |
24 // val lst = List() |
19 all.maxBy(_._1) |
25 // def collatz(n: Long) : Long = { |
|
26 // if (n == 1) { steps + 1 } |
|
27 // else if (n % 2 == 0) { |
|
28 // collatz(n/2); |
|
29 // } |
|
30 // else { |
|
31 // collatz((3 * n) + 1); |
|
32 // } |
|
33 // steps + 1 |
|
34 // } |
|
35 // collatz(6) |
|
36 |
|
37 def collatz(n: Long, list: List[Long] = List()): Long = { |
|
38 if (n == 1) { |
|
39 n :: list |
|
40 list.size.toLong |
|
41 } |
|
42 else if (n % 2 == 0) { |
|
43 collatz(n / 2, n :: list) |
|
44 } |
|
45 else { |
|
46 collatz((3 * n) + 1, n :: list) |
|
47 } |
|
48 } |
|
49 |
|
50 val test = collatz(6) |
|
51 |
|
52 //(2) Complete the collatz_max function below. It should |
|
53 // calculate how many steps are needed for each number |
|
54 // from 1 up to a bound and then calculate the maximum number of |
|
55 // steps and the corresponding number that needs that many |
|
56 // steps. Again, you should expect bounds in the range of 1 |
|
57 // up to 1 Million. The first component of the pair is |
|
58 // the maximum number of steps and the second is the |
|
59 // corresponding number. |
|
60 |
|
61 //def collatz_max(bnd: Long) : (Long, Long) = ... |
|
62 def collatz_max(bnd: Long) : (Long, Long) = { |
|
63 val stepsTable = for (n <- (1 to bnd.toInt).toList) yield (collatz(n), n.toLong) |
|
64 //println(stepsTable) |
|
65 stepsTable.max |
20 } |
66 } |
21 |
67 |
22 |
68 |
23 /* some test cases |
|
24 val bnds = List(10, 100, 1000, 10000, 100000, 1000000) |
|
25 |
|
26 for (bnd <- bnds) { |
|
27 val (steps, max) = collatz_max(bnd) |
|
28 println(s"In the range of 1 - ${bnd} the number ${max} needs the maximum steps of ${steps}") |
|
29 } |
69 } |
30 |
70 |
31 */ |
|
32 |
|
33 |
|
34 |
|
35 |
|
36 def collatz(n: Long) : Long = { |
|
37 if (n == 1) { |
|
38 1L |
|
39 } else { |
|
40 if (n % 2 == 0) { |
|
41 collatz(n/2) + 1 |
|
42 } else { |
|
43 collatz((n*3)+1) + 1 |
|
44 } |
|
45 } |
|
46 } |
|
47 |
|
48 } |
|
49 |
|
50 |
|
51 |
|