+inf.0

2014年9月5日金曜日

Project Euler - Problem 457

問題はこちら。

いきなり $\mbox{mod }p^2$ で考えるのはしんどいので、 $\mbox{mod }p$ から考える。

f (n) = n 2 - 3 n - 1 \equiv 0 (mod p)

$f(n) = n^2 - 3n - 1 \equiv 0 \mbox{ (mod }p)$

このような $n, p$ の組が見つかった時、以下も成立することが分かる。

f (n \pm p k) = (n \pm p k) 2 - 3 \cdot (n \pm p k) - 1 \equiv n 2 - 3 n - 1 \equiv 0 (mod p)

$f(n \pm pk) = (n \pm pk)^2 - 3 \cdot (n \pm pk) - 1 \\ \equiv n^2 - 3n - 1 \equiv 0 \mbox{ (mod }p)$

以上より、 $n^2 - 3n - 1 \equiv 0 \mbox{ (mod }p)$ なる $n, p$ の組があるならば、 $1 \leq p < n$ も成立する。次に $\mbox{mod }p^2$ について考える。

f (m) = m 2 - 3 m - 1 \equiv 0 (mod p 2) f (m = n + p k) = (n + p k) 2 - 3 \cdot (n + p k) - 1 \equiv n 2 + 2 n p k + p 2 k 2 - 3 n - 3 p k - 1 \equiv 2 n p k - 3 p k + n 2 - 3 n - 1 \equiv (2 n - 3) p k + (n 2 - 3 n - 1) \equiv 0 (mod p 2)

$f(m) = m^2 - 3m - 1 \equiv 0 \mbox{ (mod }p^2) \\ f(m=n+pk) = (n+pk)^2 - 3 \cdot (n+pk) - 1 \\ \equiv n^2 + 2npk + p^2k^2 - 3n - 3pk - 1 \\ \equiv 2npk - 3pk + n^2 - 3n - 1 \\ \equiv (2n - 3)pk + (n^2 - 3n - 1) \equiv 0 \mbox{ (mod } p^2) \\$

この時、 $n^2 - 3n - 1 \equiv 0 \mbox{ (mod } p)$ であるので、両辺を p で割り

(2 n - 3) p k / p + (n 2 - 3 - 1) / p \equiv 0 (mod p 2 / p) (2 n - 3) k + (n 2 - 3 n - 1) / p \equiv 0 (mod p)

$(2n - 3)pk/p + (n^2 - 3 - 1)/p \equiv 0 \mbox{ (mod } p^2/p)\\ (2n - 3)k + (n^2 - 3n - 1)/p \equiv 0 \mbox{ (mod } p)$

この 1 次合同式を解くことで $k$ を得られ、 $f(m = n+pk) \equiv 0 \mbox{ (mod }p^2)$ なる $m$ も得られる。そして同様に $p^3, p^4, ...$ の場合も計算可能なことより、以上のこれらの性質から、篩を使うことで $N$ までの区間に存在する素数を、高速に列挙可能でもあることが分かる。

なお、 $f(n) = n^2 - 3n - 1 \equiv 0 \mbox{ (mod } p)$ なる n を 1 つ求められているならば

f (p - n + 3) = (p - n + 3) 2 - 3 \cdot (p - n + 3) - 1 \equiv n 2 - 2 n p - 3 n + p 2 + 3 p - 1 \equiv n 2 - 3 n - 1 \equiv 0 (mod p)

$f(p-n+3) = (p-n+3)^2 - 3 \cdot (p-n+3) - 1 \\ \equiv n^2-2 n p-3 n+p^2+3 p-1 \\ \equiv n^2 - 3n - 1 \equiv 0 \mbox{ (mod } p)$

より、もうひとつの p で割り切れる系列を見つけ出すことができる。ただし

f (n = 8) = 39 \equiv 0 (mod p = 13) p - n + 3 = 13 - 8 + 3 = 8

