ShortestAdditionChain

QuesTion

the Shortest Addition Chain (加法連鎖)

表です。十進ベーシックで出力しました。 右の三つの数字は、左から順に、

　足し算に表れる数値の種類の数

　計算回数

　通常の2進法を利用した場合の計算回数

です。

さて、もちろん、足し算の仕方は何通りもあります。このプログラムでは、

　足し算に現れる数の種類が少ないもの。

　さらにその数の大きさが小さいもの。

というような基準でひとつ選んでいます。（のはずです）

  1=1                                                 1  0  0 
  2=1+1                                               1  1  1 
  3=1+1+1                                             1  2  2 
  4=1+1+2                                             2  2  2 
  5=1+1+2+1                                           2  3  3 
  6=1+1+2+2                                           2  3  3 
  7=1+1+2+2+1                                         2  4  4 
  8=1+1+2+4                                           3  3  3 
  9=1+1+1+3+3                                         2  4  4 
 10=1+1+2+4+2                                         3  4  4 
 11=1+1+1+3+3+2                                       3  5  5 
 12=1+1+2+4+4                                         3  4  4 
 13=1+1+2+4+4+1                                       3  5  5 
 14=1+1+2+4+4+2                                       3  5  5 
 15=1+1+2+1+5+5                                       3  5  6 
 16=1+1+2+4+8                                         4  4  4 
 17=1+1+2+4+8+1                                       4  5  5 
 18=1+1+1+3+6+6                                       3  5  5 
 19=1+1+1+3+6+6+1                                     3  6  6 
 20=1+1+2+4+8+4                                       4  5  5 
 21=1+1+1+3+6+6+3                                     3  6  6 
 22=1+1+2+2+6+6+4                                     4  6  6 
 23=1+1+2+1+4+9+5                                     5  6  7 
 24=1+1+2+4+8+8                                       4  5  5 
 25=1+1+2+4+8+8+1                                     4  6  6 
 26=1+1+2+4+8+8+2                                     4  6  6 
 27=1+1+1+3+3+9+9                                     3  6  7 
 28=1+1+2+4+8+8+4                                     4  6  6 
 29=1+1+2+4+8+8+4+1                                   4  7  7 
 30=1+1+2+1+5+10+10                                   4  6  7 
 31=1+1+2+4+1+9+9+4                                   4  7  8 
 32=1+1+2+4+8+16                                      5  5  5 
 33=1+1+2+4+8+16+1                                    5  6  6 
 34=1+1+2+4+8+16+2                                    5  6  6 
 35=1+1+2+1+5+10+10+5                                 4  7  7 
 36=1+1+1+3+6+12+12                                   4  6  6 
 37=1+1+1+3+6+12+12+1                                 4  7  7 
 38=1+1+2+2+6+12+12+2                                 4  7  7 
 39=1+1+1+3+6+12+12+3                                 4  7  8 
 40=1+1+2+4+8+16+8                                    5  6  6 
 41=1+1+2+4+8+16+8+1                                  5  7  7 
 42=1+1+1+3+6+12+12+6                                 4  7  7 
 43=1+1+2+4+1+8+17+9                                  6  7  8 
 44=1+1+2+4+4+12+12+8                                 5  7  7 
 45=1+1+1+3+6+3+15+15                                 4  7  8 
 46=1+1+2+4+2+8+18+10                                 6  7  8 
 47=1+1+2+1+5+5+15+15+2                               4  8  9 
 48=1+1+2+4+8+16+16                                   5  6  6 
 49=1+1+2+4+8+16+16+1                                 5  7  7 
 50=1+1+2+4+8+16+16+2                                 5  7  7 
 51=1+1+2+4+8+1+17+17                                 5  7  8 
 52=1+1+2+4+8+16+16+4                                 5  7  7 
 53=1+1+2+4+8+16+16+4+1                               5  8  8 
 54=1+1+1+3+3+9+18+18                                 4  7  8 
 55=1+1+1+3+3+9+18+18+1                               4  8  9 
 56=1+1+2+4+8+16+16+8                                 5  7  7 
 57=1+1+1+3+3+9+18+18+3                               4  8  8 
 58=1+1+2+4+8+16+16+8+2                               5  8  8 
 59=1+1+2+4+8+1+17+17+8                               5  8  9 
 60=1+1+2+1+5+10+20+20                                5  7  8 
 61=1+1+2+1+5+10+20+20+1                              5  8  9 
 62=1+1+2+4+8+2+18+18+8                               5  8  9 
 63=1+1+1+3+3+9+18+18+9                               4  8 10 
 64=1+1+2+4+8+16+32                                   6  6  6 
 65=1+1+2+4+8+16+32+1                                 6  7  7 
 66=1+1+2+4+8+16+32+2                                 6  7  7 
 67=1+1+2+4+8+1+17+17+16                              6  8  8 
 68=1+1+2+4+8+16+32+4                                 6  7  7 
 69=1+1+2+1+4+9+5+23+23                               6  8  8 
 70=1+1+2+1+5+10+20+20+10                             5  8  8 
 71=1+1+2+1+5+10+20+20+10+1                           5  9  9 
 72=1+1+1+3+6+12+24+24                                5  7  7 
 73=1+1+1+3+6+12+24+24+1                              5  8  8 
 74=1+1+2+2+6+12+24+24+2                              5  8  8 
 75=1+1+1+3+6+12+24+24+3                              5  8  9 
 76=1+1+2+4+4+12+24+24+4                              5  8  8 
 77=1+1+2+4+1+8+17+34+9                               7  8  9