|
1 // Part 1 about the 3n+1 conceture |
|
2 //================================= |
|
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 1 Million. |
|
10 |
|
11 def collatz(n: Long): List[Long] = |
|
12 if (n == 1) List(1) else |
|
13 if (n % 2 == 0) (n::collatz(n / 2)) else |
|
14 (n::collatz(3 * n + 1)) |
|
15 |
|
16 |
|
17 // an alternative that calculates the steps directly |
|
18 def collatz1(n: Long): Int = |
|
19 if (n == 1) 1 else |
|
20 if (n % 2 == 0) (1 + collatz1(n / 2)) else |
|
21 (1 + collatz1(3 * n + 1)) |
|
22 |
|
23 import scala.annotation.tailrec |
|
24 |
|
25 @tailrec |
|
26 def collatz2(n: Long, acc: Long): Long = |
|
27 if (n == 1) acc else |
|
28 if (n % 2 == 0) collatz2(n / 2, acc + 1) else |
|
29 collatz2(3 * n + 1, acc + 1) |
|
30 |
|
31 |
|
32 //(2) Complete the collatz bound function below. It should |
|
33 // calculuate how many steps are needed for each number |
|
34 // from 1 upto a bound and return the maximum number of |
|
35 // steps and the corresponding number that needs that many |
|
36 // steps. You should expect bounds in the range of 1 |
|
37 // upto 1 million. |
|
38 |
|
39 def collatz_max(bnd: Long): (Long, Long) = { |
|
40 (1L to bnd).view.map((i) => (collatz2(i, 1), i)).maxBy(_._1) |
|
41 } |
|
42 |
|
43 |
|
44 // some testing harness |
|
45 //val bnds = List(10, 100, 1000, 10000, 100000, 1000000) |
|
46 val bnds = List(10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000) |
|
47 |
|
48 for (bnd <- bnds) { |
|
49 val (steps, max) = collatz_max(bnd) |
|
50 println(s"In the range of 1 - ${bnd} the number ${max} needs the maximum steps of ${steps}") |
|
51 } |
|
52 |
|
53 |
|
54 //val all = for (i <- (1 to 100000).toList) yield collatz1(i) |
|
55 //println(all.sorted.reverse.take(10)) |