having fun with subtrees

trees.scala

case class Node(left: Option[Node] = None, right: Option[Node] = None) {
  lazy val size: Int = 1 + left.map(_.size).getOrElse(0) + right.map(_.size).getOrElse(0)
  lazy val sum:Int = size +left.map(_.sum).getOrElse(0) + right.map(_.sum).getOrElse(0)
}

def tree(n: Int): Node = {
  assert(n>0)
  n match {
    case 1 => Node()
    case 2 => Node(Some(Node()), None)
    case _ => 
      val l = (n-1) / 2
      Node(Some(tree(l)), Some(tree(n-1-l)))
  }
}


(1 to 100) forall (n => tree(n).size == n)

def test(n:Int) = tree(n).sum.toDouble / n / (math.log(n) / math.log(2) - 1)


///////////////////////////////////////////////////

case class Node(children: Seq[Node] = Nil){
  lazy val size: Int = 1 + children.foldLeft(0)(_+_.size)
  lazy val sum: Int = size + children.foldLeft(0)(_+_.sum)
}

def tree(b: Int, d: Int): Node =
    if(d<=1) 
      Node()
    else 
      Node( (1 to b).map(_ => tree(b, d-1)) )

def test(b: Int, d: Int) = {
  val t = tree(b,d)
  t.sum / t.size / (math.log(t.size) / math.log(b) -1)
}

/////////////////////////////////////////////////
import BigInt.int2bigInt

def log(n: BigInt, base: Int): Double = {
  val len = n.toString(base).length
  math.log( (BigDecimal(n) / BigDecimal(base).pow(len)).doubleValue ) / math.log(base) + len
}

def test(b: Int, d: Int) = {
  def calc(i: Int): (BigInt,BigInt) = {
    if (i<=1) (1,1)
    else {
      val (size,sum) = calc(i-1)
      val curSize = b*size+1
      (curSize, curSize + b*sum)
    }
  }
  val (size,sum) = calc(d)
  (BigDecimal(sum) / BigDecimal(size)) / (log(size,b)-1)
}

///////////////////////////////////////////////

def test(b: Int, d: Int) = {
  def calc(i: Int, size: BigInt, sum: BigInt): (BigInt,BigInt)= {
    if (i==d) (size,sum)
    else {
      val curSize = b*size+1
      calc(i+1, curSize, curSize+b*sum)
    }
  }
  val (size,sum) = calc(1,1,1)
  (BigDecimal(sum) / BigDecimal(size)) / (log(size,b)-1)
}

////////////////////////////////////////////////
/* 
wolfram alpha
  (((b^d-1)/(b-1)),(1+b^(1+d) d-b^d (1+d))/(-1+b)^2) where b = 3, d = 12  
  
  (1+b^(1+d) d-b^d (1+d))/((-1+b) (-1+b^d)) / (d-1) where b=2, d=10
*/

import BigInt.int2bigInt

def ratio(b: Int, d: Int) = (BigDecimal((b pow (d+1)) * d - (b pow d) * (d + 1) + 1) / BigDecimal((b-1)*((b pow d) - 1)))/BigDecimal(d-1)