第10章 第3の基数

R
  • 予習の記事はこちら
  • ある数 M が与えられたときの最適な位取り記数法を求める
  • 一般化して各位が全て同じ基数とは限らないとしておく
  • \{r_i\}：各位の位取りの基数をおさめた数列
  • まず\{r_i\}の最適な要素数 w を求める
    • w を固定するたびに \prod_{w} r_i -1 \geq M の条件のもとで\sum_{w} r_i を最小にする\{r_i\}を求める
      • （\sum_{w} r_i が効率、本文でいうrwに相当）
    • 不等式（相加相乗平均の関係）より \sum r_i \geq w (M+1)^{\frac{1}{w}}
    • (M+1)^{\frac{1}{w}} が整数なら r_i = (M+1)^{\frac{1}{w}}
    • 整数でないなら \sum r_i = [w(M+1)^{\frac{1}{w}}]+1 をできるだけ均等にr_iに分配する
  • 以上を用いて、ある M が与えられたとき、最適な w がもとまる
    • これは w をいろいろふって\sum r_i が最も小さくなる w を選べばよい
  • この w について \{r_i\}_{i=1}^{w} が求まる
    • できるだけ均等に分配する
  • 本当は w が M を用いて表されるので r_i も M のみを用いて表されるはずで、これによって r_i \sim 3 となるところを確かめることができるはず
  • さらにポテンシャルというものを\frac{\prod r_i -1}{\sum r_i}で考える
    • これは "表せる最大数/効率" を表す
  • 予想として M が与えられたとき、最も効率のよい w と \{r_i \} のとき最もポテンシャルの値が小さくなる?