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,3

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,...

Links

Table of n, a(n) for n=1..87.

Anonymous, Euclidean algorithm, Springer's Encyclopedia of Maths.

Eric W. Weisstein, Euclidean algorithm, MathWorld.

Wikipedia, Euclid's algorithm

Example

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.

Prog

(Python)
from fractions 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

Crossrefs

Sequence in context: A035463 A245424 A071784 * A066030 A025863 A346307

Adjacent sequences: A161635 A161636 A161637 * A161639 A161640 A161641

Keyword

nonn,easy

Author

Yalcin Aktar, Jun 15 2009

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

Status

approved