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