login
This site is supported by donations to The OEIS Foundation.

 

Logo


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

%I

%S 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,

%T 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,

%U 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

%N 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).

%H Antti Karttunen, <a href="/A300234/b300234.txt">Table of n, a(n) for n = 1..65537</a>

%H Antti Karttunen, <a href="/A286594/a286594.txt">Scheme (Racket) program to compute this sequence</a>

%F a(n) = A285721(n,A000010(n)).

%F a(n) = n - A300238(n).

%e For n = 1, phi(1) = 1, and the arguments for gcd are equal at the start, thus a(1) = 0.

%e 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.

%e 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.

%e For n = 6, eulerphi(6) = 2, gcd(6,2) = gcd(4,2) = gcd(2,2), two steps required, thus a(6) = 2.

%e 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.

%o (PARI)

%o A285721(n,k) = if(n==k, 0, 1 + A285721(abs(n-k),min(n,k)));

%o A300234(n) = A285721(n,eulerphi(n));

%Y Cf. A000010, A285721.

%Y Cf. also A286594, A300227, A300228, A300237, A300238.

%K nonn

%O 1,3

%A _Antti Karttunen_, Mar 02 2018

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 November 13 10:50 EST 2019. Contains 329093 sequences. (Running on oeis4.)