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,5

Comments

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

Links

Antti Karttunen, Table of n, a(n) for n = 0..16384

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

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

Example

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.

Prog

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

Crossrefs

Cf. A006530, A052126, A076563, A175126.

Sequence in context: A328847 A331175 A331954 * A078899 A055172 A187445

Adjacent sequences: A309889 A309890 A309891 * A309893 A309894 A309895

Keyword

nonn

Author

Rémy Sigrist, Aug 21 2019

Status

approved