Skip to content

Instantly share code, notes, and snippets.

@dacr
Last active May 25, 2024 10:18
Show Gist options
  • Save dacr/defcac98a987d77218746641f5581405 to your computer and use it in GitHub Desktop.
Save dacr/defcac98a987d77218746641f5581405 to your computer and use it in GitHub Desktop.
Collatz conjecture / conjecture de syracuse. / published by https://github.com/dacr/code-examples-manager #f089f2c7-797f-4238-864e-7cf602ae7701/e5e981ada9308ab8e353084e1e23ca3677a68db8
// summary : Collatz conjecture / conjecture de syracuse.
// keywords : scala, math, conjecture, syracuse, @testable
// publish : gist
// authors : David Crosson
// license : Apache NON-AI License Version 2.0 (https://raw.githubusercontent.com/non-ai-licenses/non-ai-licenses/main/NON-AI-APACHE2)
// id : f089f2c7-797f-4238-864e-7cf602ae7701
// created-on : 2019-06-17T06:43:16Z
// managed-by : https://github.com/dacr/code-examples-manager
// run-with : scala-cli $file
// ---------------------
//> using scala "3.4.2"
//> using dep "org.scalatest::scalatest:3.2.10"
// ---------------------
/*
Collatz conjecture wikipedia : https://en.wikipedia.org/wiki/Collatz_conjecture
*/
import org.scalatest._,flatspec._,matchers._
def pathLengthToOne(from:Long):Int = {
@annotation.tailrec
def loop(current:Long, length:Int=0):Int = {
if (current == 1) length else {
if (current % 2 == 0) loop(current / 2, length + 1)
else loop(3 * current +1, length + 1)
}
}
loop(from)
}
def pathToOne(from:Long):List[Long] = {
@annotation.tailrec
def loop(current:Long, currentPath:List[Long]=Nil):List[Long] = {
if (current == 1L) current::currentPath else {
if (current % 2 == 0) loop(current / 2, current::currentPath)
else loop(3 * current +1, current::currentPath)
}
}
loop(from)
}
def highestPathLength(start:Long, end:Long):Int = {
start.to(end).map(pathLengthToOne).max
}
object CollatzConjectureTest extends AnyFlatSpec with should.Matchers {
"collatz conjecture path" should "start with 1" in {
pathToOne(128).head shouldBe 1L
}
it should "last with its start value" in {
pathToOne(17).last shouldBe 17L
}
it should "be possible to get the path up to 1" in {
pathToOne(7) shouldBe List(1, 2, 4, 8, 16, 5, 10, 20, 40, 13, 26, 52, 17, 34, 11, 22, 7)
}
}
CollatzConjectureTest.execute()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment