progs/collatz_sol.scala
author Christian Urban <urbanc@in.tum.de>
Tue, 07 Nov 2017 13:08:18 +0000
changeset 127 b4def82f3f9f
parent 123 556cd74cbba9
child 140 ecec79b9ab25
permissions -rw-r--r--
updated
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
127
b4def82f3f9f updated
Christian Urban <urbanc@in.tum.de>
parents: 123
diff changeset
     1
// Part 1 about the 3n+1 conjecture
b4def82f3f9f updated
Christian Urban <urbanc@in.tum.de>
parents: 123
diff changeset
     2
//==================================
11
417869f65585 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
     3
127
b4def82f3f9f updated
Christian Urban <urbanc@in.tum.de>
parents: 123
diff changeset
     4
object CW6a {
123
556cd74cbba9 updated
Christian Urban <urbanc@in.tum.de>
parents: 64
diff changeset
     5
127
b4def82f3f9f updated
Christian Urban <urbanc@in.tum.de>
parents: 123
diff changeset
     6
def collatz(n: Long): Long =
b4def82f3f9f updated
Christian Urban <urbanc@in.tum.de>
parents: 123
diff changeset
     7
  if (n == 1) 1 else
b4def82f3f9f updated
Christian Urban <urbanc@in.tum.de>
parents: 123
diff changeset
     8
    if (n % 2 == 0) 1 + collatz(n / 2) else 
b4def82f3f9f updated
Christian Urban <urbanc@in.tum.de>
parents: 123
diff changeset
     9
      1 + collatz(3 * n + 1)
15
52713e632ac0 updated
Christian Urban <urbanc@in.tum.de>
parents: 11
diff changeset
    10
11
417869f65585 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    11
127
b4def82f3f9f updated
Christian Urban <urbanc@in.tum.de>
parents: 123
diff changeset
    12
def collatz_max(bnd: Long): (Long, Long) = {
b4def82f3f9f updated
Christian Urban <urbanc@in.tum.de>
parents: 123
diff changeset
    13
  val all = for (i <- (1 to bnd.toInt).toList) yield collatz(i)
18
87e55eb309ed updated
Christian Urban <urbanc@in.tum.de>
parents: 17
diff changeset
    14
  val max = all.max
127
b4def82f3f9f updated
Christian Urban <urbanc@in.tum.de>
parents: 123
diff changeset
    15
  (max, all.indexOf(max) + 1)
11
417869f65585 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    16
}
417869f65585 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    17
417869f65585 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    18
127
b4def82f3f9f updated
Christian Urban <urbanc@in.tum.de>
parents: 123
diff changeset
    19
// some testing harness...5 Mio pushes the envelope
b4def82f3f9f updated
Christian Urban <urbanc@in.tum.de>
parents: 123
diff changeset
    20
b4def82f3f9f updated
Christian Urban <urbanc@in.tum.de>
parents: 123
diff changeset
    21
val bnds = List(2, 10, 100, 1000, 10000, 100000, 
b4def82f3f9f updated
Christian Urban <urbanc@in.tum.de>
parents: 123
diff changeset
    22
		77000, 90000, 1000000, 5000000)
11
417869f65585 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    23
417869f65585 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    24
for (bnd <- bnds) {
127
b4def82f3f9f updated
Christian Urban <urbanc@in.tum.de>
parents: 123
diff changeset
    25
  val (steps, max) = collatz_max(bnd)
18
87e55eb309ed updated
Christian Urban <urbanc@in.tum.de>
parents: 17
diff changeset
    26
  println(s"In the range of 1 - ${bnd} the number ${max} needs the maximum steps of ${steps}")
11
417869f65585 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    27
}
417869f65585 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    28
18
87e55eb309ed updated
Christian Urban <urbanc@in.tum.de>
parents: 17
diff changeset
    29
127
b4def82f3f9f updated
Christian Urban <urbanc@in.tum.de>
parents: 123
diff changeset
    30
}
123
556cd74cbba9 updated
Christian Urban <urbanc@in.tum.de>
parents: 64
diff changeset
    31