cp's OEIS Frontend

A335885 The length of a shortest 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 A335885 #28 May 29 2022 21:41:44
%S A335885 0,0,1,0,1,1,1,0,2,1,2,1,2,1,2,0,1,2,2,1,2,2,2,1,2,2,3,1,2,2,1,0,3,1,
%T A335885 2,2,3,2,3,1,2,2,3,2,3,2,2,1,2,2,2,2,3,3,3,1,3,2,3,2,2,1,3,0,3,3,2,1,
%U A335885 3,2,3,2,3,3,3,2,3,3,2,1,4,2,3,2,2,3,3,2,3,3,3,2,2,2,3,1,2,2,4,2,3,2,3,2,3
%N A335885 The length of a shortest 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 A335885 The length of a shortest path from n to a power of 2, when using the transitions x -> A171462(x) and x -> A335876(x) in any order.
%C A335885 a((2^e)-1) is equal to A046051(e) = A001222((2^e)-1) when e is either a Mersenne exponent (in A000043), or some other number: 1, 4, 6, 8, 16, 32. For example, 32 is present because 2^32 - 1 = 4294967295 = 3*5*17*257*65537, a squarefree product of five known Fermat primes. - _Antti Karttunen_, Aug 11 2020
%H A335885 Antti Karttunen, <a href="/A335885/b335885.txt">Table of n, a(n) for n = 1..65537</a>
%F A335885 Fully additive with a(2) = 0, and a(p) = 1+min(a(p-1), a(p+1)), for odd primes p.
%F A335885 For all n >= 1, a(n) <= A335875(n) <= A335881(n) <= A335884(n) <= A335904(n).
%F A335885 For all n >= 0, a(A000244(n)) = n, and these also seem to give records.
%e A335885 A335876(67) = 68, and A171462(68) = 64 = 2^6, and this is the shortest path from 67 to a power of 2, thus a(67) = 2.
%e A335885 A171462(15749) = 15748, A335876(15748) = 15872, A335876(15872) = 16384 = 2^14, and this is the shortest path from 15749 to a power of 2, thus a(15749) = 3.
%o A335885 (PARI) A335885(n) = { my(f=factor(n)); sum(k=1,#f~,if(2==f[k,1],0,f[k,2]*(1+min(A335885(f[k,1]-1),A335885(f[k,1]+1))))); };
%o A335885 (PARI)
%o A335885 \\ Or empirically as:
%o A335885 A171462(n) = if(1==n,0,(n-(n/vecmax(factor(n)[, 1]))));
%o A335885 A335876(n) = if(1==n,2,(n+(n/vecmax(factor(n)[, 1]))));
%o A335885 A209229(n) = (n && !bitand(n,n-1));
%o A335885 A335885(n) = if(A209229(n),0,my(xs=Set([n]),newxs,a,b,u); for(k=1,oo, newxs=Set([]); for(i=1,#xs,u = xs[i]; a = A171462(u); if(A209229(a), return(k)); b = A335876(u); if(A209229(b), return(k)); newxs = setunion([a],newxs); newxs = setunion([b],newxs)); xs = newxs));
%Y A335885 Cf. A000043, A046051, A052126, A171462, A335876, A335875, A335881, A335884, A335904, A335907.
%Y A335885 Cf. A000079, A335911, A335912 (positions of 0's, 1's and 2's in this sequence) and array A335910.
%K A335885 nonn
%O A335885 1,9
%A A335885 _Antti Karttunen_, Jun 29 2020