1 object CW6a { |
1 // Basic Part about the 3n+1 conjecture |
|
2 //================================== |
2 |
3 |
3 //(1) Complete the collatz function below. It should |
4 // generate jar with |
4 // recursively calculate the number of steps needed |
5 // > scala -d collatz.jar collatz.scala |
5 // until the collatz series reaches the number 1. |
6 |
6 // If needed, you can use an auxiliary function that |
7 object CW6a { // for purposes of generating a jar |
7 // performs the recursion. The function should expect |
8 |
8 // arguments in the range of 1 to 1 Million. |
9 def collatz(n: Long): Long = |
9 def stepsCounter(n: Long, s: Long) : Long = n match{ |
10 if (n == 1) 0 else |
10 case 1 => s |
11 if (n % 2 == 0) 1 + collatz(n / 2) else |
11 case n if(n%2==0) => stepsCounter(n/2,s+1) |
12 1 + collatz(3 * n + 1) |
12 case _ => stepsCounter(3*n+1, s+1) |
13 |
|
14 |
|
15 def collatz_max(bnd: Long): (Long, Long) = { |
|
16 val all = for (i <- (1L to bnd)) yield (collatz(i), i) |
|
17 all.maxBy(_._1) |
13 } |
18 } |
14 |
19 |
15 def collatz(n: Long) : Long = n match { |
20 //collatz_max(1000000) |
16 case n if(n>0) => stepsCounter(n,0) |
21 //collatz_max(10000000) |
17 case n if(n<=0) => stepsCounter(1,0) |
22 //collatz_max(100000000) |
|
23 |
|
24 |
|
25 /* some test cases |
|
26 val bnds = List(10, 100, 1000, 10000, 100000, 1000000) |
|
27 |
|
28 for (bnd <- bnds) { |
|
29 val (steps, max) = collatz_max(bnd) |
|
30 println(s"In the range of 1 - ${bnd} the number ${max} needs the maximum steps of ${steps}") |
|
31 } |
|
32 |
|
33 */ |
|
34 |
|
35 def is_pow(n: Long) : Boolean = (n & (n - 1)) == 0 |
|
36 |
|
37 def is_hard(n: Long) : Boolean = is_pow(3 * n + 1) |
|
38 |
|
39 def last_odd(n: Long) : Long = |
|
40 if (is_hard(n)) n else |
|
41 if (n % 2 == 0) last_odd(n / 2) else |
|
42 last_odd(3 * n + 1) |
|
43 |
|
44 |
|
45 //for (i <- 130 to 10000) println(s"$i: ${last_odd(i)}") |
|
46 for (i <- 1 to 100) println(s"$i: ${collatz(i)}") |
|
47 |
18 } |
48 } |
19 |
49 |
20 |
50 |
21 |
51 |
22 //(2) Complete the collatz_max function below. It should |
|
23 // calculate how many steps are needed for each number |
|
24 // from 1 up to a bound and then calculate the maximum number of |
|
25 // steps and the corresponding number that needs that many |
|
26 // steps. Again, you should expect bounds in the range of 1 |
|
27 // up to 1 Million. The first component of the pair is |
|
28 // the maximum number of steps and the second is the |
|
29 // corresponding number. |
|
30 |
|
31 def collatz_max(bnd: Long) : (Long, Long) = { |
|
32 val allCollatz = for(i<-1L until bnd) yield collatz(i) |
|
33 val pair = (allCollatz.max, (allCollatz.indexOf(allCollatz.max) +1).toLong) |
|
34 pair |
|
35 } |
|
36 |
|
37 } |
|