diff -r 1bde878ba6c9 -r e5c1d69cffa4 pre_testing1/collatz.scala --- a/pre_testing1/collatz.scala Tue Nov 17 00:34:55 2020 +0000 +++ b/pre_testing1/collatz.scala Wed Nov 18 01:54:39 2020 +0000 @@ -1,54 +1,59 @@ -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 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(n: Long) : Long = - if ( n == 1) 1; - else if (n % 2 == 0) 1 + collatz( n / 2); - else 1 + collatz( n * 3 + 1); +def aux(n: Long, acc: Long) : Long = + if (n == 1) acc else + if (n % 2 == 0) aux(n / 2, acc + 1) else + aux(3 * n + 1, acc + 1) -//(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(n: Long): Long = aux(n, 0) + +def collatz_max(bnd: Long): (Long, Long) = { + val all = for (i <- (1L to bnd)) yield (collatz(i), i) + all.maxBy(_._1) +} -def collatz_max(bnd: Long) : (Long, Long) = - ((1.toLong to bnd).toList.map - (n => collatz(n)).max , - (1.toLong to bnd).toList.map - (n => collatz(n)).indexOf((1.toLong to bnd).toList.map - (n => collatz(n)).max) + 1); +//collatz_max(1000000) +//collatz_max(10000000) +//collatz_max(100000000) + +/* some test cases +val bnds = List(10, 100, 1000, 10000, 100000, 1000000) -//(3) Implement a function that calculates the last_odd -// number in a collatz series. For this implement an -// is_pow_of_two function which tests whether a number -// is a power of two. The function is_hard calculates -// whether 3n + 1 is a power of two. Again you can -// assume the input ranges between 1 and 1 Million, -// and also assume that the input of last_odd will not -// be a power of 2. -//idk - def is_pow_of_two(n: Long) : Boolean = - if ( n & ( n - 1) == 0) true; - else false; +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_hard(n: Long) : Boolean = - if ( (3*n + 1) & 3*n == 0) true; - else false; +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) -def last_odd(n: Long) : Long = ??? +//for (i <- 130 to 10000) println(s"$i: ${last_odd(i)}") +//for (i <- 1 to 100) println(s"$i: ${collatz(i)}") + +} -}