1 // Core Part 1 about the 3n+1 conjecture |
1 // Core Part 1 about the 3n+1 conjecture |
2 //================================== |
2 //============================================ |
3 |
3 |
4 // generate jar with |
4 object C1 { |
5 // > scala -d collatz.jar collatz.scala |
|
6 |
5 |
7 object C1 { // for purposes of generating a jar |
6 // ADD YOUR CODE BELOW |
|
7 //====================== |
8 |
8 |
9 def collatz(n: Long): Long = |
9 // test1 7 Nov |
|
10 // test2 |
|
11 // test3 |
|
12 // test4 |
|
13 |
|
14 |
|
15 //(1) |
|
16 def collatz(n: Long) : Long = |
10 if (n == 1) 0 else |
17 if (n == 1) 0 else |
11 if (n % 2 == 0) 1 + collatz(n / 2) else |
18 if (n % 2 == 0) 1 + collatz(n / 2) else |
12 1 + collatz(3 * n + 1) |
19 1 + collatz(3 * n + 1) |
13 |
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 //} |
14 |
27 |
15 def collatz_max(bnd: Long): (Long, Long) = { |
28 def collatz_max(bnd: Long): (Long, Long) = { |
16 val all = for (i <- (1L to bnd)) yield (collatz(i), i) |
29 val all = for (i <- (1L to bnd)) yield (collatz(i), i) |
17 all.maxBy(_._1) |
30 all.maxBy(_._1) |
18 } |
31 } |
19 |
32 |
20 //collatz_max(1000000) |
|
21 |
33 |
22 |
34 |
23 /* some test cases |
35 //(3) |
24 val bnds = List(10, 100, 1000, 10000, 100000, 1000000) |
|
25 |
36 |
26 for (bnd <- bnds) { |
37 def is_pow_of_two(n: Long) : Boolean = (n & (n - 1)) == 0 |
27 val (steps, max) = collatz_max(bnd) |
|
28 println(s"In the range of 1 - ${bnd} the number ${max} needs the maximum steps of ${steps}") |
|
29 } |
|
30 |
38 |
31 */ |
39 def is_hard(n: Long) : Boolean = is_pow_of_two(3 * n + 1) |
32 |
40 |
33 |
41 def last_odd(n: Long) : Long = if (is_hard(n)) n else |
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 |
42 if (n % 2 == 0) last_odd(n / 2) else |
41 last_odd(3 * n + 1) |
43 last_odd(3 * n + 1) |
42 |
|
43 |
|
44 |
|
45 //for (i <- 130 to 10000) println(s"$i: ${last_odd(i)}") |
|
46 //for (i <- 1 to 100) println(s"$i: ${collatz(i)}") |
|
47 |
44 |
48 } |
45 } |
49 |
46 |
50 |
47 |
51 |
48 |
|
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. |