私はウィキペディアに記載されている三元ツリーアルゴリズムに従って、すべての互いに素のペアを生成することができますすぐに https://en.wikipedia.org/wiki/Coprime_integers定数空間を使用してすべてのペアを繰り返しますか？
を：
Start with two coprime branches: (2,1), (3,1), then iterate:
Branch 1: (2m-n,m)
Branch 2: (2m+n,m)
Branch 3: (m+2n,n)
使用スペースが生成された各ペアの3倍に成長するが（印刷されているとか、そうでなければ記憶されていないとか）。ここで
はHaskellでは解決策になるかもしれません： Generating sorted list of all possible coprimes
しかし、私は遅延評価や無限リストを持っていないのpythonで何か、を探していました。
これは対数空間を使用して、多分それは良いことだが十分な？それは線形時間です（最初のkペアを生成するためにO（k）時間を使います）。
def coprimes():
yield (2, 1)
yield (3, 1)
for m, n in coprimes():
yield (2*m - n, m)
yield (2*m + n, m)
yield (m + 2*n, n)
あなたはデイビット・エップスタインにより、これらの記事では、このような自己再帰的なジェネレータについての詳細を読むことができます：最初の20を示す
デモペア：
>>> pairs = coprimes()
>>> for _ in range(20):
print(next(pairs))
(2, 1)
(3, 1)
(3, 2)
(5, 2)
(4, 1)
(5, 3)
(7, 3)
(5, 1)
(4, 3)
(8, 3)
(7, 2)
(8, 5)
(12, 5)
(9, 2)
(7, 4)
(9, 4)
(6, 1)
(7, 5)
(13, 5)
(11, 3)
Pythonのプロセスのメモリ使用量は、任意のPythonのプロセスは、少なくとも私を取る9.5メガバイトのベースラインに滞在しながら、約4分の私のPCを取る億ペアを示すデモ。
>>> from itertools import islice
>>> next(islice(coprimes(), 10**9-1, None))
(175577, 63087)
これはもっとエレガントで、受け入れられるべきです！有益なリンクもあります。 – IVlad
ありがとう、これはエレガントなソリューションであり、イテレータでこれを実行できるかどうかはわかりませんでした。 – user318904
ほんの数を取得するには受け入れHaskellのソリューションのPythonのバージョン
def find_coprimes():
l = 1
while True:
i = 2
while i < l-i:
if gcd(i, l-i) == 1:
yield i, l-i
i += 1
l += 1
：
iterator = find_coprimes()
for i in range(10):
print(next(iterator))
出力：
(2, 3)
(2, 5)
(3, 4)
(3, 5)
(2, 7)
(4, 5)
(3, 7)
(2, 9)
(3, 8)
(4, 7)
ハスケルの問題と同じ制限が必要ですか？ '各ペアの最初の要素は2番目の要素より小さくなければなりません。並べ替えは、ペアの要素の合計で昇順に行う必要があります。 2つの合計が等しい場合は、ペアの最初の要素によって決まります。もしそうなら、それらのペアをあなたのアルゴリズムで交換したいと思います。 Pythonには無限のジェネレータがありますが、これはおそらくあなたの「無限リスト」に似ています。そして、あなたは「3倍の成長」の問題を避けようとしているのですか、単純なPythonコードがほしいのですか？ –
* "しかし、私は怠惰な評価や無限リストを持たないPythonで何かを探していました。" * Pythonには、潜在的に無限のシーケンスを生成するジェネレータ（遅延的に値を与える）と関数（特にitertoolsで）があります。 – Tagc
私はhaskellソリューションの制限を探していませんでした。そして、怠惰な/無限の用語にかかわらず、どんな慣用的なpython解決策も機能します。 – user318904