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 // 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. |
|
9 |
6 |
10 def collatz(n: Long) : Long = |
7 object CW6a { // for purposes of generating a jar |
11 if ( n == 1) 1; |
8 |
12 else if (n % 2 == 0) 1 + collatz( n / 2); |
9 /* |
13 else 1 + collatz( n * 3 + 1); |
10 def collatz(n: Long): Long = |
|
11 if (n == 1) 0 else |
|
12 if (n % 2 == 0) 1 + collatz(n / 2) else |
|
13 1 + collatz(3 * n + 1) |
|
14 */ |
|
15 |
|
16 def aux(n: Long, acc: Long) : Long = |
|
17 if (n == 1) acc else |
|
18 if (n % 2 == 0) aux(n / 2, acc + 1) else |
|
19 aux(3 * n + 1, acc + 1) |
14 |
20 |
15 |
21 |
16 //(2) Complete the collatz_max function below. It should |
22 def collatz(n: Long): Long = aux(n, 0) |
17 // calculate how many steps are needed for each number |
|
18 // from 1 up to a bound and then calculate the maximum number of |
|
19 // steps and the corresponding number that needs that many |
|
20 // steps. Again, you should expect bounds in the range of 1 |
|
21 // up to 1 Million. The first component of the pair is |
|
22 // the maximum number of steps and the second is the |
|
23 // corresponding number. |
|
24 |
23 |
25 def collatz_max(bnd: Long) : (Long, Long) = |
24 def collatz_max(bnd: Long): (Long, Long) = { |
26 ((1.toLong to bnd).toList.map |
25 val all = for (i <- (1L to bnd)) yield (collatz(i), i) |
27 (n => collatz(n)).max , |
26 all.maxBy(_._1) |
28 (1.toLong to bnd).toList.map |
27 } |
29 (n => collatz(n)).indexOf((1.toLong to bnd).toList.map |
|
30 (n => collatz(n)).max) + 1); |
|
31 |
28 |
32 //(3) Implement a function that calculates the last_odd |
29 //collatz_max(1000000) |
33 // number in a collatz series. For this implement an |
30 //collatz_max(10000000) |
34 // is_pow_of_two function which tests whether a number |
31 //collatz_max(100000000) |
35 // is a power of two. The function is_hard calculates |
|
36 // whether 3n + 1 is a power of two. Again you can |
|
37 // assume the input ranges between 1 and 1 Million, |
|
38 // and also assume that the input of last_odd will not |
|
39 // be a power of 2. |
|
40 //idk |
|
41 def is_pow_of_two(n: Long) : Boolean = |
|
42 if ( n & ( n - 1) == 0) true; |
|
43 else false; |
|
44 |
32 |
45 def is_hard(n: Long) : Boolean = |
33 /* some test cases |
46 if ( (3*n + 1) & 3*n == 0) true; |
34 val bnds = List(10, 100, 1000, 10000, 100000, 1000000) |
47 else false; |
35 |
|
36 for (bnd <- bnds) { |
|
37 val (steps, max) = collatz_max(bnd) |
|
38 println(s"In the range of 1 - ${bnd} the number ${max} needs the maximum steps of ${steps}") |
|
39 } |
|
40 |
|
41 */ |
|
42 |
|
43 def is_pow(n: Long) : Boolean = (n & (n - 1)) == 0 |
|
44 |
|
45 def is_hard(n: Long) : Boolean = is_pow(3 * n + 1) |
|
46 |
|
47 def last_odd(n: Long) : Long = |
|
48 if (is_hard(n)) n else |
|
49 if (n % 2 == 0) last_odd(n / 2) else |
|
50 last_odd(3 * n + 1) |
48 |
51 |
49 |
52 |
50 def last_odd(n: Long) : Long = ??? |
53 //for (i <- 130 to 10000) println(s"$i: ${last_odd(i)}") |
|
54 //for (i <- 1 to 100) println(s"$i: ${collatz(i)}") |
|
55 |
|
56 } |
51 |
57 |
52 |
58 |
53 |
59 |
54 } |
|