This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A300234 a(n) = number of steps in simple Euclidean algorithm for gcd(n,k) to reach the termination test n=k when starting with n = n and k = phi(n). 6
 0, 1, 2, 1, 4, 2, 6, 1, 2, 3, 10, 2, 12, 4, 8, 1, 16, 2, 18, 3, 4, 6, 22, 2, 4, 7, 2, 4, 28, 6, 30, 1, 9, 9, 9, 2, 36, 10, 5, 3, 40, 4, 42, 6, 8, 12, 46, 2, 6, 3, 10, 7, 52, 2, 5, 4, 6, 15, 58, 6, 60, 16, 4, 1, 10, 8, 66, 9, 11, 13, 70, 2, 72, 19, 8, 10, 13, 6, 78, 3, 2, 21, 82, 4, 24, 22, 12, 6, 88, 6, 11, 12, 8, 24, 13, 2, 96, 4, 9, 3, 100, 10, 102, 7, 9 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,3 LINKS Antti Karttunen, Table of n, a(n) for n = 1..65537 Antti Karttunen, Scheme (Racket) program to compute this sequence FORMULA a(n) = A285721(n,A000010(n)). a(n) = n - A300238(n). EXAMPLE For n = 1, phi(1) = 1, and the arguments for gcd are equal at the start, thus a(1) = 0. For n = 2, eulerphi(2) = 1, gcd(2,1) = gcd(1,1), thus 1 step were required to reach the termination condition, and a(2) = 1. For n = 5, eulerphi(5) = 4, gcd(5,4) = gcd(4,1) = gcd(3,1) = gcd(2,1) = gcd(1,1), four steps required, thus a(5) = 4. For n = 6, eulerphi(6) = 2, gcd(6,2) = gcd(4,2) = gcd(2,2), two steps required, thus a(6) = 2. Here a simple subtracting version of gcd-algorithm is used, where the new versions of two arguments will be the smaller argument and the smaller argument subtracted from the larger, and this is repeated until both are equal. PROG (PARI) A285721(n, k) = if(n==k, 0, 1 + A285721(abs(n-k), min(n, k))); A300234(n) = A285721(n, eulerphi(n)); CROSSREFS Cf. A000010, A285721. Cf. also A286594, A300227, A300228, A300237, A300238. Sequence in context: A057923 A147763 A098371 * A070777 A173614 A173557 Adjacent sequences:  A300231 A300232 A300233 * A300235 A300236 A300237 KEYWORD nonn AUTHOR Antti Karttunen, Mar 02 2018 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 October 13 16:10 EDT 2019. Contains 327966 sequences. (Running on oeis4.)