13 if (n % 2 == 0) (n::collatz(n / 2)) else |
13 if (n % 2 == 0) (n::collatz(n / 2)) else |
14 (n::collatz(3 * n + 1)) |
14 (n::collatz(3 * n + 1)) |
15 |
15 |
16 |
16 |
17 // an alternative that calculates the steps directly |
17 // an alternative that calculates the steps directly |
18 def collatz1(n: Long): Int = |
18 def collatz1(n: Long): Long = |
19 if (n == 1) 1 else |
19 if (n == 1) 1 else |
20 if (n % 2 == 0) (1 + collatz1(n / 2)) else |
20 if (n % 2 == 0) (1 + collatz1(n / 2)) else |
21 (1 + collatz1(3 * n + 1)) |
21 (1 + collatz1(3 * n + 1)) |
22 |
22 |
23 import scala.annotation.tailrec |
23 import scala.annotation.tailrec |
35 // steps and the corresponding number that needs that many |
35 // steps and the corresponding number that needs that many |
36 // steps. You should expect bounds in the range of 1 |
36 // steps. You should expect bounds in the range of 1 |
37 // upto 1 million. |
37 // upto 1 million. |
38 |
38 |
39 def collatz_max(bnd: Long): (Long, Long) = { |
39 def collatz_max(bnd: Long): (Long, Long) = { |
40 (1L to bnd).view.map((i) => (collatz2(i, 1), i)).maxBy(_._1) |
40 (1L to bnd).view.map((i) => (collatz1(i), i)).maxBy(_._1) |
41 } |
41 } |
42 |
42 |
43 |
43 |
44 // some testing harness |
44 // some testing harness |
45 //val bnds = List(10, 100, 1000, 10000, 100000, 1000000) |
45 //val bnds = List(10, 100, 1000, 10000, 100000, 1000000) |
46 val bnds = List(10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000) |
46 val bnds = List(10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 2000000000) |
|
47 |
|
48 |
47 |
49 |
48 for (bnd <- bnds) { |
50 for (bnd <- bnds) { |
49 val (steps, max) = collatz_max(bnd) |
51 val (steps, max) = collatz_max(bnd) |
50 println(s"In the range of 1 - ${bnd} the number ${max} needs the maximum steps of ${steps}") |
52 println(s"In the range of 1 - ${bnd} the number ${max} needs the maximum steps of ${steps}") |
51 } |
53 } |