login
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
OFFSET
1,3
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
KEYWORD
nonn
AUTHOR
Antti Karttunen, Mar 02 2018
STATUS
approved