■2乗和が等しい数列とスー・モース数列(その16)

 1から8までのすべての数字を含む排他的数列

  {an}={1,4,5,8}

  {bn}={2,3,6,7}

では

  2^0+3^0+5^0+8^0=1^0+4^0+6^0+7^0=4

  2^1+3^1+5^1+8^1=1^1+4^1+6^1+7^1=18

  2^2+3^2+5^2+8^2=1^2+4^2+6^2+7^2=102

2乗和まで等しい数列となっている.

 1から16までのすべての数字を含む排他的数列

  {an}={1,4,6,7,10,11,13,16}

  {bn}={2,3,5,8,9,12,14,15}

では

  1+4+6+7+10+11+13+16=2+3+5+8+9+12+14+15=68

  1^2+4^2+6^2+7^2+10^2+11^2+13^2+16^2=2^2+3^2+5^2+8^2+9^2+12^2+14^2+15^2=748

  1^3+4^3+6^3+7^3+10^3+11^3+13^3+16^3=2^3+3^3+5^3+8^3+9^3+12^3+14^3+15^3=9248

3乗和まで等しい数列となっている.

 これらの具体的なアルゴリズムは,スー・モース数列と関係している.

===================================

【1】スー・モース数列

 スー・モース数列では,nを2進展開したとき,現れる1の個数が奇数の場合tn=1,現れる1の個数が偶数の場合tn=0と定める.たとえば,n=23では

  23=(10111)2→t23=0

 したがって,スー・モース数列{tn}は

  0,1,1,0,1,0,0,1,

  1,0,0,1,0,1,1,0,

  1,0,0,1,0,1,1,0,

  0,1,1,0,1,0,0,1,・・・

 ここには明確な回文構造が見られます.すなわち,先頭から2^n項があるとき,ビット単位に1と0を入れ替え,数列の後ろに連結します.0/1が連続して3つ現れることはありません.

===================================

[1]スー・モース数列は

  t2n=tn

>  t2n+1=1−tn

によって再帰的に定義することもできます.

[2]置換則: 0→01,1→10

 0から始めると

  →01

  →0110

  →01101001

  →0110100110010110

  →01101001100101101001011001101001

 このような置換則はフラクタル幾何学でしばしば用いられますから,ご存知の方も多いと思います.

[3]

>  Π(1−x^2^k)=Σ(−1)^tnx^n

>を満たす一意な数列としても定義することができます.

 冒頭の例では

  Σ(−1)^tnx^n=0

となるように,整数を2つの集合に分け,それぞれのベキ乗の和が等しくなる等式を探していることになります.

===================================