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

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.

Links

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

Formula

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

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

Example

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.

Prog

(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

Crossrefs

Cf. A006530, A076563.

Sequence in context: A160976 A029218 A100376 * A336318 A020738 A063279

Adjacent sequences: A382983 A382984 A382985 * A382987 A382988 A382989

Keyword

nonn,look

Author

Jakub Buczak, Apr 11 2025

Status

approved