A161638 The largest number of steps in Euclid's algorithm applied to A157807(n) and A157813(n).

1, 1, 2, 2, 1, 1, 2, 3, 2, 2, 1, 1, 2, 2, 3, 3, 2, 2, 4, 3, 1, 1, 2, 2, 3, 3, 2, 2, 3, 2, 1, 1, 2, 3, 3, 2, 3, 4, 4, 3, 2, 2, 4, 3, 1, 1, 2, 2, 2, 4, 2, 3, 5, 3, 3, 3, 2, 2, 4, 4, 3, 3, 1, 1, 2, 3, 2, 3, 4, 3, 2, 2, 3, 3, 4, 3, 2, 2, 1, 1, 2, 3, 2, 3, 3, 3, 2

Offset: 1

Author

Yalcin Aktar, Jun 15 2009

Keywords

• nonn
• easy

Comments

The sequence of fractions is ordered as follows: 1/1, 2/1, 1/2, 1/3, 3/1, 4/1, 3/2, 2/3, 1/4, 1/5, 5/1,...

Examples

			a(8) = 3 because the algorithm applied to the pair (2,3) needs the steps 2 = 3 x 0 + 2 then 3 = 2 x 1 + 1 and 2 = 1 x 2 + 0.
		

Links

• Anonymous, Euclidean algorithm, Springer's Encyclopedia of Maths.
• Eric W. Weisstein, Euclidean algorithm, MathWorld.
• Wikipedia, Euclid's algorithm

Programs

Python

from math import gcd
def euclid_steps(a, b):
  if b == 0:
    return 0
  else:
    return 1 + euclid_steps(b, a % b)
for s in range(2, 100, 2):
  for i in range(1, s):
    if gcd(i, s - i) != 1: continue
    print(euclid_steps(i, s - i))
  for i in range(s, 0, -1):
    if gcd(i, s + 1 - i) != 1: continue
    print(euclid_steps(i, s + 1 - i))
# Hiroaki Yamanouchi, Oct 06 2014

Extensions

Partially edited by R. J. Mathar, Sep 23 2009

a(1) prepended and a(12)-a(87) added by Hiroaki Yamanouchi, Oct 06 2014