login
a(0) = 0; for n >= 1, a(n) = 1 + a(n-A009191(n)).
0

%I #15 Feb 28 2020 01:37:49

%S 0,1,1,2,3,4,4,5,4,5,5,6,5,6,6,7,8,9,6,7,7,8,8,9,9,10,10,11,11,12,12,

%T 13,13,14,14,15,12,13,13,14,14,15,15,16,16,16,17,18,18,19,19,20,20,21,

%U 21,22,19,20,20,21,19,20,20,20,21,22,22,23,23,24,24,25,20,21,21,21,22,23,23,24,25,26

%N a(0) = 0; for n >= 1, a(n) = 1 + a(n-A009191(n)).

%C Number of steps needed to reach zero when starting from k = n and repeatedly applying the map that replaces k with k - gcd(k,d(k)), where d(k) is the number of divisors of k (A000005).

%C Empirically: n/log(n) <= a(n) <= n/log(n) + 2*log(n).

%e a(6) = 1 + a(6-gcd(6,4)) = 1 + a(4) = 2 + a(4-gcd(4,3)) = 2 + a(3) = 3 + a(3-gcd(3,2)) = 3 + a(2) = 4 + a(2-gcd(2,2)) = 4 + a(0) = 4.

%o (PARI) a(n) = if (n==0, 0, 1 + a(n - gcd(n, numdiv(n)))); \\ _Michel Marcus_, Sep 25 2019

%Y Cf. A000005, A009191, A155043.

%K nonn

%O 0,4

%A _Ctibor O. Zizka_, Sep 23 2019