■スー・モース数列(その4)

整数を2つの集合に分け,それぞれのベキ乗の和が等しくなる等式を探す問題はプルーヘ・タリー・エスコット問題と呼ばれる.以下,その例を掲げる.

 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

ここでは問題を簡単にするため,1から2の累乗までのすべての数字を含む排他的数列を取り上げます.

この問題は2進法に基づくスー・モース数列を使うと解くことができます。平等に配分することができる数列というわけです。

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

【1】1から2の累乗までのすべての数字を含む排他的数列

たとえば,1から8までのすべての数字を含む排他的数列では,2乗和まで等しい.

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

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

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

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

たとえば、1から16までのすべての数字を含む排他的数列では,3乗和まで等しい.

 {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

 これから予想されることは,

[1]1から4までのすべての数字を含む排他的数列では,和が等しい.

[2]1から8までのすべての数字を含む排他的数列では,2乗和まで等しい.

[3]1から16までのすべての数字を含む排他的数列では,3乗和まで等しい.

[4]1から32までのすべての数字を含む排他的数列では,4乗和まで等しい.

[5]1から64までのすべての数字を含む排他的数列では,5乗和まで等しい.

[6]k乗和まで等しい2つの数列はそれぞれ同数の偶数,奇数を含む排他的な数列である.

ここで,整数を2つの集合に分け,それぞれのベキ乗の和が等しくなるようにする簡単なアルゴリズムが存在する.答えを先にいうと,スー・モース数列{0110100110010110}の{1}項だけ抽出すると

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

が得られる.

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