■剰余系と整数生成定規(その58)
一般に,1からnまですべてはかれるようにするにはどうしたらいいか?
らとえば,n=41が可能な集合として,
t={12,13,16,25,28,29,41}
がある.
===================================
差分集合
d={12,13−12,16−13,25−16,28−25,29−28,41−29}
={12,1,3,9,3,1,12}
={1,1,3,3,9,12,12}
各1回まで使うことができるから
{1,3,9,12}
の9を除き,2回使えると考えてよい.面倒くさがらずに計算すると
1=1
2=2・1
3=3
4=1+3
5=2・1+3
6=2・3
7=1+2・3
8=2・1+2・3
9=9
10=1+9
11=2・1+9
12=3+9
14=2・1+3+9
15=2・3+9
16=1+2・3+9
17=2・1+2・3+9
ここまでは{1,1,3,3,9}で生成できた.
17+1=12+6 30=2・12+6
17+k=12+5+k 30+k=2・12+5+k
29=12+17 41=2・12+17
こうして,1から41まですべて生成することができる.
===================================