A309892 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.

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, 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, 4, 3, 10, 1, 4, 1, 2, 11, 4, 7, 6, 1, 12, 7, 2, 1, 8, 5

Offset: 0

Author

Rémy Sigrist, Aug 21 2019

Keywords

• nonn

Comments

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

Examples

			For n = 16:
- the greatest prime factor of 16 is 2,
- the greatest prime factor of 16-2 = 14 is 7,
- the greatest prime factor of 14-7 = 7 is 7,
- 7 - 7 = 0,
- hence a(16) = 3.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 0..16384
• Antti Karttunen, Data supplement: n, a(n) computed for n = 0..65537

Crossrefs

Cf. A006530, A052126, A076563, A175126.

Programs

PARI

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

Formula

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

a(n) = n if n <= 1, for n >= 2, a(n) = 1+a(A076563(n)). - Antti Karttunen, Aug 22 2019