いけがみです。

> 連鎖も知りたい。最小長も知りたい。
> でもどうやら、完成されたアルゴリズムはない。

なるほど。

D. Bleichenbacher と A. Flammenkamp が最近、
近似アルゴリズムでない、最小加法連鎖を求めるアルゴリズムについて
論文を書いたようです。

Daniel Bleichenbacher and Achim Flammenkamp,
"An efficient algorithm for computing shortest addition chains",
submitted to SIAM Journal of Discrete Mathematics.

これによれば、基本的には地道に定義どおり再帰計算するんだけど、
いくつかの打ち切り条件を使って早めに終われるときは終わるんだとか。
(というのが僕の感想です)

http://wwwhomes.uni-bielefeld.de/achim/addition_chain.html

に投稿中の論文と、計算結果(最小長の表)が置いてあります。

Ruby は
  * 集合の各元に対する操作 <- イテレータ
  * 集合演算(元の追加, 和など) <- Set, Array
  * 多倍長整数演算
がありますから、これらが必要なアルゴリズムの実験には
うってつけだと思います。