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