A309892 - OEIS

%I #16 Aug 22 2019 20:43:27

%S 0,1,1,1,2,1,2,1,3,3,2,1,4,1,2,3,3,1,4,1,4,3,2,1,4,5,2,5,4,1,6,1,7,3,

%T 2,5,4,1,2,3,6,1,6,1,4,7,2,1,8,7,8,3,4,1,4,5,8,3,2,1,6,1,2,9,3,5,6,1,

%U 4,3,10,1,4,1,2,11,4,7,6,1,12,7,2,1,8,5

%N a(0) = 0, a(1) = 1, and for any n > 1, a(n) is the number of iterations of the map x -> x - gpf(x) (where gpf(x) denotes the greatest prime factor of x) required to reach 0 starting from n.

%C This sequence is similar to A175126: here we subtract the greatest prime factor, there the least prime factor.

%H Antti Karttunen, <a href="/A309892/b309892.txt">Table of n, a(n) for n = 0..16384</a>

%H Antti Karttunen, <a href="/A309892/a309892.txt">Data supplement: n, a(n) computed for n = 0..65537</a>

%F a(n) <= n / A006530(n) for any n > 0.

%F a(n) = n if n <= 1, for n >= 2, a(n) = 1+a(A076563(n)). - _Antti Karttunen_, Aug 22 2019

%e For n = 16:

%e - the greatest prime factor of 16 is 2,

%e - the greatest prime factor of 16-2 = 14 is 7,

%e - the greatest prime factor of 14-7 = 7 is 7,

%e - 7 - 7 = 0,

%e - hence a(16) = 3.

%o (PARI) a(n) = for (k=0, oo, if (n==0, return (k), n==1, n--, my (f=factor(n)); n-=f[#f~,1]))

%Y Cf. A006530, A052126, A076563, A175126.

%K nonn

%O 0,5

%A _Rémy Sigrist_, Aug 21 2019