core_solution1/collatz.scala
author Christian Urban <christian.urban@kcl.ac.uk>
Thu, 02 Nov 2023 13:53:37 +0000
changeset 474 b528d1d3d3c3
parent 401 9471c3b7ea02
permissions -rw-r--r--
updated
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
399
b17a98b0c52f updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 373
diff changeset
     1
// Core Part 1 about the 3n+1 conjecture
208
f8883f8a14ad updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     2
//==================================
f8883f8a14ad updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     3
266
ca48ac1d3c3e updated to 2.13
Christian Urban <urbanc@in.tum.de>
parents: 208
diff changeset
     4
// generate jar with
ca48ac1d3c3e updated to 2.13
Christian Urban <urbanc@in.tum.de>
parents: 208
diff changeset
     5
//   > scala -d collatz.jar  collatz.scala
208
f8883f8a14ad updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     6
399
b17a98b0c52f updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 373
diff changeset
     7
object C1 { // for purposes of generating a jar
208
f8883f8a14ad updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     8
f8883f8a14ad updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     9
def collatz(n: Long): Long =
f8883f8a14ad updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    10
  if (n == 1) 0 else
f8883f8a14ad updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    11
    if (n % 2 == 0) 1 + collatz(n / 2) else 
f8883f8a14ad updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    12
      1 + collatz(3 * n + 1)
f8883f8a14ad updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    13
f8883f8a14ad updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    14
f8883f8a14ad updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    15
def collatz_max(bnd: Long): (Long, Long) = {
f8883f8a14ad updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    16
  val all = for (i <- (1L to bnd)) yield (collatz(i), i)
f8883f8a14ad updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    17
  all.maxBy(_._1)
f8883f8a14ad updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    18
}
f8883f8a14ad updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    19
320
cdfb2ce30a3d updated
Christian Urban <urbanc@in.tum.de>
parents: 282
diff changeset
    20
//collatz_max(1000000)
401
9471c3b7ea02 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 399
diff changeset
    21
208
f8883f8a14ad updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    22
f8883f8a14ad updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    23
/* some test cases
f8883f8a14ad updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    24
val bnds = List(10, 100, 1000, 10000, 100000, 1000000)
f8883f8a14ad updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    25
f8883f8a14ad updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    26
for (bnd <- bnds) {
f8883f8a14ad updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    27
  val (steps, max) = collatz_max(bnd)
f8883f8a14ad updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    28
  println(s"In the range of 1 - ${bnd} the number ${max} needs the maximum steps of ${steps}")
f8883f8a14ad updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    29
}
f8883f8a14ad updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    30
f8883f8a14ad updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    31
*/
f8883f8a14ad updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    32
373
d29cd5883c7b updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 353
diff changeset
    33
335
7e00d2b13b04 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 320
diff changeset
    34
def is_pow(n: Long) : Boolean = (n & (n - 1)) == 0
7e00d2b13b04 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 320
diff changeset
    35
7e00d2b13b04 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 320
diff changeset
    36
def is_hard(n: Long) : Boolean = is_pow(3 * n + 1)
7e00d2b13b04 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 320
diff changeset
    37
7e00d2b13b04 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 320
diff changeset
    38
def last_odd(n: Long) : Long = 
7e00d2b13b04 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 320
diff changeset
    39
  if (is_hard(n)) n else
7e00d2b13b04 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 320
diff changeset
    40
    if (n % 2 == 0) last_odd(n / 2) else 
7e00d2b13b04 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 320
diff changeset
    41
      last_odd(3 * n + 1)
7e00d2b13b04 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 320
diff changeset
    42
7e00d2b13b04 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 320
diff changeset
    43
373
d29cd5883c7b updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 353
diff changeset
    44
336
25d9c3b2bc99 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 335
diff changeset
    45
//for (i <- 130 to 10000) println(s"$i: ${last_odd(i)}")
353
bb6074814a73 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 346
diff changeset
    46
//for (i <- 1 to 100) println(s"$i: ${collatz(i)}")
335
7e00d2b13b04 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 320
diff changeset
    47
208
f8883f8a14ad updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    48
}
335
7e00d2b13b04 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 320
diff changeset
    49
7e00d2b13b04 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 320
diff changeset
    50
7e00d2b13b04 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 320
diff changeset
    51