

A278744


Number of steps (modular reductions) in calculating the GCD of nth consecutive primes p(n) and p(n+1) by the Euclidean algorithm.


1



1, 2, 2, 3, 2, 2, 2, 3, 3, 2, 2, 2, 2, 3, 3, 3, 2, 2, 3, 2, 2, 3, 3, 2, 2, 2, 3, 2, 2, 2, 3, 3, 2, 3, 2, 2, 2, 3, 3, 3, 2, 2, 2, 2, 2, 5, 5, 3, 2, 2, 3, 2, 2, 3, 3, 3, 2, 2, 2, 2, 3, 3, 3, 2, 2, 5, 2, 4, 2, 2, 3, 3, 2, 2, 3, 3, 5, 2, 2, 3, 2, 2, 2, 2, 3, 3, 2, 2, 2, 3, 3, 3, 3, 4, 3, 3, 4, 2, 2, 2, 4, 3, 3, 2
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

If x(0)>x(1) are integers, the Euclidean algorithm (or Euclid's algorithm) calculates the GCD of x(0) and x(1) by the recursive formula x(i+2) = x(i) mod x(i+1). This recursion terminates when x(t) = 0 for some t. Then x(t1) is the GCD. Since the p(n) and p(n+1) are distinct primes, their GCD is 1, and there corresponding x(t1) = 1. a(n) is the number of modular reductions, i.e., t2.
Records are a(1) = 1 from gcd(2,3), a(2) = 2 from gcd(3,5), a(4) = 3 from gcd(7, 11), a(46) = 5 from gcd(199,211), a(221) = 6 from gcd(1381,1399), a(757) = 7 from gcd(5749,5779), a(5518) = 8 from gcd(54217,54251), a(65106) = 9 from gcd(815729, 815809), a(1293698) = 10 from gcd(20388583m 20388727), a(3997147) = 11 from gcd(67816457, 67816601).  Charles R Greathouse IV, Nov 28 2016


LINKS

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


EXAMPLE

For n=5, x(0) = p(6) = 13, x(1) = p(5) = 11. Then x(0) mod x(1) = x(2) = 2, hence x(1) mod x(2) = x(3) = 1. Since there are two modular reductions, a(5) = 2.


PROG

#(sage)
A = []
q = 1
for i in range(100):
q = next_prime(q)
p = next_prime(q)
ctr = 0
while q!=1:
r = p%q
p = q
q = r
ctr += 1
A.append(ctr)
print A
(PARI) ctgcd(m, n)=my(s); while(n!=1, [m, n]=[n, m%n]; s++); s
a(n, p=prime(n), q=nextprime(p+1))=ctgcd(p, qp)+1 \\ Charles R Greathouse IV, Nov 28 2016


CROSSREFS

Cf. A051010, A072030, A188224, A034883, A267178.
Sequence in context: A073813 A104517 A098397 * A082091 A334216 A100549
Adjacent sequences: A278741 A278742 A278743 * A278745 A278746 A278747


KEYWORD

nonn


AUTHOR

Adnan Baysal, Nov 27 2016


STATUS

approved



