xi+yj(i=1,2,･･･,6,j=1,2,･･･,6) の和を作ると、２から３７までのすべての整数がちょうど１度ずつ
現れるようにするには、どのようなグループ分けをしておけば可能か？
らすかるさんからのコメントです。（平成２８年１１月４日付け）
(x1,x2,x3,x4,x5,x6)=(1,7,13,19,25,31)、(y1,y2,y3,y4,y5,y6)=(1,2,3,4,5,6) と分ければよい。
りらひいさんからのコメントです。（平成２８年１１月４日付け）
他には、 (x1,x2,x3,x4,x5,x6)=(1,4,7,10,13,16)、(y1,y2,y3,y4,y5,y6)=(1,2,3,19,20,21)
(x1,x2,x3,x4,x5,x6)=(1,3,5,7,9,11)、(y1,y2,y3,y4,y5,y6)=(1,2,13,14,25,26)
ＧＡＩさんからのコメントです。（平成２８年１１月５日付け）
らすかるさんのも含めてあと４タイプ作れます。
りらひいさんからのコメントです。（平成２８年１１月５日付け）
全部である証明はできていないけど、はいどうぞ。
(x1,x2,x3,x4,x5,x6)=(1,4,13,16,25,28)、(y1,y2,y3,y4,y5,y6)=(1,2,3,7,8,9)
(x1,x2,x3,x4,x5,x6)=(1,4,7,19,22,25)、(y1,y2,y3,y4,y5,y6)=(1,2,3,10,11,12)
(x1,x2,x3,x4,x5,x6)=(1,3,13,15,25,27)、(y1,y2,y3,y4,y5,y6)=(1,2,5,6,9,10)
(x1,x2,x3,x4,x5,x6)=(1,3,5,19,21,23)、(y1,y2,y3,y4,y5,y6)=(1,2,7,8,13,14)
ＧＡＩさんからのコメントです。（平成２８年１１月６日付け）
はい、これで全部だと思います。なんかもう出し方を会得されたようですね。
バージョンアップを図り、 (x1,x2,x3,x4,x5,x6,x7,x8,x9,x10)、(y1,y2,y3,y4,y5,y6,y7,y8,y9,y10)
の２組に対し、xi+yj (i=1,2,･･･,10;j=1,2,･･･,10) が2〜101を一度だけ構成するもののすべて
の組合せは？（10タイプは越えることはないと思います。たぶん）
これに挑戦する時間がとれましたらやってみて下さい。（私は丸一日は要しました。）
らすかるさんからのコメントです。（平成２８年１１月６日付け）
プログラムを作って調べたところ、
(1,2,21,22,41,42,61,62,81,82),(1,3,5,7,9,11,13,15,17,19)
(1,2,3,4,5,51,52,53,54,55),(1,6,11,16,21,26,31,36,41,46)
(1,2,11,12,21,22,31,32,41,42),(1,3,5,7,9,51,53,55,57,59)
(1,2,3,4,5,26,27,28,29,30),(1,6,11,16,21,51,56,61,66,71)
(1,2,5,6,9,10,13,14,17,18),(1,3,21,23,41,43,61,63,81,83)
(1,2,3,4,5,11,12,13,14,15),(1,6,21,26,41,46,61,66,81,86)
(1,2,3,4,5,6,7,8,9,10),(1,11,21,31,41,51,61,71,81,91)
の7通りとなりました。そして、16個×2までそれぞれ何通りかを調べて、「A273013」に行きあ
たりました。
1組の個数が素数(2,3,5,7,11,…)の時、1通り、
異なる2つの素因数の積(6,10,14,15,21,…)の時、7通り、
1つの素因数の2乗(4,9,25,49,…)の時、3通り、
1つの素因数の3乗(8,27,125,343,…)の時、10通り、
p×q^2形(12,18,20,28,…)の時、42通り
などのように、素因数分解したときの指数で個数が決まるようです。
りらひいさんからのコメントです。（平成２８年１１月７日付け）
私は一般の形に持っていくのが好きなので、一般形で列挙してみました。
xi、yi を0以上の整数として、xi+yi が0からn2-1を網羅する組み合わせとした方が美しいの
で、以下ではそのようにしています。
GAIさんの条件（xi、yi を自然数として、xi+yi が2からn2+1を網羅する組み合わせ）にすると
きは、以下に示すxi、yi のすべてにプラス1してください。
（以下で、Π[k=1〜0](kの関数) = 1 とします。）
ｎを素因数分解したときの各素因数の指数の和（ｎの素因数の総数）をMとおく。
[A] ｍを1以上M以下の整数とする。s[k]、t[k] (k=1,…m) を1より大きなｎの約数として、
ｎ = Π[k=1〜m]s[k] 、ｎ = Π[k=1〜m]t[k]
と分解する。集合X、Yを次のように決める。
X = {Σ[k=1〜m](i[k](Π[a=1〜k-1]s[a])(Π[b=1〜k-1]t[b]))|i[k]∈{0,…,s[k]-1} (k=1,…,m) }
Y = {Σ[k=1〜m](j[k](Π[a=1〜k]s[a])(Π[b=1〜k-1]t[b]))|j[k]∈{0,…,t[k]-1} (k=1,…,m) }
このとき、{ x+y | x∈X, y∈Y } = {0,…,n^2-1} となる。
[B] ｍを2以上M以下の整数とする。s[k]、t[k] (k=1,…m) を1より大きなｎの約数として、
ｎ = Π[k=1〜m]s[k] 、ｎ = Π[k=1〜m-1]t[k]
と分解する。集合X、Yを次のように決める。
X = {Σ[k=1〜m](i[k](Π[a=1〜k-1]s[a])(Π[b=1〜k-1]t[b]))|i[k]∈{0,…,s[k]-1} (k=1,…,m) }
Y = {Σ[k=1〜m-1](j[k](Π[a=1〜k]s[a])(Π[b=1〜k-1]t[b]))|j[k]∈{0,…,t[k]-1} (k=1,…,m-1) }
このとき、{ x+y | x∈X, y∈Y } = {0,…,n^2-1} となる。
分かりにくいので、例をひとつあげておきます。
n=10 のとき、n=2*5なので、M=2
[A] 1≦ｍ≦2
(A1) ｍ=1 のとき、(s[1],t[1]) = (10,10) となる。X = {i[1]|i[1]=0,1,…,9 }、Y = {j[1]*10|j[1]=0,1,…,9 }
とすれば、{ x+y | x∈X, y∈Y } = {0,…,n^2-1}
(A2) ｍ=2 のとき、(s[1],s[2];t[1],t[2]) = (2,5;2,5)または(2,5;5,2)または(5,2;2,5)または(5,2;5,2)
となる。
{A2-1} (s[1],s[2];t[1],t[2]) = (2,5;2,5) のとき、
X = {i[1]+i[2]*4|i[1]=0,1 ; i[2]=0,1,…,4} 、Y = {j[1]*2+j[2]*20|j[1]=0,1 ; j[2]=0,1,…,4}
とすれば、{ x+y | x∈X, y∈Y } = {0,…,n^2-1}
{A2-2} (s[1],s[2];t[1],t[2]) = (2,5;5,2) のとき、
X = {i[1]+i[2]*10|i[1]=0,1 ; i[2]=0,1,…,4} 、Y = {j[1]*2+j[2]*50|j[1]=0,1,…,4 ; j[2]=0,1}
とすれば、{ x+y | x∈X, y∈Y } = {0,…,n^2-1}
{A2-3} (s[1],s[2];t[1],t[2]) = (5,2;2,5) のとき、
X = {i[1]+i[2]*10|i[1]=0,1,…,4 ; i[2]=0,1} 、Y = {j[1]*5+j[2]*20|j[1]=0,1 ; j[2]=0,1,…,4}
とすれば、{ x+y | x∈X, y∈Y } = {0,…,n^2-1}
{A2-4} (s[1],s[2];t[1],t[2]) = (5,2;5,2) のとき、
X = {i[1]+i[2]*25|i[1]=0,1,…,4 ; i[2]=0,1} 、Y = {j[1]*5+j[2]*50|j[1]=0,1,…,4 ; j[2]=0,1}
とすれば、{ x+y | x∈X, y∈Y } = {0,…,n^2-1}
[B] 2≦m≦2
(B1) m=2 のとき、(s[1],s[2];t[1]) = (2,5;10)または(5,2;10) となる。
{B1-1} (s[1],s[2];t[1]) = (2,5;10) のとき、
X = {i[1]+i[2]*20|i[1]=0,1 ; i[2]=0,1,…,4} 、Y = {j[1]*2|j[1]=0,1,…,9}
とすれば、{ x+y | x∈X, y∈Y } = {0,…,n^2-1}
{B1-2} (s[1],s[2];t[1]) = (5,2;10) のとき、
X = {i[1]+i[2]*50|i[1]=0,1,…,4 ; i[2]=0,1} 、Y = {j[1]*5|j[1]=0,1,…,9}
とすれば、{ x+y | x∈X, y∈Y } = {0,…,n^2-1}
＃ らすかるさんが紹介された「A273013」に書いてあることなんですけど、先ほどの列挙に
対応させて書くと、次のようになると思います。
ｎを1より大きなｎの約数ｍ個の積に分解する方法の数を f(n,m) とおきます。(1≦m≦M)
[A]のとき、 Σ[m=1,M]f(n,m)^2 通り 、[B]のとき、Σ[m=2,M]f(n,m-1)f(n,m) 通り
となる。
1組の個数が素数(2,3,5,7,11,…)の時、1通り
n=p とすると、M=1で、f(p,1)=1 [p]
[A]のとき、1^2=1通り 、[B]のとき 0通り で、1+0=1通り
異なる2つの素因数の積(6,10,14,15,21,…)の時、7通り
n=pq とすると、M=2で、f(pq,1)=1 [pq] 、f(pq,2)=2 [p*q, q*p]
[A]のとき、1^2+2^2=5通り 、[B]のとき、1*2=2通り で、5+2=7通り
1つの素因数の2乗(4,9,25,49,…)の時、3通り
n=p^2 とすると、M=2で、f(p^2,1)=1 [pp] 、f(p^2,2)=1 [p*p]
[A]のとき、1^2+1^2=2通り 、[B]のとき、1*1=1通り で、2+1=3通り
1つの素因数の3乗(8,27,125,343,…)の時、10通り
n=p^3 とすると、M=3で、f(p^3,1)=1 [ppp] 、f(p^3,2)=2 [p*pp, pp*p] 、f(p^3,3)=1 [p*p*p]
[A]のとき、1^2+2^2+1^2=6通り 、[B]のとき、1*2+2*1=4通り で、6+4=10通り
p×q^2形(12,18,20,28,…)の時、42通り
n=pq^2 とすると、M=3で、f(pq^2,1)=1 [pqq] 、f(pq^2,2)=4 [p*qq, q*pq, pq*q, qq*p]
f(pq^2,3)=3 [p*q*q, q*p*q, q*q*p]
[A]のとき、1^2+4^2+3^2=26通り 、[B]のとき、1*4+4*3=16通り で、26+16=42通り
異なる3つの素因数の積の時、n=pqr とすると、M=3で、
f(pqr,1)=1 [pqr]
f(pqr,2)=6 [p*qr, q*pr, r*pq, pq*r, pr*q, qr*p]
f(pqr,3)=6 [p*q*r, p*r*q, q*p*r, q*r*p, r*p*q, r*q*p]
[A]のとき、1^2+6^2+6^2=73通り 、[B]のとき、1*6+6*6=42通り で、73+42=115通り
DD++さんからのコメントです。（平成２８年１１月７日付け）
私もりらひいさんと同じところに行き着き、そしてこれら２種類以外に存在しない証明ができ
ずに行き詰まりました。当たり前のように見えるものほど、いざ証明しようとすると難しい……。
りらひいさんからのコメントです。（平成２８年１１月９日付け）
３つの集合に拡張してみた。
{ x+y+z | x∈X, y∈Y, z∈Z } = {0,…,215} をみたす0以上の整数を要素とする要素数6の集
合X、Y、Zを求めよ。
２つの集合の場合を自然に拡張して、解71通りを得ました。
（X,Y,Zの入れ替え含むならこの6倍。）
これで全部であるという証明はできていません。「A131514」が正しいのであれば、これで全
部っぽいですが．．．。
らすかるさんからのコメントです。（平成２８年１１月１０日付け）
以前のプログラムを改造して全通り探索をしたところ、確かに71通りになり、一覧の解もす
べて一致しました。
りらひいさんからのコメントです。（平成２８年１１月１０日付け）
全パターン検索ありがとうございます。集合の数を増やす方向で拡張していくとき、私が行
った導出方法によるパターン数を順番に求めていったところ、各集合の要素数が異なる素
数の積になるときのパターン数は、「A002119」になるらしいと分かりました。
ＧＡＩさんからのコメントです。（平成２８年１１月１０日付け）
２つの集合の場合を自然に拡張して・・・
まさかこれを手作業？もし、この作業をやらせるとしたら、どんなコードになるか教えて下さ
い。
りらひいさんからのコメントです。（平成２８年１１月１１日付け）
半分は手作業で、もう半分はエクセル関数を使って出しています。考察とパターン構成を
同じエクセルファイルを使って行ったのでごちゃごちゃしてます。
6の分解の仕方とその並べ方は手作業で、71パターン打ち込んでいます。そこから各パタ
ーンの具体的な集合要素を出すのは、エクセル関数を作ってオートフィル使って一気に。
各集合の中の順番が昇順ではなかったため、数値コピーをした後に並べ替えた感じです
ね。csvで出力してメモ帳で開いて見栄えを良くしてコピペしました。
途中でプログラム組もうかとも思ったけど、関数を使った方が早そうだということでこうなり
ました。作ったものが本当に条件を満たしているかどうかだけ、最後にエクセルVBAで簡単
なコードを組んで確認しています。手探りでトライアンドエラーしながら進めたので、きれいに
なっていません。
DD++さんからのコメントです。（平成２８年１１月１１日付け）
手作業で頑張る場合、こういう手順になると思います。
さすがに、6個3組0から215まで（71解）を例示に使うのは大変なので、元の6個2組0から
35まで（7解）で例示します。（りらひいさんと同じく、「0以上の整数」に変更しています）
まず、x^36-1 を因数分解します。この時点でかなり根性を必要としますが、頑張ります。
x^36-1
= (x^18-1) (x^18+1)
= (x^9-1) (x^9+1) (x^18+1)
= (x^3-1) (x^6+x^3+1) (x^3+1) (x^6-x^3+1) (x^6+1) (x^12-x^6+1)
= (x-1) (x^2+x+1) (x^6+x^3+1) (x+1) (x^2-x+1) (x^6-x^3+1) (x^2+1) (x^4-x^2+1) (x^12-x^6+1)
これを x-1 で割ると、
x^35+x^34+x^33+……+x+1
= (x^2+x+1) (x^6+x^3+1) (x+1) (x^2-x+1) (x^6-x^3+1) (x^2+1) (x^4-x^2+1) (x^12-x^6+1)
これを見ながら、右辺の8つを2グループに分けます。
まず、x=1 のときに2になる (x+1) と (x^2+1) は別グループにします。また、x=1 のときに3
になる (x^2+x+1) と (x^6+x^3+1) は別グループにします。残りの4つは x=1 のときに1にな
るので、こうすることで、各グループの積が x=1 のときに6になることが保証されます。
(x^2-x+1) はマイナスを残さないために、(x+1) か (x^2+x+1) と同グループにする必要が
あります。同じく (x^4-x^2+1) は (x^2+1) か (x^2+x+1)×(x^2-x+1) と同グループにする必
要があり、(x^6-x^3+1) は (x+1)×(x^2-x+1) か (x^6+x^3+1) と同グループにする必要が
あり、(x^12-x^6+1) は (x^2+1)×(x^4-x^2+1) か (x^6+x^3+1)×(x^6-x^3+1) と同グループ
にする必要があります。
[A] (x+1) (x^2+x+1) と (x^2+1) (x^6+x^3+1) で組み合わせたとき、(x^2-x+1) は必然的に
前者、(x^4-x^2+1) は任意、(x^6-x^3+1) も任意。(x^12-x^6+1) は必然的に後者ですが、
(x^4-x^2+1) と (x^6-x^3+1) の少なくともどちらかが後者グループにいることが必要です。
ということで、以下の3解が見つかります。
(x+1) (x^2+x+1) (x^2-x+1) = x^5+x^4+x^3+x^2+x+1
(x^2+1) (x^6+x^3+1) (x^4-x^2+1) (x^6-x^3+1) (x^12-x^6+1) = x^30+x^24+x^18+x^12+x^6+1
より {0,1,2,3,4,5},{0,6,12,18,24,30}
(x+1) (x^2+x+1) (x^2-x+1) (x^4-x^2+1) = x^9+x^8+x^5+x^4+x+1
(x^2+1) (x^6+x^3+1) (x^6-x^3+1) (x^12-x^6+1) = x^26+x^24+x^14+x^12+x^2+1
より {0,1,4,5,8,9},{0,2,12,14,24,26}
(x+1) (x^2+x+1) (x^2-x+1) (x^6-x^3+1) = x^11+x^10+x^9+x^2+x+1
(x^2+1) (x^6+x^3+1) (x^4-x^2+1) (x^12-x^6+1) = x^30+x^24+x^18+x^12+x^6+1
より {0,1,2,9,10,11},{0,3,6,18,21,24}
[B] (x+1) (x^6+x^3+1) と (x^2+1) (x^2+x+1) で組み合わせたとき、(x^2-x+1) は任意、
(x^4-x^2+1) は必然的に後者、(x^6-x^3+1) は必然的に前者、(x^12-x^6+1) は任意。
ということで、同様に展開の計算をして残りの4解が見つかります。
以上で、全7解を、それが全解である保証とともに得られます。
（りらひいさんの方法だと解のリストアップまでは速いですが、全解である保証は困難にな
ると思います）
他の個数でも n個m組の場合には x^(n^m)-1 の因数分解をすればなんとかなると思い
ますが、一般化の際には以下が困難として立ちはだかります。
(1) nの素因数が多い場合の因数分解の結果を一般化するのが大変
(2) マイナスが消える法則性はどのようになっているのか見通しが立ちにくい
(3) 因数の係数に2以上が出てきた場合の処理はどうなるのかが謎
(3) の具体例として、105個ずつ2組の数で0から11024まで作る場合があります。x^11025-1
の因数分解を考えることになりますが、この因数27個（(x-1)を除けば26個）の中に-2という
係数が登場するものが6つ含まれます。
これらはどのように組み合わせて消せばいいのか私には全く予測できません。おそらく全
解数は pqr 型の115個だとは思いますが。
ＧＡＩ さんからのコメントです。（平成２８年１１月１１日付け）
DD++さんの母関数を利用する技を見習って、比較的因数を含む12(=2^2*3)に対するもので
W=(1+t+t^2+t^3+････+t^11)^2=((t^12-1)/(t-1))^2
ここで、 t^12-1=(t-1)(t+1)(t^2-t+1)(t^2+1)(t^2+t+1)(t^4-t^2+1) から、
W=(t+1)^2(t^2-t+1)^2(t^2+1)^2(t^2+t+1)^2(t^4-t^2+1)^2
この因数を２グループ（F,G)に分けて、それぞれの係数の和が12になるものの組合せを探る。
A=t+1 、B=t^2-t+1 、C=t^2+1 、D=t^2+t+1 、E=t^4-t^2+1 とおいて、
[1] F=A*C*D=t^5+2t^4+3t^3+3t^2+2t+1
G=A*B^2*C*D*E=t^17+t^14+t^13+t^11+t^10+t^9+t^8+t^7+t^6+t^4+t^3+1
それぞれにtをかけて(1以上の数に読み替えるため）tの指数を読みとり、
S1=(1,2,2,3,3,3,4,4,4,5,5,6)とS2=(1,4,5,7,8,9,10,11,12,14,15,18)
すると、この２グループでのx+y(x∈S1,y∈S2)の頻度分布は、
和； 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
頻度；1 2 3 4 5 6 7 8 9 10 11 12 11 10 9 8 7 6 5 4 3 2 1
と通常に1,2,3,･･･,12のナンバリングしたものの２つの和に同質（確率分布が同じ）となれる。
以下
[2] F=A^2*B*D 、G=B*C~2*D*E^2 より、
S1=(1,2,2,3,3,4,4,5,5,6,6,7)とS2=(1,3,5,7,7,9,9,11,11,13,15,17)
[3] F=A*C*D*E 、G=A*B^2*C*D*E より、
S1=(1,2,2,3,3,4,7,8,8,9,9,10)とS2=(1,3,4,5,6,7,8,9,10,11,12,14)
[4] F=A^2*B*D*E 、G=B*C^2*D*E
S1=(1,2,2,3,5,6,6,7,9,10,10,11),S2=(1,3,3,5,5,7,7,9,9,11,11,13)
[5] F=A*B*C*D 、G=A*B*C*D*E^2
S1=(1,2,3,3,4,4,5,5,6,6,7,8),S2=(1,2,5,6,7,8,9,10,11,12,15,16}
[6] F=C^2*D*E 、G=A^2*B~2*D*E
S1=(1,2,3,3,4,5,7,8,9,9,10,11),S2=(1,2,4,5,5,6,8,9,9,10,12,13)
[7] F=A^2*B^2*D 、G=B^2*D*E^2
S1=(1,2,3,4,4,5,5,6,6,7,8,9),S2=(1,2,3,7,7,8,8,9,9,13,14,15)
と意外にたくさんのパターンが見つけられた。（これ以外を見落としているかも・・・）
でも、母関数的に考える方法はとても有効ですね。
