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

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

Stern-Brocot tree を使い列挙する

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

• Stern–Brocot tree - Wikipedia, the free encyclopedia
• ファレイ数列 - Wikipedia # 隣接する分数と中間数

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

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

$${\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 を掛けるより、若干効率が良い。