Exploring the Collatz conjecture on the Scala REPL
Yesterday I wrote about the Collatz conjecture. I mentioned that you can use a computer to help you explore the Collatz conjecture. If you have Scala on your computer, you can use the Scala Read-Eval-Print-Loop (REPL) sort of like a Mathematica or Python notebook.
You can use the Scala REPL like a glorified calculator.
scala> 27 * 3 + 1
res0: Int = 82scala> 82 / 2
res1: Int = 41scala> 41 * 3 + 1
res2: Int = 124scala> 124 / 2
res3: Int = 62scala> 62 / 2
res4: Int = 31scala>
We should define a function so that we don’t have to keep typing times 3 plus 1 or divide by 2.
scala> def f(n: Int): Int = (n % 2) match {
| case 0 => n / 2
| case _ => 3 * n + 1
| }
f: (n: Int)Intscala> f(31)
res5: Int = 94scala> f(94)
res6: Int = 47scala> f(47)
res7: Int = 142
Still, we can streamline this further.
scala> LazyList.iterate(27)(f)
res8: scala.collection.immutable.LazyList[Int] = LazyList(<not computed>)scala> res8.take(120).toList
res9: List[Int] = List(27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2)
Alright, this is good, but I’d like some way to have the computer calculate more of these details automatically. I’m working on a Collatz tree mapper (source and tests available on GitHub).
scala> val tree = new main.IntegerTree(f)
tree: main.IntegerTree = main.IntegerTree@46f597f1scala> tree.query(27)
res11: List[Int] = List(27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1)scala> res11.size - 1
res12: Int = 111scala> tree.query(514048)
res13: List[Int] = List(514048, 257024, 128512, 64256, 32128, 16064, 8032, 4016, 2008, 1004, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1)
I am working towards a program that will draw a tree or chart for these numbers. There is no reason why a program with a graphical user interface can’t be invoked from the Scala REPL. I plan to update this article when that program is ready.