cp's OEIS Frontend

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.

%I A335884 #15 Jul 01 2020 22:29:44
%S A335884 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 A335884 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 A335884 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 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.
%C A335884 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 A335884 Antti Karttunen, <a href="/A335884/b335884.txt">Table of n, a(n) for n = 1..65537</a>
%F A335884 Fully additive with a(2) = 0, and a(p) = 1+max(a(p-1), a(p+1)), for odd primes p.
%F A335884 For all n >= 1, A335904(n) >= a(n) >= A335881(n) >= A335875(n) >= A335885(n).
%F A335884 For all n >= 0, a(A335883(n)) = n.
%o A335884 (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 A335884 (PARI)
%o A335884 \\ Or empirically as:
%o A335884 A171462(n) = if(1==n,0,(n-(n/vecmax(factor(n)[, 1]))));
%o A335884 A335876(n) = if(1==n,2,(n+(n/vecmax(factor(n)[, 1]))));
%o A335884 A209229(n) = (n && !bitand(n,n-1));
%o A335884 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 A335884 Cf. A052126, A171462, A335875, A335876, A335881, A335885, A335904, A335908.
%Y A335884 Cf. A335883 (position of the first occurrence of each n).
%K A335884 nonn
%O A335884 1,5
%A A335884 _Antti Karttunen_, Jun 29 2020