Hi all,
This is my attempt to generate all pairs of relatively prime pairs of
nonnegative integers (n, m) such that n + m <= N, using the Stern-Brocot tree.
def rp_bounded_sum(n, i = 0, p = (0, 1), q = (1, 1), S = set([(0, 1), (1, 1)])):
# Returns a set S with all relatively prime pairs (a, b)
# such that 0 <= a <= b and a + b <= n.
r = p[0] + q[0], p[1] + q[1]
if r[0] + r[1] <= n:
S.add(r)
rp_bounded_sum(n, 1, p, r, S)
rp_bounded_sum(n, 1, r, q, S)
if not i:
return S
Strangely, (to me) it seems that the function remembers the set S between
different calls:
>>> T=rp_bounded_sum(200)
>>> len(T)
6117
>>> T=rp_bounded_sum(100)
>>> len(T)
6117
Why?
I modified it to
def rp_bounded_sum(n, i = 0, p = (0, 1), q = (1, 1), S = set()):
# Returns a set S with all relatively prime pairs (a, b)
# such that 0 <= a <= b and a + b <= n.
if not i:
S = set([(0, 1), (1, 1)])
r = p[0] + q[0], p[1] + q[1]
if r[0] + r[1] <= n:
S.add(r)
rp_bounded_sum(n, 1, p, r, S)
rp_bounded_sum(n, 1, r, q, S)
if not i:
return S
Now it works fine but I don't understand why the first example fails. I'm not
very pleased with any of these two solutions so I would be grateful for any
suggestions of improvements. I use Python 2.7.2 under Windows 7 and I ran this
in Python shell in IDLE.
Cheers, Robert
_______________________________________________
Tutor maillist - [email protected]
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
