import scala.annotation.tailrec
// Core Part 1 about the 3n+1 conjecture
//============================================

object C1 {

@tailrec
private def collatz(n: Long, steps: Long = 0): Long = {
  if (n == 1) steps
  else if (n % 2 == 0) collatz(n / 2, steps + 1)
  else collatz(n * 3 + 1, steps + 1)
}

def collatz_max(upper: Long): (Long, Long) = {
  (1L to upper).map(n => (collatz(n), n)).maxBy(_._1)
}


private def is_pow_of_two(n: Long) : Boolean = {
  (n & (n - 1)) == 0
}

private def is_hard(n: Long) : Boolean = {
  is_pow_of_two(3 * n + 1)
}


private def last_odd(n: Long): Long = {
  (1L to n).filter(is_hard).max
}

}



// This template code is subject to copyright 
// by King's College London, 2022. Do not 
// make the template code public in any shape 
// or form, and do not exchange it with other 
// students under any circumstance.