出題側として、難しい問題にするには、自分や仲間達の最新研究成果を使うが、問題を難しくするには、計算すべき数値の範囲(大きさ)や数値の量を大幅に増やす、といった安易なアプローチもある。

例えば、ごく簡単な足し算。数学では、a と b が与えられたら、その和は a+b で計算できるから、それ以上のことを深く考える必要はない。しかし、コンピュータの世界では、10進20桁未満の整数同士なら簡単だが、それ以上の大きさ、例えば、10進200桁同士の整数 a と b を足すにはひと工夫が必要。

近々、2進128桁までの整数はC言語でもふつうに扱えるようになると予想できるが、ある種の計算ではいままで以上に難しくなる。例えば、素数表の生成には、エラトステネスのふるいが効率がもっともよいのでよく利用されるが、128桁になると、あまり役に立たなくなるかもしれない。10秒では計算が終了しないから。

<オリジナル問題>(素数の分布)
 整数dが与えられたら、素数 a とそのつぎの素数 b との間隔 (=b-a) がd以上であるような、最小素数 a, bペアを計算せよ。ただし、a, bの大きさは10進35桁まで。
  例: d = 1 ⇒ a = 2, b = 3
     d = 2 ⇒ a = 3, b = 5
     d = 3 ⇒ a = 7, b = 11
     d = 4 ⇒ a = 7, b = 11
     d = 5 ⇒ a = 23, b = 29
     d = 6 ⇒ a = 23, b = 29
     d = 7 ⇒ a = 89, b = 97
</オリジナル問題>

ということで、プログラミング問題を解いたといっても、数学と違って、いろいろなレベルがある。つまり、計算量を探求するならば、多くの問題はいまだに解けられていない、と強引に主張しても間違いない。しかし、コンピュータの世界では、そのための言い訳というか、責任逃れの逃げ道が理論的にある程度用意されている。NP完全問題がその好例。誰もが解けないから、私ができなくても当然という、おかしな論理が、コンピュータの世界では堂々と成り立つ。

さて、違う問題をここで考えてみる。

問題 #10241
  三角数 (Triangular Number) とはつぎの数列で表される数のこと、つまり、 1, 3, 6, 10, 15, 21, 28 など、k( k+1)/2 を満たす数のことをいう。一方、平方数(四角数ともいう) (Square number) とは 1, 4, 9, 16, 25 のような数のことをいう。
 平方数を S とし、三角数を T とすると、つぎの条件2つを満たすすべての X を表示せよ。
    X = S
    X = (2n+1) * T  (ただし、n = 0, 1, …, 7)
なお、Xの範囲は 16×1034 まで。
 例: X = 1, 9, 36, 196, 225, 324, 900, 1225, 4225, 11025, 41616, 53361, 88209, 108900, …
</問題 #10241>

この問題の難しいところはやはり大きさの一点につきるだろう。10進36桁の整数はいまのプログラミング環境ではかなり厳しい。

<番外編>
 三角数でもあり、平方数でもある 平方三角数 Square Triangular Number というのがあって、そのN番目の値 Y(N) がつぎの漸化式で求まる。
   Y(N) = 34 * Y(N-1) – Y(N-2) + 2
   Y(1) = 1, Y(2) = 36
</番外編>

ここで考えている問題では、n=0の場合が Square Triangular Number にあたる。

問題解くための数式を整理してみる。T = t (t+1)/2、S = s2 とおくと、
   X = s2
   X = (2n+1) t (t+1)/2
なので、
   t (t+1) (2n+1) / 2 = s2
   (t2+t) (2n+1) / 2 = s2
   ((t+1/2)2-1/4) (2n+1) / 2 = s2
   ((2t+1)2-1) (2n+1) / 8 = s2
   (2t+1)2-1 = 8 s2/(2n+1)
最終的に、
   (2t+1)2 – (2s)2 2/(2n+1) = 1
が得られる。

Comments are closed.

Post Navigation