The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. 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 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.

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