- 追加された行はこの色です。
- 削除された行はこの色です。
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
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
