diff -r 40657f9a4e4a -r 663c2a9108d1 pre_testing1/collatz.scala --- a/pre_testing1/collatz.scala Sat Oct 31 16:47:46 2020 +0000 +++ b/pre_testing1/collatz.scala Sun Nov 01 01:21:31 2020 +0000 @@ -1,37 +1,51 @@ -object CW6a { +// Basic Part about the 3n+1 conjecture +//================================== + +// generate jar with +// > scala -d collatz.jar collatz.scala + +object CW6a { // for purposes of generating a jar -//(1) Complete the collatz function below. It should -// recursively calculate the number of steps needed -// until the collatz series reaches the number 1. -// If needed, you can use an auxiliary function that -// performs the recursion. The function should expect -// arguments in the range of 1 to 1 Million. -def stepsCounter(n: Long, s: Long) : Long = n match{ - case 1 => s - case n if(n%2==0) => stepsCounter(n/2,s+1) - case _ => stepsCounter(3*n+1, s+1) +def collatz(n: Long): Long = + if (n == 1) 0 else + if (n % 2 == 0) 1 + collatz(n / 2) else + 1 + collatz(3 * n + 1) + + +def collatz_max(bnd: Long): (Long, Long) = { + val all = for (i <- (1L to bnd)) yield (collatz(i), i) + all.maxBy(_._1) } -def collatz(n: Long) : Long = n match { - case n if(n>0) => stepsCounter(n,0) - case n if(n<=0) => stepsCounter(1,0) +//collatz_max(1000000) +//collatz_max(10000000) +//collatz_max(100000000) + + +/* some test cases +val bnds = List(10, 100, 1000, 10000, 100000, 1000000) + +for (bnd <- bnds) { + val (steps, max) = collatz_max(bnd) + println(s"In the range of 1 - ${bnd} the number ${max} needs the maximum steps of ${steps}") +} + +*/ + +def is_pow(n: Long) : Boolean = (n & (n - 1)) == 0 + +def is_hard(n: Long) : Boolean = is_pow(3 * n + 1) + +def last_odd(n: Long) : Long = + if (is_hard(n)) n else + if (n % 2 == 0) last_odd(n / 2) else + last_odd(3 * n + 1) + + +//for (i <- 130 to 10000) println(s"$i: ${last_odd(i)}") +for (i <- 1 to 100) println(s"$i: ${collatz(i)}") + } -//(2) Complete the collatz_max function below. It should -// calculate how many steps are needed for each number -// from 1 up to a bound and then calculate the maximum number of -// steps and the corresponding number that needs that many -// steps. Again, you should expect bounds in the range of 1 -// up to 1 Million. The first component of the pair is -// the maximum number of steps and the second is the -// corresponding number. - -def collatz_max(bnd: Long) : (Long, Long) = { - val allCollatz = for(i<-1L until bnd) yield collatz(i) - val pair = (allCollatz.max, (allCollatz.indexOf(allCollatz.max) +1).toLong) - pair -} - -}