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

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

Offset: 1

Author

Adnan Baysal, Nov 27 2016

Keywords

• nonn

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(t-1) is the GCD. Since the p(n) and p(n+1) are distinct primes, their GCD is 1, and there corresponding x(t-1) = 1. a(n) is the number of modular reductions, i.e., t-2.

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

Examples

			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.
		

Crossrefs

Cf. A051010, A072030, A188224, A034883, A267178.

Programs

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,q-p)+1 \\ Charles R Greathouse IV, Nov 28 2016

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