$f(n=8) = 39 \equiv 0 \mbox{ (mod } p=13) \\ p-n+3 = 13-8+3 = 8$

のようなパターンもあるため、少しの注意が必要となる。また、 $\mbox {mod } p=13$ については

(2 \cdot 8 - 3) k + 39 / 13 \equiv 0 (mod 13) 13 k + 3 \equiv 0 (mod 13) 3 \neq 0

$(2 \cdot 8 - 3)k + 39/13 \equiv 0 \mbox{ (mod } 13) \\ 13k + 3 \equiv 0 \mbox{ (mod } 13) \\ 3 \neq 0$

と、 $k$ が消えてしまうことから、 $f(13k+8) \equiv 0 \mbox{ (mod } 13^2)$ なる $k$ は存在しないことも分かる。

自分の中では普通に解いたつもりだけど、他の人の解き方はわりと違うようだった。なんでや。

2013年10月24日木曜日

互いに素である a,b の組を効率良く列挙しよう

互いに素である 2 つの自然数を効率的に列挙する方法について、2 通りのアルゴリズムを紹介する。

Stern-Brocot tree を使い列挙する

この木がどんなものであるかは、Wikipedia を読むのが一番手っ取り早い。とはいっても、英語版にはそのもののページがあるが、日本語版には無いようだ。しかし、ファレイ数列のページでこの木について触れられているので、そこのリンクを貼っておく。

ユークリッドの互除法を逆算する要領で列挙する

最大公約数を求める際にユークリッドの互除法が使われるが、それを逆の手順で計算する事によっても、互いに素である組を網羅する事が出来る。つまり、

g c d (a, b) = {a g c d (b, a mod b) (b = 0) (o t h e r w i s e) g c d (b, a mod b) = g c d (b, a + b n)

${\rm gcd}(a,\: b) = \begin {cases} a & (b = 0) \\ {\rm gcd}(b,\: a \bmod b) & (otherwise) \end {cases} \\ {\rm gcd}(b,\: a \bmod b) = {\rm gcd}(b,\: a+bn)$

である事を利用し、 ${\rm gcd}(1,\: 1) = 1$ から始めて逆算を行えば、全ての互いに素である a,b の組を列挙可能となる。

C++ と Scheme による実装

まずは C++ で書いたものから。

そして Scheme で書いたもの。

2 つのアルゴリズムの違い

まず 1 つ目に、再帰関数に渡さなければならない引数の数が違う。引数の数が違えば、再帰呼び出しにおけるスタックの消費量が違い、また push/pop の要不要によって処理速度も変わってくる。その為、Stern-Brocot tree によるものは、ユークリッドの互除法を逆の手順にしたものよりも、メモリを食い速度も若干遅くなる。

2 つ目に、特定の区間にある既約分数を列挙出来るかどうかといった差異がある。Stern-Brocot tree を用いたものでは、enum_coprimes_with_stern_brocot_tree(N, 0, 1, 1, 1) として、 $[\frac01,\: \frac11]$ に存在する既約分数を列挙可能だが、ユークリッドの互除法を逆の手順にしたものでは、簡単には実現出来ない。因みに、Stern-Brocot tree をもちいたアルゴリズムで $[\frac13,\: \frac12]$ に存在する既約分数を列挙するには、enum_coprimes_with_stern_brocot_tree(N, 1, 3, 1, 2) とすれば良い。これは他の区間でも同様である。

ちょっとした応用

これまで、互いに素となる a,b の組、つまり ${\rm gcd} (a,b) = 1$ となる a,b の組を列挙をする方法を書いてきたが、少し応用すれば ${\rm gcd}(a,b) = n$ となる a,b の組を列挙する事も出来る。これは単純に、互いに素となる a,b の組を列挙し an,bn としても計算しても良いが、以下のようにする事でも可能だ。

こうしてやれば、互いに素である a,b の組を生成する都度 n を掛けるより、若干効率が良い。