|
1 import scala.annotation.tailrec |
1 // Core Part 1 about the 3n+1 conjecture |
2 // Core Part 1 about the 3n+1 conjecture |
2 //============================================ |
3 //============================================ |
3 |
4 |
4 object C1 { |
5 object C1 { |
5 |
6 |
6 // ADD YOUR CODE BELOW |
7 @tailrec |
7 //====================== |
8 private def collatz(n: Long, steps: Long = 0): Long = { |
|
9 if (n == 1) steps |
|
10 else if (n % 2 == 0) collatz(n / 2, steps + 1) |
|
11 else collatz(n * 3 + 1, steps + 1) |
|
12 } |
8 |
13 |
9 // test1 7 Nov |
14 def collatz_max(upper: Long): (Long, Long) = { |
10 // test2 |
15 (1L to upper).map(n => (collatz(n), n)).maxBy(_._1) |
11 // test3 |
|
12 // test4 |
|
13 |
|
14 |
|
15 //(1) |
|
16 def collatz(n: Long) : Long = |
|
17 if (n == 1) 0 else |
|
18 if (n % 2 == 0) 1 + collatz(n / 2) else |
|
19 1 + collatz(3 * n + 1) |
|
20 |
|
21 |
|
22 //(2) |
|
23 //def collatz_max(bnd: Long) : (Long, Long) = { |
|
24 // val all = for (i <- (1L to bnd)) yield (collatz(i), i) |
|
25 // all.maxBy(_._1) |
|
26 //} |
|
27 |
|
28 def collatz_max(bnd: Long): (Long, Long) = { |
|
29 val all = for (i <- (1L to bnd)) yield (collatz(i), i) |
|
30 all.maxBy(_._1) |
|
31 } |
16 } |
32 |
17 |
33 |
18 |
|
19 private def is_pow_of_two(n: Long) : Boolean = { |
|
20 (n & (n - 1)) == 0 |
|
21 } |
34 |
22 |
35 //(3) |
23 private def is_hard(n: Long) : Boolean = { |
|
24 is_pow_of_two(3 * n + 1) |
|
25 } |
36 |
26 |
37 def is_pow_of_two(n: Long) : Boolean = (n & (n - 1)) == 0 |
|
38 |
27 |
39 def is_hard(n: Long) : Boolean = is_pow_of_two(3 * n + 1) |
28 private def last_odd(n: Long): Long = { |
40 |
29 (1L to n).filter(is_hard).max |
41 def last_odd(n: Long) : Long = if (is_hard(n)) n else |
30 } |
42 if (n % 2 == 0) last_odd(n / 2) else |
|
43 last_odd(3 * n + 1) |
|
44 |
31 |
45 } |
32 } |
46 |
33 |
47 |
34 |
48 |
35 |