A335884 - OEIS

%I #15 Jul 01 2020 22:29:44

%S 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,

%T 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,

%U 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

%N 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.

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

%H Antti Karttunen, <a href="/A335884/b335884.txt">Table of n, a(n) for n = 1..65537</a>

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

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

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

%o (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))))); };

%o (PARI)

%o \\ Or empirically as:

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

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

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

%o 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));

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

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

%K nonn

%O 1,5

%A _Antti Karttunen_, Jun 29 2020