Collatz conjecture / conjecture de syracuse. / published by https://github.com/dacr/code-examples-manager #f089f2c7-797f-4238-864e-7cf602ae7701/9169b385ba76b71c61bedf0127b563ab364ee5cb

math-collatz-conjecture.sc

// 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.1.1"
//> 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()