結城浩
2003年12月30日
アフタヌーン・ティールームでパスタ・ランチを食べ終えた私は、 ロイヤルミルクティを飲みながら、ぼんやりと窓の外を眺めていた。 年末のはずなのに、町は意外に閑散としている。 ふと、ドアのほうに目をやると、ピンクのセーターを来た女の子が一人 入ってくる。 女の子は店内を見回して、私の方を向くとにこっと微笑んでこちらに近づいてきた。 彼女は、不思議そうな顔をしている私の向かいの席にするっと腰をおろすと、 大きな布のバッグをテーブルの上に置いて、ふう、と一息つく。
びっくりした私が「ええと…どちらさまですか？」と尋ねると、 彼女は「わかりませんか？」と答える。 私は彼女の顔をじっと見る。 …高校生、いや中学生かな？ ふかふかした、やわらかいピンク色のとっくりセーター。 髪はストレートのロングで、プラスチックの髪留めが1つ。これもピンク。 整った顔立ちをしていて、微笑んでいる…だめだ、思い出せない。いったい誰だろう。
彼女は、困っている私をにこにこしながら見ている。 やがて、彼女は口を開く。
「それじゃ、問題を解く、というのはいかがでしょう？ そうしたら私が誰か、思い出すかもしれませんよ。」
「問題？」
「既約分数を考えることにしましょう。既約分数はご存知ですか？」
「きやくぶんすう？ え、ええ。分子と分母で共通の因数がない分数？」
「まあよいでしょう。いま既約分数 p/q (q分のp)を考えます。pは0以上の整数(0, 1, 2, 3, ...)、qは1以上の整数(1, 2, 3, ...)。pとqには1より大きい共通の因数がない。すなわち…」
「すなわち？」
「すなわち、pとqの最大公約数は1である。gcd(p,q)=1.よろしいですか？」
「…はい。」
気おされてしまった私はおとなしく答える。 アフタヌーン・ティールームの店員さんがメニューを持って注文を採りに来たが、 彼女は「すぐに出ますので」と答える。
「さらに」と彼女は私に向き直って続ける。 「p/q の値は0以上1以下としましょう。いくつか例を示していただけますか？」
「p/qの例？ たとえば1/2とか、2/3。」
「そうですね。0/1はいかがでしょう。」
「0と1の最大公約数は…1と考えてもよいね。0はすべての整数で「割り切れる」と考えられるから、すべての整数が0の約数。だから0と1の最大公約数は1。だから0/1も既約分数。」
「はい、そうですね。0/1も既約分数としましょう。でも、0がすべての整数で「割り切れる」というのは誤りですね。」
「ん？」どんなnを持ってきても、「0割るn」は「0余り0」だから、割り切れるんじゃないかな？
「だって、0は0では割れませんもの。」彼女はにっこりする。
…確かにその通りだ。 「0/1は既約分数。そういう意味では1/1も既約分数。すべての正整数nについて1/nは既約分数。ところで、これが問題？」
「いいえ、ここからが問題です。」 彼女は口元を一瞬だけきゅっと上げて、問題を出す。
問題：正の整数Nが与えられているとき、 以下の条件を満たす既約分数p/qを「すべて」求めるアルゴリズムを示してください。 条件は：
私が机上のナプキンに条件をあわててメモしていると、彼女は続けて例を示した。
「たとえば、Nが4だとしましょう。その場合、求める既約分数は分母が4以下の、次の7個です。
0/1, 1/1, 1/2, 1/3, 2/3, 1/4, 3/4.
でも、2/4は当てはまりません。gcd(2,4)=2だからです。」
私がナプキンをにらみながら分母に関するループを考え、 ブルート・フォースなアルゴリズムを組み立て始めていると、 彼女は席を立ち、重そうなバッグを持ち上げながらこう言った。
「ゆっくり考えてくださいね。またそのうちにお会いしましょう。 日記の読者さんへのクイズになさったら、きっとどなたかエレガントな解法をご存知でしょう。 見つからなかったら、時計を作る方にお尋ねになるとよいですよ。 では、よいお年を」
彼女が大きなバッグを持ち替えたとき、 こんなししゅうが見えた。
Where is the truth?
（フィクションです、念のため）