login
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.
11
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
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
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. A335883 (position of the first occurrence of each n).
Sequence in context: A240883 A048272 A112329 * A325033 A333626 A117448
KEYWORD
nonn
AUTHOR
Antti Karttunen, Jun 29 2020
STATUS
approved