The OEIS is supported by the many generous donors to the OEIS 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(15748) = 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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified July 17 11:42 EDT 2024. Contains 374377 sequences. (Running on oeis4.)