cp's OEIS Frontend

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.

%I A278744 #20 Aug 22 2025 04:29:27
%S A278744 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,
%T A278744 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,
%U A278744 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
%N 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.
%C A278744 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.
%C A278744 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
%e A278744 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.
%o A278744 (Sage)
%o A278744 A = []
%o A278744 q = 1
%o A278744 for i in range(100):
%o A278744    q = next_prime(q)
%o A278744    p = next_prime(q)
%o A278744    ctr = 0
%o A278744    while q!=1:
%o A278744        r = p%q
%o A278744        p = q
%o A278744        q = r
%o A278744        ctr += 1
%o A278744    A.append(ctr)
%o A278744 print A
%o A278744 (PARI) ctgcd(m,n)=my(s); while(n!=1, [m,n]=[n,m%n]; s++); s
%o A278744 a(n,p=prime(n),q=nextprime(p+1))=ctgcd(p,q-p)+1 \\ _Charles R Greathouse IV_, Nov 28 2016
%Y A278744 Cf. A051010, A072030, A188224, A034883, A267178.
%K A278744 nonn
%O A278744 1,2
%A A278744 _Adnan Baysal_, Nov 27 2016