反復アルゴリズムにおいて，各ステップごとに最大化を試みるものを欲張り算法（greedy algorithm）と呼びます．欲張り算法はあるときは最も賢明な方法ですが，ときとして破綻します．

　２３＝４^2＋２^2＋１^2＋１^2＋１^2　　（破綻）

　２３＝３^2＋３^2＋２^2＋１^2　　（破綻せず）

　２３＝２^3＋２^3＋１^3＋１^3＋１^3＋１^3＋１^3＋１^3＋１^3　　（破綻せず）

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【１】ウェアリングの問題とヒルベルトの定理

　１７７０年，ウェアリングは４平方和定理を拡張して，「任意の整数はたかだか９個の３乗数の和として，あるいは１９個の４乗数の和として表される」

ことを証明抜きで主張しました（９三乗数定理，１９四乗数定理）．これが，有名なウェアリングの問題です．

　ｇ（２）＝４はラグランジュにより，ｇ（３）＝９はヴィーフェリッヒによって証明されました（１９０９年）．

　ウェアリングの問題は，２次形式ではなく高次形式を扱っていて，多くの数学的思考を刺激しました．そして，１９０９年，ヒルベルトによって「どの数もｇ個のｋ乗数の和で表される」ことが肯定的に証明されています．

　　ｎ＝ｘ1^k＋・・・＋ｘg^k

　ヒルベルトはｇ（ｋ）の値がｋのみによって表されることを証明したのですが，それはｇ（ｋ）の存在のみを証明したのであって具体的な値を決める方法を示したものではありませんでした．

　１８５９年，リューヴィルはｇ（４）≦５３を示しました．ｇ（４）＝１９ですからこの結果は実際とはかなり隔たりがあるのですが，ｇ（４）の限界を与える方法を初めて示したことになります．そのあたりからいろいろな研究がなされることになりました．そして，１９四乗数定理「すべての正の整数は１９個の４乗数の和で表される」は１９８６年に証明されています．つまり，ウェアリングの問題（１８世紀）も２００年以上かかって解決されたことになります．

　なお，ｇ乗数は平方数よりもずっとまばらにしか分布しませんから，以下，３７個の５乗数の和，７３個の６乗数の和，・・・と続きます．実は，ガウス記号を用いて

　　ｇ（ｋ）＝２^k＋［（３／２）^k］−２

の式が正しいだろうと予想されています．１≦ｋ≦１０では

　　ｋ　　１　　２　　３　　４　　５　　６　　７　　８　　９　　10

　　下界　１　　４　　９　　19　　37　　73 143 279 548 1079

となり，ここに示した値はすべてこの式を満たし，かなりの範囲のところまで正しいことが確認されます．

　　ｇ（ｋ）≧２^k＋［（３／２）^k］−２

の不等式を証明したのはオイラーの息子，ヨハン・アルブレヒト・オイラーです（１７７２年）．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