A335884 - OEIS

A335884

The length of a longest path from n to a power of 2, when applying the nondeterministic maps k -> k - k/p and k -> k + k/p, where p can be any of the odd prime factors of k, and the maps can be applied in any order.

0, 0, 1, 0, 2, 1, 2, 0, 2, 2, 3, 1, 3, 2, 3, 0, 3, 2, 3, 2, 3, 3, 4, 1, 4, 3, 3, 2, 4, 3, 4, 0, 4, 3, 4, 2, 4, 3, 4, 2, 4, 3, 4, 3, 4, 4, 5, 1, 4, 4, 4, 3, 4, 3, 5, 2, 4, 4, 5, 3, 5, 4, 4, 0, 5, 4, 5, 3, 5, 4, 5, 2, 5, 4, 5, 3, 5, 4, 5, 2, 4, 4, 5, 3, 5, 4, 5, 3, 5, 4, 5, 4, 5, 5, 5, 1, 5, 4, 5, 4, 5, 4, 5, 3, 5

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,5

COMMENTS

The length of a longest path from n to a power of 2, when using the transitions x -> A171462(x) and x -> A335876(x).

LINKS

Antti Karttunen, Table of n, a(n) for n = 1..65537

FORMULA

Fully additive with a(2) = 0, and a(p) = 1+max(a(p-1), a(p+1)), for odd primes p.

For all n >= 1, A335904(n) >= a(n) >= A335881(n) >= A335875(n) >= A335885(n).

For all n >= 0, a(A335883(n)) = n.

PROG

(PARI) A335884(n) = { my(f=factor(n)); sum(k=1, #f~, if(2==f[k, 1], 0, f[k, 2]*(1+max(A335884(f[k, 1]-1), A335884(f[k, 1]+1))))); };

(PARI)

\\ Or empirically as:

A171462(n) = if(1==n, 0, (n-(n/vecmax(factor(n)[, 1]))));

A335876(n) = if(1==n, 2, (n+(n/vecmax(factor(n)[, 1]))));

A209229(n) = (n && !bitand(n, n-1));

A335884(n) = if(A209229(n), 0, my(xs=Set([n]), newxs, a, b, u); for(k=1, oo, newxs=Set([]); if(!#xs, return(k-1)); for(i=1, #xs, u = xs[i]; a = A171462(u); if(!A209229(a), newxs = setunion([a], newxs)); b = A335876(u); if(!A209229(b), newxs = setunion([b], newxs))); xs = newxs));

CROSSREFS

Cf. A052126, A171462, A335875, A335876, A335881, A335885, A335904, A335908.

Cf. A335883 (position of the first occurrence of each n).

Sequence in context: A240883 A048272 A112329 * A325033 A333626 A117448

Adjacent sequences: A335881 A335882 A335883 * A335885 A335886 A335887

KEYWORD

nonn

AUTHOR

Antti Karttunen, Jun 29 2020

STATUS

approved