The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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. 15
 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, 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, 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 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,9 COMMENTS 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. 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 LINKS Antti Karttunen, Table of n, a(n) for n = 1..65537 FORMULA Fully additive with a(2) = 0, and a(p) = 1+min(a(p-1), a(p+1)), for odd primes p. For all n >= 1, a(n) <= A335875(n) <= A335881(n) <= A335884(n) <= A335904(n). For all n >= 0, a(A000244(n)) = n, and these also seem to give records. EXAMPLE 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. A171462(15749) = 15748, A335876(A15748) = 15872, A335876(15872) = 16384 = 2^14, and this is the shortest path from 15749 to a power of 2, thus a(15749) = 3. PROG (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))))); }; (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)); 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)); CROSSREFS Cf. A000043, A046051, A052126, A171462, A335876, A335875, A335881, A335884, A335904, A335907. Cf. A000079, A335911, A335912 (positions of 0's, 1's and 2's in this sequence) and array A335910. Sequence in context: A062754 A342846 A045888 * A335875 A107279 A078461 Adjacent sequences:  A335882 A335883 A335884 * A335886 A335887 A335888 KEYWORD nonn AUTHOR Antti Karttunen, Jun 29 2020 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified October 22 21:41 EDT 2021. Contains 348180 sequences. (Running on oeis4.)