|
401
|
1 |
// Core Part 1 about the 3n+1 conjecture
|
|
433
|
2 |
//============================================
|
|
|
3 |
|
|
|
4 |
object C1 {
|
|
|
5 |
|
|
|
6 |
// ADD YOUR CODE BELOW
|
|
|
7 |
//======================
|
|
363
|
8 |
|
|
433
|
9 |
// test1 7 Nov
|
|
|
10 |
// test2
|
|
|
11 |
// test3
|
|
|
12 |
// test4
|
|
363
|
13 |
|
|
208
|
14 |
|
|
433
|
15 |
//(1)
|
|
|
16 |
def collatz(n: Long) : Long =
|
|
363
|
17 |
if (n == 1) 0 else
|
|
|
18 |
if (n % 2 == 0) 1 + collatz(n / 2) else
|
|
|
19 |
1 + collatz(3 * n + 1)
|
|
208
|
20 |
|
|
363
|
21 |
|
|
433
|
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 |
|
|
363
|
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 |
}
|
|
208
|
32 |
|
|
|
33 |
|
|
401
|
34 |
|
|
433
|
35 |
//(3)
|
|
|
36 |
|
|
|
37 |
def is_pow_of_two(n: Long) : Boolean = (n & (n - 1)) == 0
|
|
363
|
38 |
|
|
433
|
39 |
def is_hard(n: Long) : Boolean = is_pow_of_two(3 * n + 1)
|
|
363
|
40 |
|
|
433
|
41 |
def last_odd(n: Long) : Long = if (is_hard(n)) n else
|
|
363
|
42 |
if (n % 2 == 0) last_odd(n / 2) else
|
|
|
43 |
last_odd(3 * n + 1)
|
|
335
|
44 |
|
|
363
|
45 |
}
|
|
335
|
46 |
|
|
|
47 |
|
|
|
48 |
|
|
433
|
49 |
// This template code is subject to copyright
|
|
|
50 |
// by King's College London, 2022. Do not
|
|
|
51 |
// make the template code public in any shape
|
|
|
52 |
// or form, and do not exchange it with other
|
|
|
53 |
// students under any circumstance.
|