PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 207 / 整数分割方程式

いくつかの正整数 k は整数の分割式
 4^t = 2^t + k
が成り立つ。4^t, 2^t, k はすべて正の整数で, t は実数とする。

最初の 2 つの分割は 4^1 = 2^1 + 2 と 4^1.5849625... = 2^1.5849625... + 6 である。

t も整数である分割を完全と呼ぶ。m≥1をみたす m に対して P(m) を k≤m で分割が完全である割合と定義する。P(6) = 1/2 である。

次の表はいくつかの m に対する P(m) の例である.

  • P(5) = 1/1
  • P(10) = 1/2
  • P(15) = 2/3
  • P(20) = 1/2
  • P(25) = 1/2
  • P(30) = 2/5
  • P(180) = 1/4
  • P(185) = 3/13

P(m) < 1/12345 をみたす最小の m を求めよ。

Problem 207 - Project Euler


 4^t = 2^t + k で 2^t=x(>0) とおきます。x^2=x+k から

 x=2^t=\dfrac{1+\sqrt{4k+1}}{2}\qquad (1)

 \therefore t=\log_2 \dfrac{1+\sqrt{4k+1}}{2}\qquad (2)

(1)から 2^t が整数になる条件は 4k+1 が奇数の平方数であることです。
4k+1=(2a-1)^2とおくと

 k=a(a-1)\qquad (3)

(2)の t が整数になる条件は真数が 2^b の形の数であることです。

 k=2^b(2^b-1)\qquad (4)

1≦k≦m を整理すると

 (3):2\leqq a\leqq \left[\dfrac{1+\sqrt{4m+1}}{2}\right]

 (4):1\leqq b\leqq \left[\log_2\dfrac{1+\sqrt{4m+1}}{2}\right]

これらの個数の比が P(m) です。

P(m) は階段状の関数です。分母が増加するときに減少するので,m を(3)の形のものにしぼって調べました。

Floor 関数の中身の「/2」を「*0.5」に変えると速くなります。