login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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
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(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

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, q-p)+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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 8 07:34 EDT 2020. Contains 335513 sequences. (Running on oeis4.)