|
463
|
1 |
import scala.annotation.tailrec
|
|
401
|
2 |
// Core Part 1 about the 3n+1 conjecture
|
|
433
|
3 |
//============================================
|
|
|
4 |
|
|
|
5 |
object C1 {
|
|
|
6 |
|
|
463
|
7 |
@tailrec
|
|
|
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 |
}
|
|
208
|
13 |
|
|
463
|
14 |
def collatz_max(upper: Long): (Long, Long) = {
|
|
|
15 |
(1L to upper).map(n => (collatz(n), n)).maxBy(_._1)
|
|
363
|
16 |
}
|
|
208
|
17 |
|
|
|
18 |
|
|
463
|
19 |
private def is_pow_of_two(n: Long) : Boolean = {
|
|
|
20 |
(n & (n - 1)) == 0
|
|
|
21 |
}
|
|
363
|
22 |
|
|
463
|
23 |
private def is_hard(n: Long) : Boolean = {
|
|
|
24 |
is_pow_of_two(3 * n + 1)
|
|
|
25 |
}
|
|
363
|
26 |
|
|
463
|
27 |
|
|
|
28 |
private def last_odd(n: Long): Long = {
|
|
|
29 |
(1L to n).filter(is_hard).max
|
|
|
30 |
}
|
|
335
|
31 |
|
|
363
|
32 |
}
|
|
335
|
33 |
|
|
|
34 |
|
|
|
35 |
|
|
433
|
36 |
// This template code is subject to copyright
|
|
|
37 |
// by King's College London, 2022. Do not
|
|
|
38 |
// make the template code public in any shape
|
|
|
39 |
// or form, and do not exchange it with other
|
|
|
40 |
// students under any circumstance.
|