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

 簡単な置換則

  0→01,1→10

をもとに非周期的で再帰的に計算可能な数列を生成してみたい.

01

0110

01101001

0110100110010110

 これはスー・モース数列と呼ばれるもので,この数列に自己相似という性質がある.たとえば,この数列をひとつ置きに選んでも同じ数列が得られる.最初の2つの数字を選ぶ,次の2つの数字を捨てるという操作を繰り返しても同じ数列が得られる.

 すなわち,この数列は非周期的ではあるが,まったくランダムではなく,強固な短期的・長期的構造をもっていて,同じ数字が3つ以上続くことはない.

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

 この数列を生成する別の方法もある.各世代は前の世代にその補数を加えればよい.たとえば,0110の補数は1001であるから

0110+1001→01101001

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

 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乗和まで等しい数列となっている.

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

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