A382986 a(n) is the number of iterations that n requires to reach 0 under the map k -> b(k) where b(k) = k+1 if k is even, and b(k) = k-gpf(k) if k is odd, where gpf(k) is the greatest prime dividing k.

0, 1, 2, 1, 2, 1, 2, 1, 4, 3, 2, 1, 2, 1, 4, 3, 2, 1, 2, 1, 6, 5, 2, 1, 8, 7, 10, 9, 2, 1, 2, 1, 4, 3, 4, 3, 2, 1, 12, 11, 2, 1, 2, 1, 4, 3, 2, 1, 4, 3, 6, 5, 2, 1, 6, 5, 14, 13, 2, 1, 2, 1, 16, 15, 4, 3, 2, 1, 4, 3, 2, 1, 2, 1, 4, 3, 4, 3, 2, 1, 4, 3, 2, 1, 6, 5, 4, 3, 2, 1

Offset: 0

Author

Jakub Buczak, Apr 11 2025

Keywords

• nonn
• look

Comments

k -> 0 occurs when k is 1 or an odd prime and this is the only way to reach 0.

At 0, a loop 0 -> 1 -> 0 occurs and there are no other loops since either 1 or 2 steps is a decrease: b(k) < k for odd k, or b(b(k)) < k for even k >= 2.

Consecutive terms can form decreasing runs starting at an even term, such as: (4, 3, 2, 1) starting at the 8th term.

Examples

			a(0) = 0, since 0 already matches the ending condition.
a(2) = 2, since (b2)=3 and then b(3)=0.
a(3) = 1, since 3 - gpf(3) = 0.
		

Links

• Jakub Buczak, Table of n, a(n) for n = 0..10000

Crossrefs

Cf. A006530, A076563.

Programs

PARI

gpf(n) = if (n==1, 1, vecmax(factor(n)[,1]));
b(m) = if (m % 2, m - gpf(m), m+1);
a(n)= my(nb=0); while (n>1, n=b(n); nb++); nb; \\ Michel Marcus, Apr 13 2025

Python

from sympy import factorint
from itertools import count
def b(n): return n - max(factorint(n), default=0) if n&1 else n + 1
def a(n): return next(i for i in count(1) if not (n:=b(n))) if n > 1 else n
print([a(n) for n in range(90)]) # Michael S. Branicky, Apr 13 2025

Formula

a(p) = 1, for odd prime p.

a(2*n) = a(2*n+1) + 1.