PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 169 / ある数を2のべき乗の和で表せる方法の数の探査

整数nを2のべき乗の和で表すことを考える。ただし各数は高々2回しか使ってはいけないものとする。この表し方の数をf(n)とする。f(0)=1と定義する。例として n=10 を考える。

  • 1+1+8
  • 1+1+4+4
  • 1+1+2+2+4
  • 2+4+4
  • 2+8

5通りの異なる表し方があるので f(10)=5 である。
f(10^25)を求めよ。

Problem 169 - Project Euler


漸化式の問題です。f(n)=f(n-2^m)+... のような式を立てたくなりますが,実はこれは筋悪。「1を何個使うか」がポイントです。奇数は1個使い,偶数は0個か2個使います。

n=2m+1 のとき,1を1個使った残りは 2m。これを表すのに1は使わないので表し方の個数は 2m/2=m と同じです。

f(2m+1)=f(m)

偶数のときも同様です。n=2m+2 から1を0個引くと 2m+2,2個引くと 2m。これらを表すのに1は使わないので

f(2m+2)=f(m+1)+f(m)

以上を f(n)=... の形に直して Mathematica に渡します。